C++ 二叉搜索树

二叉搜索树的概念

二叉搜索树（BST）是一种特殊的二叉树。它满足一个核心规则：

对于任意一个节点，左子树中所有节点的值都小于该节点，右子树中所有节点的值都大于该节点。

例如：

二叉搜索树和普通二叉树的区别：

普通二叉树只要求每个节点最多有两个孩子。但BST 还要求节点之间满足大小关系。即上面的核心规则。

二叉搜索树的性能分析

BST （二叉搜索树）最大的价值是：

如果树比较平衡，查找、插入、删除的平均时间复杂度都是 O(log n)。此时二叉搜索树接近或就是完全二叉树，这是最优的情况。

完全二叉树：除了最后一层，其余层都是满的，且最后一层的节点都靠左排列。

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为：N。

那么这样的效率显然是无法满足我们需求的，我们后续继续讲解⼆叉搜索树的变形：平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据。

另外需要说明的是，二分查找也可以实现O(log2 N) 级别的查找效率，但是二分查找有两⼤缺陷：
1. 需要存储在支持下标随机访问的结构中，并且有序。
2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据⼀般需要挪动数
据。这里也就体现出了平衡二叉搜索树的价值。

二叉搜索树的插入

插⼊的具体过程如下：
1. 树为空，则直接新增结点，赋值给root指针
2. 树不空，按二叉搜索树性质，插⼊值比当前结点⼤往右走，插⼊值比当前结点小往左走，找到空位置，插入新结点。
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑⼀致性，插入相等的值不要⼀会往右走，⼀会往左走）

二叉搜索树的查找

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

二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）
1. 要删除结点N左右孩子均为空
2. 要删除的结点N左孩子位空，右孩子结点不为空
3. 要删除的结点N右孩子位空，左孩子结点不为空
4. 要删除的结点N左右孩子结点均不为空

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

案例演示

二叉搜索树的优点和缺点

BST 的优点：

1. 查找比普通数组线性查找快
2. 插入和删除比较方便
3. 中序遍历可以得到有序序列
4. 适合实现动态集合（在动态变化中，始终保持有序，插入、删除、查找都高效）

缺点是：树可能退化成链表。

如果数据接近有序，普通 BST 性能会变差。比如输入1,2,3,4,5：

这就失去了BST的高效性。

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

key搜索场景

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

常见场景

1. 判断某个数字是否出现过
2. 存储一批不重复的编号
3. 维护一个有序集合
4. 求最大值、最小值
5. 判断元素是否存在
6. 中序遍历输出有序序列

key/value搜索场景

key 用来比较和查找，value 是和 key 对应的数据。增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。

常见场景：

1. 根据学号查学生姓名
2. 根据商品编号查商品信息
3. 根据用户名查用户资料
4. 根据单词查词频
5. 根据员工 ID 查员工对象

C++ 中更推荐用什么容器实现BST这种数据结构

实际开发中，如果只是需要一个自动排序、快速查找、快速插入删除的数据结构，通常不需要自己手写 BST。可以直接用：

set<int> s;
map<string, int> mp;
multiset<int> ms;
multimap<string, int> mmp;

#include <iostream>
#include <map>
using namespace std;

int main() {
map<string, int> score;

score["Alice"] = 90;
score["Bob"] = 85;
score["Cindy"] = 95;

for (auto& p : score) {
cout << p.first << " " << p.second << endl;
}

return 0;
}

输出会按 key 排序：

Alice 90
Bob 85
Cindy 95

工程开发时：优先使用 set、map、multiset、multimap。需要稳定高性能时：可以使用红黑树、AVL 树等平衡搜索树

关于上述容器不支持修改key值的说明

比如 BST 中有：

  10
  / \\
 5 20

如果你直接把 5 改成 30：

  10
   / \\
30 20

这棵树就不再是 BST 了，因为 30 在 10 的左边，但它比 10 大

你可能会疑惑为什么修改key值后容器不能自动调整？

答案是，你直接修改 key，相当于“偷偷改了节点的排序依据”，容器本身并不知道你改了，也就没机会重新调整。可以理解为，插入元素的时候，容器会根据这个key值决定按规则决定把节点放在哪里。若是后续手动修改，容器是不知道被修改的，识别不了，因此就破坏了BST的结构。

但是删除key，容器会自动调整，使之满足二叉搜索树的规则。因为删除是容器提供的正规操作，只要执行删除，容器就知道要做结构调整了。

正确修改key的方式，删除旧 key，再插入新 key。插入新key，容器才会给你按规则调整。

删除 key：是容器知道的操作，所以能自动调整。

修改 key：是绕过容器规则偷偷改变排序依据，容器无法感知，也无法保证树结构正确。

二叉搜索树和set、map容器的关系

二叉搜索树 BST 是一种底层数据结构思想；set、map 是 C++ STL 提供的容器。set、map 的底层通常就是用“平衡二叉搜索树”，尤其是红黑树实现的。

红黑树，可以理解为一种特殊的二叉搜索树，它的结构近似平衡。

总结

二叉搜索树是思想和底层数据结构；
set 是只存 key 的有序容器；
map 是存 key/value 的有序容器；
set/map 通常用红黑树这种平衡二叉搜索树实现。

set 和 map 为什么不用普通 BST？

因为普通 BST 可能退化。比如插入1,2,3,4,5，普通BST会退化成链表的形式。此时，查找5需要走5次，复杂度接近o(n)。

而红黑树能通过它的规则维持树的大致平衡。更加高效：

查找：O(log n)
插入：O(log n)
删除：O(log