大连响应式网站建设,同城信息小程序源码,网站建设公司推荐q479185700顶上,局域网内部网站建设app下载文章目录 一、二叉搜索树1.二叉搜索树概念2.二叉搜索树操作3.二叉搜索树的实现 二、二叉搜索树的应用1.kv模型2.kv模型的实现 三、 二叉搜索树的性能分析 一、二叉搜索树
1.二叉搜索树概念
二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性… 文章目录 一、二叉搜索树1.二叉搜索树概念2.二叉搜索树操作3.二叉搜索树的实现 二、二叉搜索树的应用1.kv模型2.kv模型的实现 三、 二叉搜索树的性能分析 一、二叉搜索树
1.二叉搜索树概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 2.二叉搜索树操作 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};1二叉搜索树的查找
a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。
b、最多查找高度次走到到空还没找到这个值不存在。
2二叉搜索树的插入
插入的具体过程如下
a. 树为空则直接新增节点赋值给root指针
b. 树不空按二叉搜索树性质查找插入位置插入新节点 3二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回否则要删除的结点可能分下面四种情况
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下
情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题–替换法删除 注意 使用替换法删除我们通常替换所需删除节点右树中的最小节点即所需删除节点右树区域的最左节点。需要与被删除节点替换的节点可能左为空所以我们不能直接删除它我们还要多做一些工作–要考虑情况c发生的可能性做情况c一样的工作。 使用替换法删除还要考虑根节点的删除问题根节点就是所需删除节点右树区域的最左节点 3.二叉搜索树的实现 BSTree.h
namespace key
{templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:/*BSTree():_root(nullptr){}*/BSTree() default; // 制定强制生成默认构造BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);//_root nullptr;}bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{return false;}}cur new Node(key);// 链接if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return true;}}return false;}bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{// 删除// 1、左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;} // 2、右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 找右树最小节点替代也可以是左树最大节点替代Node* pminRight cur;Node* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_left minRight) //考虑根节点做判断{pminRight-_left minRight-_right; //正常节点}else{pminRight-_right minRight-_right; //根节点}delete minRight;}return true;}}return false;}protected:Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}private:Node* _root nullptr;};
}Test.cpp
void TestBSTree1()
{int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };key::BSTreeint t1;for (auto e : a){t1.Insert(e);}//t1.InOrder(t1.GetRoot());t1.InOrder();/*t1.Erase(7);t1.InOrder();t1.Erase(14);t1.InOrder();t1.Erase(3);t1.InOrder();*/t1.Erase(8);t1.InOrder();for (auto e : a){t1.Erase(e);t1.InOrder();}t1.InOrder();
}int main()
{TestBSTree1();return 0;
}二、二叉搜索树的应用
1.kv模型 K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误 KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。
2.kv模型的实现 改造二叉搜索树为KV结构
// 改造二叉搜索树为KV结构
namespace key_value
{// BinarySearchTree -- BSTree// SearchBinaryTreetemplateclass K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};templateclass K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public:bool Insert(const K key, const V value){if (_root nullptr){_root new Node(key, value);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{return false;}}cur new Node(key, value);// 链接if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return cur;}}return nullptr;}bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{// 删除// 1、左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;} // 2、右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 找右树最小节点替代也可以是左树最大节点替代Node* pminRight cur;Node* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}protected:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}private:Node* _root nullptr;};
}测试用例
// 测试用例
void TestBSTree2()
{key_value::BSTreestring, string dict;dict.Insert(sort, 排序);dict.Insert(left, 左边);dict.Insert(right, 右边);dict.Insert(string, 字符串);dict.Insert(insert, 插入);dict.Insert(erase, 删除);string str;while (cin str){auto ret dict.Find(str);if (ret){cout : ret-_value endl;}else{cout 无此单词 endl;}}
}void TestBSTree3()
{string arr[] { 西瓜, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉, 梨 };key_value::BSTreestring, int countTree;for (auto str : arr){//key_value::BSTreeNodestring, int* ret countTree.Find(str);auto ret countTree.Find(str);if (ret nullptr){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();
}int main()
{TestBSTree3();return 0;
}三、 二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log_2 N以2为底N的对数最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N
结论如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优依据AVL树和红黑树的知识可以很好的解决这两个知识小编会在后续章节讲解此处先不做深入赘述。
