【C++】—— 二叉搜索树

【C++】—— 二叉搜索树

• 1 二叉搜索树的概念
• 2 二叉搜索树的性能分析
• 3 二叉搜索树的实现
  • 3.1 基本结构
  • 3.2 insert
  • 3.3 中序遍历
  • 3.4 find
  • 3.5 erase
    • 3.5.1 情况分析
    • 3.5.2 代码实现
  • 3.5 默认成员函数
    • 3.5.1 拷贝构造
    • 3.5.2 构造函数
    • 3.5.3 赋值重载
    • 3.5.4 析构函数
• 4 二叉搜索树的应用
  • 4.1 key 搜索场景
  • 4.2 key/value 搜索场景
• 5 key 模型代码实现
• 6 key/value模型代码实现

1 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树：若它的左子树不为空，则左子树上所有节点的值都小于等于根节点的值若它的右子树不为空，则右子树上所有节点的值都大于等于根节点的值它的左右子树也都是二叉搜索树二叉搜索树种可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们学习 m a p map map / s e t set set / m u l t i m a p multimap multimap / m u l t i s e t multiset multiset 系列容器底层就是二叉搜索树，其中 m a p map map / s e t set set 不支持插入相等值， m u l t i s e t multiset multiset / m u l t i m a p multimap multimap 支持插入相等值

2 二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：O(log₂ N)最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：O( N / 2 N/2 N/2)

所以综合而言二叉搜索树增删查改时间复杂度为：O(N)

这样的二叉搜索树并不稳定，树的形状与数据的插入顺序息息相关（插入的数据是有序或较为有序的，二叉搜索树就退化成链式结构），这样的效率显然是无法满足时间的需求的。因此后续我们还将学习二叉搜索树的变形：AVL树 和 红黑树，他们才能适用于我们在内存中存储和搜索数据

另外需要说明的是，二分查找也可以实现O(logN)级别的查找效率，但是二分查找有两大缺陷：需要存储在支持下标随机访问的结构中，并且有序插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。（我们查找一个数据往往不是单纯的查找，还要对其进行增删查改等相关操作）

这也就体现出了平衡二叉搜索树的价值

3 二叉搜索树的实现

搜索二叉树分为两种：允许插入相等的值和不允许插入相等的值。
一般我们会分开用，实现两份搜索二叉树。
本文实现的是不容许数值冗余的搜索二叉树

3.1 基本结构

首先我们要定义二叉树节点，及二叉搜索树的基本结构

template<classK>structBSTNode{ K _key; BSTNode<K, V>* _left; BSTNode<K, V>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};template<classK>classBSTree{using Node = BSTNode<K>;public:private: Node* _root =nullptr;};

注：关于类型重命名，C++11给了一个新用法： u s i n g using using。 u s i n g using using 与 t y p e d e f typedef typedef 的功能是一样的，只有一些细微的差别，现阶段可认为是一样的。

搜索二叉树，模板参数我们就不用 T 了，而用K
因为一般搜索的时候，我们都要进行一个比较：比他大往右边走，比他小往左边走。我们一般把用来比较的这个值称为 Key，也就是关键字。所以我们一般用 K 来做末模版参数

3.2 insert

实现插入要怎么实现呢？前面我们学习二叉树的时候都是用递归，那这里也要用递归吗？

可以用
递归的逻辑是这样的
要插入的值比当前根大，递归到其右子树；若比它小递归到其左子树；遇到空就插进去

但是这里没必要用递归

我们直接用循环就能够搞定
我们最开始定义一个 c u r cur cur 指针指向树的根，假设现在插入的是 16， c u r cur cur 指向 8；16 比 8 大， c u r cur cur 往右边走；若比 c u r cur cur 小，往左边走，直到遇到空位。
既能用循环又能用递归的情况下，我们无脑用循环。因为递归有栈溢出的风险，却需要建立栈帧，消耗一般比循环大。
但我们不能直接 n e w new new 一个结点给 c u r cur cur。因为 c u r cur cur 只是一个临时变量，只给 c u r cur cur，树并没有将这个节点链接起来，所以我们还要有个指针 p a r e n t parent parent 记录 c u r cur cur 的父节点

当然，还有一种特殊的情况：空树。这时直接让 _ r o o t root root 指向一个 n e w new new 出的新节点即可。

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

如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）

3.3 中序遍历

搜索二叉树有一个性质：中序遍历时，是有序的。
中序遍历我们前面学习普通二叉树时实现过了，这里就不再过多介绍

