C++ | 二叉搜索树

回顾：上一篇我们结束了 多态，接下来这篇文章让我们进入到 二叉搜索树 的学习，体会新的设计思路吧~

一 概念

二叉搜索树又称⼆叉排序树。

性质

1. 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
2. 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
3. 它的左右子树也分别为⼆叉搜索树。
4. ⼆叉搜索树中可以⽀持插入相等的值，也可以不⽀持插入相等的值，后续会提到具体实现。

二 性能分析

2.1 二叉搜索树性能分析

1. 最优情况下，⼆叉搜索树为完全⼆叉树，其高度（即时间复杂度）为： logN。
2. 最坏情况下，二叉搜索树为单枝，其高度（即时间复杂度）为： N。
3. 总结：⼆叉搜索树增删查改时间复杂度为 O(N)

2.2 二分查找

二分查找时间复杂度为logN，但是有两大缺陷：

1. 需要存储在支持下标随机访问的结构中，并且有序。
2. 插入和删除数据效率很低（因为存储在下标随机访问的结构中，插入和删除数据⼀般需要挪动数据）。

三 二叉搜索树的插入

1. 树为空。
2. 树不为空，按⼆叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走。
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走。

3.1 上代码

boolinsert(constK&key){if(!_root){_root=newNode(key);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(key);if(parent->_key>key){parent->_left=cur;}else{parent->_right=cur;}returntrue;}

当前不支持插入已出现过的值。

3.2 测试

wyzy::BSTree<int>tree;inta[]={8,3,1,10,6,4,7,14,13};for(autoe:a){tree.insert(e);}tree.inOrder();

运行：

四 二叉搜索树的查找

4.1 上代码

boolfind(constK&key){Node*cur=_root;while(cur){if(cur->_key<key){cur=cur->_right;}elseif(cur->_key>key){cur=cur->_left;}else{returntrue;}}returnfalse;}

跟插入类似的逻辑，只不过这里找到相等的就可以结束了。

4.2 测试

插入代码同上。

while(cin>>x){if(tree.find(x)){cout<<"find it"<<endl;}else{cout<<"not find it"<<endl;}}

运行：

测试涉及operator bool把iostream对象转换成bool值。

五 二叉搜索树的删除

5.1 四种情况

1. 要删除结点N左右孩子均为空。
2. 要删除的结点N左孩子为空，右孩子结点不为空。
3. 要删除的结点N右孩子为空，左孩子结点不为空。
4. 要删除的结点N左右孩子结点均不为空。

对应删除逻辑：

1. 直接删除。
2. 把右孩子交给父结点。
3. 把左孩子交给父结点。
4. 找 左子树的最大结点/右子树的最小结点 替代被删位置。

5.2 上代码

boolerase(constK&key){Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{break;}}if(cur){if(!cur->_left){if(!parent){_root=cur->_right;}elseif(cur==parent->_left){parent->_left=cur->_right;}else{parent->_right=cur->_right;}deletecur;}elseif(!cur->_right){if(!parent){_root=cur->_left;}elseif(cur==parent->_left){parent->_left=cur->_left;}else{parent->_right=cur->_left;}deletecur;}else{Node*mR_parent=cur;Node*minRight=cur->_right;while(minRight->_left){mR_parent=minRight;minRight=minRight->_left;}swap(cur->_key,minRight->_key);if(mR_parent==cur){mR_parent->_right=minRight->_right;}else{mR_parent->_left=minRight->_right;}deleteminRight;}returntrue;}returnfalse;}

5.3 测试

插入代码依旧。

for(autoe:a){tree.erase(e);tree.inOrder();}

运行：

六 二叉搜索树的其他实现

6.1 析构函数

6.1.1 _destory

需要有个递归函数我们另外写一个_destory：

void_destory(Node*root){if(!root){return;}_destory(root->_left);_destory(root->_right);deleteroot;}

6.1.2 析构函数

析构里调用_destory：

~BSTree(){_destory(_root);_root=nullptr;}

6.1.3 测试

依旧上面那棵树：

wyzy::BSTree<int>tree;inta[]={8,3,1,10,6,4,7,14,13};for(autoe:a){tree.insert(e);}

调试：

画出来这样：

调试：

6.2 拷贝构造

6.2.1 默认构造

这里需要显式定义默认构造。
走初始化列表：

BSTree(){}

或者强制默认生成：

BSTree()=default;

6.2.2 上代码

（1）辅助函数_constructor

void_constructor(Node*root){if(!root){return;}insert(root->_key);_constructor(root->_right);_constructor(root->_left);}

老生常谈的递归了。

（2）_constructor

BSTree(constBSTree&tree){_constructor(tree._root);}

6.2.3 测试

wyzy::BSTree<int>tree1;inta[]={8,3,1,10,6,4,7,14,13};for(autoe:a){tree1.insert(e);}wyzy::BSTree<int>tree2(tree1);tree1.inOrder();tree2.inOrder();

调试：

运行：

6.3 赋值重载

6.3.1 代码

复用。

BSTree&operator=(constBSTree&tree){if(tree._root!=nullptr){_destory(_root);_root=nullptr;}_constructor(tree._root);return*this;}

6.3.2 测试

wyzy::BSTree<int>tree1;wyzy::BSTree<int>tree2;inta[]={8,3,1,10,6,4,7,14,13};for(autoe:a){tree1.insert(e);}tree2=tree1;tree1.inOrder();tree2.inOrder();

调试：

运行：

七 二叉搜索树key和key/value使用场景

7.1 key搜索场景

• 识别车牌号。

7.2 key/value搜索场景

• 简单中英字典。
• 商场停车场。
• 统计文章单词出现次数。

二叉搜索树 的学习就到这里，下一篇我们上新的容器 map&set ，很快会更出来~