voidInOrder(Node* root){if(root ==nullptr)return;_InOrder(root->_left); cout << root->_key <<" ";_InOrder(root->_right);}

但是这个中序有一个问题：不好调用
因为想要调用中序来遍历搜索二叉树，要传递一个根节点 r o o t root root。但是根是私有的，无法外面无法访问。

解决方式如下：友有元提供 G e t ( ) Get() Get() 函数

但这些方法或多或少有些麻烦，C++ 解决这种问题时，一般选择在外面套一层函数。

classBSTNode{public:voidInOrder(){_InOrder(_root); cout << endl;}private:void_InOrder(Node* root){if(root ==nullptr)return;_InOrder(root->_left); cout << root->_key <<" ";_InOrder(root->_right);}}； 

虽然我们在类外不能访问 _root，但是类里面可以啊。
这样，对外公开的接口我们就可以不用传根了

3.4 find

• 从根开始比较，查找 x x x， x x x 比根的值大则往右边走查找， x x x 比根值小则往左边走查找
• 最多查找高度次，走到空，还没找到，这个值不存在
• 如果不支持插入相等的值，找到 x x x 即可返回
• 如果支持插入相等的值，意味着有多个 x x x 的存在，一般要求查找中序的第一个 x x x。如下图，查找 3，要找到 1 的右孩子的那个 3 返回

怎样才能找到中序第一个 3 呢？按中序遍历一遍吗？这样太慢了
这里讲一下大致思路，感兴趣的小伙伴可自行实现：查找方式与上述步骤一致，有些许不同。我们知道中序遍历是：左子树、根、右子树，中序往往是先遍历左子树。因此我们按上述方式找到了 8 左节点的 3，还要进入这个 3 的左子树查找；若其左子树中有 3，再进入这个 3 的左子树；若左子树中无 3，则回退，表明这个左子树的根是中序第一个3。

Node*find(const K& key){ Node* cur = _root;while(cur !=nullptr){if(key > cur->_key){ cur = cur->_right;}elseif(key < cur->_key){ cur = cur->_left;}elsereturn cur;}returnnullptr;}

3.5 erase

3.5.1 情况分析

二叉搜索树的删除比较麻烦，需分情况讨论要删除的解决点 N N N 左右节点都为空，即叶子节点要删除的结点 N N N 左孩子为空，右孩子结点不为空要删除的结点 N N N 右孩子为空，左孩子结点不为空要删除的节点 N N N 左右子树都不为空

对应以上四种解决方案第一种情况：这种情况最好解决，将 N 节点的父亲对应孩子指针指向空，直接删除 N 节点（情况一可以当成情况二、三来处理，效果是一样的）第二种情况：把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点第三种情况：把 N 结点的父亲对应孩子指针指向 N 的左孩子⼦，直接删除 N 结点第四种情况：无法直接删除 N 节点，因为 N 的两个孩子无处安放，我们可以用替换法删除。找到 N 左子树的值最大节点 R（最右节点）或者 N 右子树的最小节点 R（最左节点）替代 N，因为这两个节点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代的意思就是 N 和 R 的两个节点的值交换，转而变成删除 R 节点，R 结点符合情况 2 或情况 3，可以直接删除

3.5.2 代码实现

首先是查找，代码逻辑与 f i n d find find 的实现相似。
不同的是，当找到相等的值（走到 e l s e else else 时）， e r a s e erase erase 是进行删除； f i n d find find 是直接退出，当走出循环，表示没有找到要删除的值， r e t u r n return return f a l s e false false

boolErase(const K& 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{// 删除}returnfalse;}

左为空：
虽然要删除的节点 N N N 左为空，但是并不知道 N N N 节点是父节点 R R R 的左节点还是右节点，因此需要先进行判断

// 左树为空if(cur->_left ==nullptr){if(parent->_left == cur){ parent->_left = cur->_right;}else{ parent->_right = cur->_right;}delete cur;}

右为空：
右为空的判断逻辑与左为空时一样的

// 右树为空elseif(cur->_right ==nullptr){if(parent->_left == cur){ parent->_left = cur->_left;}else{ parent->_right = cur->_left;}delete cur;}

但是上述情况还有一种坑的情况，如图：

假设现在我们要删除的是 8。
这时就需要特殊处理，需要更新 _ r o o t root root 了

// 左树为空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;}// 右树为空elseif(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* replaceParent =nullptr; Node* replace = cur->_right;//replace不断往右边走while(replace->_left){ replaceParent = replace; replace = replace->_left;}//将替代节点replace的val值赋值给本来要删除的节点cur cur->_key = replace->_key;//再删除replace节点，此时的replace只可能是前三种情况 replaceParent->_left = replace->_right;delete replace;}

删除 r e p l a c e replace replace 还有一种很坑的情况： c u r cur cur 的右孩子就是最左节点。假设我们现在要删除 8

因为 c u r cur cur 的右孩子就是最左节点，此时并没有进入循环， r e p l a c e P a r e n t replaceParent replaceParent 还是空，执行 replaceParent->_left = replace->_right; 语句就会报错
解决办法就是 r e p l a c e P a r e n t replaceParent replaceParent 初值不要给 n u l l p t r nullptr nullptr，而是给 c u r cur cur
最后删除 r e p l a c e replace replace 节点时，因为 r e p l a c e replace replace 是 r e p l a c e P a r e n t replaceParent replaceParent 的右节点，所以应是将 r e p l a c e replace replace 的孩子给 r e p l a c e P a r e n t replaceParent replaceParent 的右孩子，而不是左孩子。
所以最后删除 r e p l a c e replace replace 节点时，要判断 r e p l a c e replace replace 是 r e p l a c e P a r e n t replaceParent replaceParent 的左孩子还是右孩子

else{ Node* replaceParent = cur; Node* replace = cur->_right;while(replace->_left){ replaceParent = replace; replace = replace->_left;} cur->_key = replace->_key;if(replaceParent->_left == replace) replaceParent->_left = replace->_right;else replaceParent->_right = replace->_right;delete replace;}

3.5 默认成员函数

3.5.1 拷贝构造

二叉树的拷贝构造一定要自己实现深拷贝，如果是编译器默认生成的浅拷贝，将是一个大坑。
我们使用前序的方式来拷贝：

BSTree(const BSTree& t){ _root =Copy(t._root);} Node*Copy(Node* root){if(root ==nullptr)returnnullptr; Node* newRoot =newNode(root->_key, root->_value); newRoot->_left =Copy(root->_left); newRoot->_right =Copy(root->_right);return newRoot;}

注：这里不能用一个一个插入的方式进行拷贝，因为这样的话树的形状就变了

这里拷贝构造我们在外面套一层壳

3.5.2 构造函数

这里编译器默认生成的构造函数就能满足我们的需求，但是我们已经实现了拷贝构造，拷贝构造本身也是一种构造，因此编译器就不会再生成构造函数。
我们可以用d e f a u l t default default 强制编译器生成构造函数

// 强制生成构造BSTree()=default;

3.5.3 赋值重载

赋值重载我们直接用现代写法，让拷贝构造去干活

BSTree&operator=(BSTree tmp){swap(_root, tmp._root);return*this;}

3.5.4 析构函数

析构函数，我们一次通过后序的方式遍历所有节点，并将他们释放

~BSTree(){Destroy(_root); _root =nullptr;}voidDestroy(Node* root){if(root ==nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}

同理，析构函数我们在外面套一层外壳

4 二叉搜索树的应用

搜索二叉树的使用场景分为两个： k e y key key搜索场景和k e y / v a l u e key/value key/value搜索场景

4.1 key 搜索场景

k e y key key 搜索场景：即只有 k e y key key 作为关键值，结构中只需要存储 k e y key key 即可，关键值即为需要搜索到的值，搜索场景只需要判断 k e y key key 在不在。 k e y key key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 k e y key key 破坏搜索树结构了。

一句话来说 k e y key key 搜索场景就是用来判断在不在

场景一：校区无人值守车库，小区车库只有买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统（后台系统可以用搜索二叉树的结果来存储车牌号），车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入

场景二：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示

4.2 key/value 搜索场景

k e y key key/ v a l u e value value 搜索场景：每一个关键值 k e y key key，都有与之对应的值 v a l u e value value， v a l u e value value 可以任意类型对象。树结构中（节点）除了需要存储 k e y key key 还要存储对应的 v a l u e value value，增/删/查还是以 k e y key key 为关键字走二叉搜索树的规则进行比较，可以快速查找到 k e y key key 对应的 v a l u e value value。 k e y key key/ v a l u e value value 的搜索场景实现的二叉搜索树支持修改，那时不支持修改 k e y key key，修改 k e y key key 破坏搜索树结构了，可以修改 v a l u e value value

场景1：简单中英互译字典。树的结构中（节点）存储key（英文）和value（中文），搜索黑丝输入英文，则同时查找到了引文对应的中文。

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌（key）和入场时间（value）；出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出听出费用，缴费后抬杆，车辆离场

场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在说明这个单词第一次出现，存在则++单词对应的次数

key/value模型的应用：
输入单词，查找单词对应的中文翻译

voidTestBSTree1(){ BSTree<string, string> dict; dict.Insert("string","字符串"); dict.Insert("left","左边"); dict.Insert("insert","插入"); string str;while(cin >> str){// 搜索二叉树结点的地址 BSTreeNode<string, string>* cur = dict.Find(str);if(cur){ cout << cur->_value << endl;}else{ cout <<"没有此单词"<< endl;}}}

统计水果个数：

voidTestBSTree2(){// 统计水果的个数 string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉","苹果","草莓","苹果","草莓"}; BSTree<string,int> countTree;for(constauto& str : arr){//BSTreeNode<string, int>* cur = countTree.Find(str);auto cur = countTree.Find(str);// 没有该水果则插入if(cur ==nullptr){ countTree.Insert(str,1);}// 有该水果则将value值++else{ cur->_value++;}} countTree.InOrder();}

5 key 模型代码实现

namespace key {template<classK>structBSTNode{ K _key; BSTNode<K>* _left; BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};// Binary Search Tree// Keytemplate<classK>classBSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K>;public:boolInsert(const K& key){if(_root ==nullptr){ _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->_right = cur;}else{ parent->_left = cur;}returntrue;}boolFind(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{returntrue;}}returnfalse;}boolErase(const K& 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{// 删除// 左为空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;}elseif(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* replaceParent = cur; Node* replace = cur->_right;while(replace->_left){ replaceParent = replace; replace = replace->_left;} cur->_key = replace->_key;if(replaceParent->_left == replace) replaceParent->_left = replace->_right;else replaceParent->_right = replace->_right;delete replace;}returntrue;}}returnfalse;}voidInOrder(){_InOrder(_root); cout << endl;}private:void_InOrder(Node* root){if(root ==nullptr){return;}_InOrder(root->_left); cout << root->_key <<" ";_InOrder(root->_right);}private: Node* _root =nullptr;};}

6 key/value模型代码实现

namespace key_value {template<classK,classV>structBSTNode{const K _key; V _value; BSTNode<K, V>* _left; BSTNode<K, V>* _right;BSTNode(const K& key,const V& value):_key(key),_value(value),_left(nullptr),_right(nullptr){}};// Binary Search Tree// Key/valuetemplate<classK,classV>classBSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K, V>;public:// 强制生成构造BSTree()=default;BSTree(const BSTree& t){ _root =Copy(t._root);} BSTree&operator=(BSTree tmp){swap(_root, tmp._root);return*this;}~BSTree(){Destroy(_root); _root =nullptr;}boolInsert(const K& key,const V& value){if(_root ==nullptr){ _root =newNode(key, value);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, value);if(parent->_key < key){ parent->_right = cur;}else{ parent->_left = cur;}returntrue;} Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_key < key){ cur = cur->_right;}elseif(cur->_key > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}boolErase(const K& 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{// 删除// 左为空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;}elseif(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* replaceParent = cur; Node* replace = cur->_right;while(replace->_left){ replaceParent = replace; replace = replace->_left;} cur->_key = replace->_key;if(replaceParent->_left == replace) replaceParent->_left = replace->_right;else replaceParent->_right = replace->_right;delete replace;}returntrue;}}returnfalse;}voidInOrder(){_InOrder(_root); cout << endl;}private:void_InOrder(Node* root){if(root ==nullptr){return;}_InOrder(root->_left); cout << root->_key <<":"<< root->_value << endl;_InOrder(root->_right);}voidDestroy(Node* root){if(root ==nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;} Node*Copy(Node* root){if(root ==nullptr)returnnullptr; Node* newRoot =newNode(root->_key, root->_value); newRoot->_left =Copy(root->_left); newRoot->_right =Copy(root->_right);return newRoot;}private: Node* _root =nullptr;};}

好啦，本期关于二叉树的知识就介绍到这里啦，希望本期博客能对你有所帮助。同时，如果有错误的地方请多多指正，让我们在 C++ 的学习路上一起进步！