前言普通二叉树更多描述的是一种“节点最多拥有两个孩子”的组织结构但它本身并没有规定节点之间应该按照什么规则排列。**二叉搜索树Binary Search TreeBST**则在二叉树的基础上增加了一套明确的排序规则使得树结构同时具备动态存储 快速查找 有序遍历这也是二叉搜索树非常重要的原因。它一方面可以帮助我们理解查找 插入 删除 树形递归这些基本操作另一方面又是后续学习AVL树 红黑树 set map等结构的重要基础。这篇文章将从 BST 的基本性质开始逐步实现 Key 型和 Key/Value 型二叉搜索树并分析删除操作、实际应用以及普通 BST 为什么还需要进一步演化成平衡搜索树。一、二叉搜索树二叉搜索树首先是一棵二叉树但它对节点之间的大小关系提出了额外要求。对于任意一个节点可以理解为左子树中的关键码 当前节点关键码 右子树中的关键码并且当前节点的左子树和右子树本身也必须继续满足二叉搜索树的规则。例如8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13以根节点8为例左边 1、3、4、6、7 都小于 8 右边 10、13、14 都大于 8再看节点31 3 4、6、7 3所以不仅根节点满足规则每一棵子树也要继续满足相同规则。这里还有一个需要提前说明的问题BST 是否允许重复关键码并没有唯一答案要由具体设计决定。例如我们自己实现一种类似set的结构可以规定key 当前节点 ↓ 插入失败也就是整棵树中不允许出现两个相同的 Key。如果设计的是允许重复数据的结构则必须规定统一策略例如相同元素统一放左边或者相同元素统一放右边关键不是必须放哪边而是重复元素的处理规则必须始终一致否则搜索树原本的顺序关系会变得混乱。这篇实现采用不允许重复 Key的方案。中序遍历天然有序二叉搜索树最漂亮的性质之一就是按照“左子树 → 根节点 → 右子树”进行中序遍历可以直接得到升序序列。还是前面的树8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13进行中序遍历左 → 根 → 右最终得到1 3 4 6 7 8 10 13 14正好是升序。如果把遍历顺序反过来右子树 → 根节点 → 左子树则能够得到降序14 13 10 8 7 6 4 3 1这也是 BST 和普通二叉树一个非常本质的区别普通二叉树的中序遍历只是访问顺序而 BST 的中序遍历同时具有排序意义。二、性能分析二叉搜索树的插入、删除、查找效率本质上都取决于一个东西树的高度h。因为无论查找还是插入本质上都是从根节点开始不断比较 ↓ 向左 或者 向右直到找到目标或者走到空节点。所以更准确地说BST 的这些核心操作复杂度通常是O(h)真正决定效率的是树到底有多高假设一棵 BST 比较均衡8 / \ 4 12 / \ / \ 2 6 10 14每向下一层搜索范围都会明显缩小。如果共有N个节点树高通常在O(logN)这个量级。因此查找、插入、删除也可以达到O(logN)但如果插入顺序变成1 2 3 4 5BST 会形成1 \ 2 \ 3 \ 4 \ 5此时已经非常接近单链表。树高h ≈ N所以查找一个元素可能需要1 → 2 → 3 → 4 → 5一路查到底。时间复杂度也就退化成O(N)因此普通 BST 的性能不能简单写成查找一定 O(logN)更加准确的是查找 / 插入 / 删除 O(h) 树较平衡 h O(logN) 极端退化 h O(N)这个结论后面会直接引出 AVL 树和红黑树。BST 和二分查找有什么区别BST 和二分查找都利用了有序 不断缩小搜索范围所以容易让人觉得二者差不多。但它们适合的场景并不完全相同。例如有一个有序数组1 3 4 6 7 8 10 13 14使用二分查找寻找7不断取中间位置 ↓ 一半一半排除查找效率可以达到O(logN)非常优秀。问题出现在动态插入 动态删除例如现在向数组中插入5为了继续保持有序1 3 4 5 6 7 8 10 13 14后面的很多元素都可能需要移动。而 BST 插入节点时通常只需要找到正确位置 修改父节点的一条指针因此 BST 更适合数据持续变化 频繁插入 频繁删除 同时还要求快速查找的场景。可以简单理解为有序数组 二分查找 ↓ 更适合数据相对稳定 二叉搜索树 ↓ 更适合动态有序数据三、Key 型 BST先实现最基本的一种二叉搜索树每个节点只保存一个 Key。它比较接近set这种“主要关心某个关键码是否存在”的结构。节点设计BST 采用链式结构每一个节点保存关键码 左孩子指针 右孩子指针代码templateclass K struct BSTNode { K _key; BSTNodeK* _left; BSTNodeK* _right; explicit BSTNode(const K key) : _key(key) , _left(nullptr) , _right(nullptr) {} };可以把一个节点理解成┌──────────────┐ │ key │ ├──────┬───────┤ │ left │ right │ └──┬───┴───┬───┘ ↓ ↓ 左子树 右子树树本身只需要保存Node* _root;也就是整棵树的根节点。类基本框架templateclass K class BSTree { using Node BSTNodeK; public: BSTree() : _root(nullptr) {} ~BSTree() { Destroy(_root); _root nullptr; } bool Insert(const K key); bool Find(const K key) const; bool Erase(const K key); void InOrder() const { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) const { if (root nullptr) return; _InOrder(root-_left); cout root-_key ; _InOrder(root-_right); } void Destroy(Node* root) { if (root nullptr) return; Destroy(root-_left); Destroy(root-_right); delete root; } private: Node* _root; };这里有一个细节非常值得注意销毁树时使用的是左子树 ↓ 右子树 ↓ 当前节点也就是后序遍历。为什么不能一上来就delete root;因为删除root之后root-_left root-_right就已经不能再安全访问了。所以释放树必须先处理孩子先把左右子树释放干净 ↓ 最后释放当前节点这就是后序遍历特别适合树形资源释放的原因。插入BST 的插入逻辑可以概括成待插入 key 当前节点 ↓ 往左走 待插入 key 当前节点 ↓ 往右走 相等 ↓ 拒绝重复插入例如向8 / \ 3 10中插入6第一步6 8 ↓ 往左到36 3 ↓ 往右发现右孩子为空8 / \ 3 10 \ 6于是将新节点挂在那里。代码templateclass K bool BSTreeK::Insert(const K key) { if (_root nullptr) { _root new Node(key); return true; } Node* parent nullptr; Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { parent cur; cur cur-_left; } else if (key cur-_key) { parent cur; cur cur-_right; } else { return false; } } Node* newNode new Node(key); if (key parent-_key) { parent-_left newNode; } else { parent-_right newNode; } return true; }这里为什么要同时维护Node* parent; Node* cur;这是插入代码中很关键的一点。cur的任务是一路向下寻找空位置最终一定会变成nullptr但找到空位置以后我们还需要知道新节点到底应该挂到谁下面所以需要提前保存parent整个过程实际上是parent ↓ 当前节点的父节点 cur ↓ 负责继续向下寻找当cur nullptr时parent刚好停在最后一个有效节点。于是才能决定parent-_left newNode;还是parent-_right newNode;这也是 BST 插入代码里parent存在的真正原因。查找查找的逻辑和插入非常相似只是不需要创建节点。例如查找7当前树8 / \ 3 10 / \ 1 6 \ 7过程7 8 ↓ 去左子树 7 3 ↓ 去右子树 7 6 ↓ 继续右 7 7 ↓ 找到代码templateclass K bool BSTreeK::Find(const K key) const { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { cur cur-_left; } else if (key cur-_key) { cur cur-_right; } else { return true; } } return false; }和插入相比查找不需要parent因为我们不需要在某个位置挂新节点。只要找到目标return true;一路走到nullptr仍然没有找到return false;即可。如果树允许重复 Key查找语义还会进一步复杂例如到底返回任意一个相同节点还是中序顺序中的第一个必须由数据结构本身明确规定。四、删除操作BST 中最值得认真理解的操作不是插入也不是查找而是删除。因为删除之后不能只是把节点从内存中释放掉还必须保证剩余节点继续满足左 根 右的搜索树性质。假设待删除节点记为cur按照孩子情况可以分成四种表面场景1. 没有左孩子也没有右孩子 2. 没有左孩子但有右孩子 3. 有左孩子但没有右孩子 4. 左右孩子都存在其中叶子节点其实可以合并进只有一侧子树的处理逻辑。因此代码层面通常最终归纳成三类左为空 右为空 左右都不为空左子树为空例如8 \ 10 \ 14删除10。10没有左子树10 \ 14所以可以直接让10的父节点8指向10 的右子树变成8 \ 14本质上就是父节点 ↓ 跳过待删除节点 ↓ 直接连接其唯一子树如果待删除的节点本身就是根节点则_root cur-_right;即可。右子树为空这个逻辑完全对称。例如8 / 3 / 1删除38 / 1本质上父节点 ↓ 直接连接 cur 的左子树左右子树都存在这是删除中真正的难点。假设要删除8 / \ 3 10 / \ \ 1 6 14直接把8删掉是不行的。因为左边整棵子树 右边整棵子树接下来应该挂到哪里这时候通常采用替换法。可以从右子树中找到最小节点作为当前节点的替代者。或者从左子树找到最大节点也可以。为什么右子树最小节点适合替换例如8 / \ 3 12 / \ 10 14要删除8。右子树最小值就是10将8 → 10以后10 / \ 3 12 \ 14仍然满足左边 10 右边因为这个节点本来就是右子树中最小的那个元素。同理左子树最大节点也可以作为替代者。完整实现templateclass K bool BSTreeK::Erase(const K key) { Node* parent nullptr; Node* cur _root; // 先找到待删除节点 while (cur ! nullptr) { if (key cur-_key) { parent cur; cur cur-_left; } else if (key cur-_key) { parent cur; cur cur-_right; } else { break; } } if (cur nullptr) { return false; } // 情况1左子树为空 if (cur-_left nullptr) { if (parent nullptr) { _root cur-_right; } else if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } delete cur; return true; } // 情况2右子树为空 if (cur-_right nullptr) { if (parent nullptr) { _root cur-_left; } else if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } delete cur; return true; } // 情况3左右子树都存在 Node* successorParent cur; Node* successor cur-_right; // 找右子树最小节点 while (successor-_left ! nullptr) { successorParent successor; successor successor-_left; } // 用后继节点的key覆盖待删除节点 cur-_key successor-_key; // 删除原来的后继节点 if (successorParent-_left successor) { successorParent-_left successor-_right; } else { // successor 就是 cur-_right successorParent-_right successor-_right; } delete successor; return true; }这段删除代码最值得理解的不是每一行怎么背而是三个思想没有左孩子 ↓ 右孩子顶上去 没有右孩子 ↓ 左孩子顶上去 左右孩子都有 ↓ 找前驱/后继替换 ↓ 再删除替代节点只要把这三条逻辑真正搞懂删除代码就不需要死记。测试 BST可以构造int values[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };依次插入BSTreeint bst; for (int value : values) { bst.Insert(value); }中序遍历bst.InOrder();应该得到1 3 4 6 7 8 10 13 14再测试cout bst.Find(6) endl; cout bst.Find(9) endl;分别得到true false删除bst.Erase(1); // 叶子节点 bst.Erase(14); // 单孩子 bst.Erase(3); // 双孩子每删除一次再进行中序遍历如果结果始终保持有序就说明删除以后 BST 的基本性质仍然成立。五、Key/Value 型 BST前面的 BST 只保存Key它适合解决某个数据存在吗例如这个车牌是否登记 这个单词是否在词库 这个ID是否存在但很多实际问题需要保存的是Key 与Key对应的数据例如英文单词 → 中文释义 车牌号 → 入场时间 商品编号 → 商品信息 单词 → 出现次数这时候就需要Key/Value 型二叉搜索树。节点结构templateclass K, class V struct BSTNode { K _key; V _value; BSTNodeK, V* _left; BSTNodeK, V* _right; BSTNode(const K key, const V value) : _key(key) , _value(value) , _left(nullptr) , _right(nullptr) {} };和 Key 型相比只是多出V _value;但搜索树的排序依据仍然是_key而不是_value也就是说Key 负责定位 Value 负责保存与 Key 关联的数据为什么 Find 要返回节点指针Key 型只关心存在 还是 不存在所以返回bool已经够用了。但是 Key/Value 型通常还希望找到 Key ↓ 读取 Value ↓ 甚至修改 Value所以bool Find(const K key);已经不够方便。更适合Node* Find(const K key);例如templateclass K, class V BSTNodeK, V* BSTreeK, V::Find(const K key) { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { cur cur-_left; } else if (key cur-_key) { cur cur-_right; } else { return cur; } } return nullptr; }于是auto ret tree.Find(apple); if (ret ! nullptr) { ret-_value; }就可以直接修改 Value。这也是Key型 Find和Key/Value型 Find设计上的重要区别。插入插入时需要同时提供key value例如bool Insert(const K key, const V value);核心搜索逻辑仍然只比较 Keytemplateclass K, class V bool BSTreeK, V::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 ! nullptr) { if (key cur-_key) { parent cur; cur cur-_left; } else if (key cur-_key) { parent cur; cur cur-_right; } else { return false; } } Node* newNode new Node(key, value); if (key parent-_key) { parent-_left newNode; } else { parent-_right newNode; } return true; }深拷贝树中保存的是大量new Node(...)动态申请出来的节点。因此如果直接依赖编译器生成的浅拷贝BSTreeK, V t2 t1;两个对象可能只是复制_root这个指针。结果就会变成t1._root ──┐ ↓ 同一棵树 ↑ t2._root ──┘最后两个对象析构第一次 delete ↓ 节点释放 第二次 delete ↓ 重复释放显然非常危险。所以需要深拷贝整棵树。可以递归实现Node* Copy(Node* root) { if (root nullptr) { return nullptr; } Node* newRoot new Node(root-_key, root-_value); newRoot-_left Copy(root-_left); newRoot-_right Copy(root-_right); return newRoot; }这个过程非常符合树的递归结构复制根 ↓ 递归复制左子树 ↓ 递归复制右子树于是拷贝构造BSTree(const BSTree other) { _root Copy(other._root); }赋值可以使用 copy-and-swapBSTree operator(BSTree other) { std::swap(_root, other._root); return *this; }这样other先通过拷贝构造得到一棵独立的新树再交换根指针。函数结束时other析构并自动释放原来属于当前对象的旧树。这种写法比手动先释放自己 再复制 再处理自赋值更加简洁也具有较好的异常安全性。Key/Value 删除时的一个细节Key/Value 型删除的结构调整和 Key 型一样。但是如果双孩子节点使用后继节点替换只复制 Key是不够的。因为一个节点表示的是Key ↔ Value完整映射关系。所以应该同步cur-_key successor-_key; cur-_value successor-_value;否则就可能出现新的 Key 旧的 Value错配。这是实现 Key/Value BST 时非常容易忽略的细节。六、典型应用BST 的核心能力可以概括成动态 有序 按 Key 查找而 Key 型和 Key/Value 型解决的问题并不完全一样。Key 型判断“有没有”例如小区车库系统。我们只关心车牌是否在白名单可以把所有允许进入的车牌作为 Key赣A12345 赣A88888 赣A66666插入 BST。车辆到达时扫描车牌 ↓ Find(车牌) ↓ 存在 → 放行 不存在 → 拒绝如果业主车辆发生变化Insert() Erase()就可以动态更新。另一个典型场景是拼写检查。将合法词库中的单词作为 Keyapple binary computer search tree文章中每出现一个单词就dict.Find(word);如果不存在标记为可能的拼写错误同时词库还可以动态加入新词 删除废弃词Key/Value建立映射最直观的就是中英词典。例如BSTreestring, string dict; dict.Insert(apple, 苹果); dict.Insert(tree, 树); dict.Insert(search, 查找); dict.Insert(binary, 二进制);查找auto ret dict.Find(search); if (ret ! nullptr) { cout ret-_value endl; }得到查找如果需要修改释义ret-_value 搜索 / 查找;即可。而中序遍历又会天然按照Key的大小顺序输出。单词计数再来看一个很典型的统计问题string words[] { apple, banana, apple, orange, apple, banana };希望得到apple → 3 banana → 2 orange → 1可以建立BSTreestring, int countTree;遍历每个单词for (const auto word : words) { auto ret countTree.Find(word); if (ret nullptr) { countTree.Insert(word, 1); } else { ret-_value; } }逻辑非常自然第一次遇见 ↓ Insert(word, 1) 以前出现过 ↓ Find ↓ value最后进行中序遍历既得到统计结果 又天然按照单词顺序排列Key/Value 结构还适合停车场计时收费。可以定义Key 车牌号 Value 入场时间车辆入场Insert(车牌, 当前时间)车辆离场Find(车牌) ↓ 取得入场时间 ↓ 计算停车时长 ↓ 计算费用 ↓ Erase(车牌)从这个例子也可以看出Key/Value 搜索树不只是“查找某个东西存不存在”还可以维护某个 Key 当前对应的状态。七、BST 的缺陷到这里 BST 看起来似乎已经非常优秀查找快 插入快 删除快 还能保持有序但它有一个致命问题树形完全取决于数据插入顺序。例如4 2 6 1 3 5 7得到4 / \ 2 6 / \ / \ 1 3 5 7非常漂亮。但如果变成1 2 3 4 5 6 7得到1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7搜索树直接退化成链表。此时原本期待的O(logN)就会退化到O(N)所以普通 BST 最大的问题并不是查找算法不够聪明。而是它没有能力主动控制自己的高度。这也自然引出了平衡二叉搜索树AVL 树AVL 树是一种对平衡要求比较严格的搜索树。它要求任意节点左子树高度 和 右子树高度不能相差太大典型约束是平衡因子绝对值不超过1。当插入或删除破坏平衡后会通过旋转重新调整结构。优势是树高控制严格 查找性能稳定代价则是插入删除时 可能需要较频繁调整红黑树红黑树也是平衡搜索树但它不像 AVL 那样追求严格高度平衡而是通过节点颜色 一组颜色规则 旋转与变色保证树不会严重失衡。因此它追求的是查询、插入和删除之间更加均衡的综合性能。这也是工程实现中经常采用红黑树的重要原因。和 STL 的关系我们前面自己实现的Key 型 BST可以帮助理解set / multiset这一类只围绕 Key 组织数据的容器。而Key/Value 型 BST则和map / multimap的设计思想非常接近。其中set map要求 Key 唯一。而multiset multimap允许出现重复 Key。这些有序关联容器的迭代顺序也是按 Key 有序从学习思路上看可以把它们串成普通 BST ↓ 理解有序搜索树 ↓ 平衡搜索树 ↓ 红黑树 ↓ set / map 等有序关联容器需要稍微严谨一点的是C 标准规定的是这些容器的行为、复杂度和有序语义并没有强制所有标准库必须使用某一种具体树结构主流实现通常采用红黑树一类的平衡搜索树。这样理解会比单纯记住map 红黑树更加准确。总结二叉搜索树真正重要的地方并不是学会写几个if (key cur-_key)而是理解它是如何利用“有序”改变普通二叉树的。整条逻辑可以串成普通二叉树 ↓ 增加大小关系约束 ↓ 二叉搜索树 BST ↓ 左 根 右 ↓ 中序遍历天然有序 ↓ 按大小关系缩小搜索范围 ↓ Insert / Find / Erase ↓ Key 型 解决“是否存在” ↓ Key/Value 型 解决“映射关系” ↓ 普通 BST 可能退化 ↓ AVL / 红黑树 ↓ set / map 等有序关联容器如果只记三个最核心的点我觉得应该是第一 左子树 根 右子树 第二 中序遍历天然有序 第三 增删查复杂度本质取决于树高 h尤其是第三点。普通 BST 真正的性能公式其实可以写成Insert Find Erase ↓ O(h)如果h ≈ logN它非常高效。如果h ≈ N它就退化成接近链表。所以后续学习 AVL 树和红黑树时真正要解决的问题并不是推翻 BST而是想办法维持 BST 的有序性质同时控制树的高度。理解了这一点再继续学习平衡树会发现 AVL 和红黑树并不是突然冒出来的新结构而是在普通二叉搜索树之上对“平衡性”这一缺陷进行进一步修正。 【C++进阶】：（3）二叉搜索树原理、实现与应用
前言普通二叉树更多描述的是一种“节点最多拥有两个孩子”的组织结构但它本身并没有规定节点之间应该按照什么规则排列。**二叉搜索树Binary Search TreeBST**则在二叉树的基础上增加了一套明确的排序规则使得树结构同时具备动态存储 快速查找 有序遍历这也是二叉搜索树非常重要的原因。它一方面可以帮助我们理解查找 插入 删除 树形递归这些基本操作另一方面又是后续学习AVL树 红黑树 set map等结构的重要基础。这篇文章将从 BST 的基本性质开始逐步实现 Key 型和 Key/Value 型二叉搜索树并分析删除操作、实际应用以及普通 BST 为什么还需要进一步演化成平衡搜索树。一、二叉搜索树二叉搜索树首先是一棵二叉树但它对节点之间的大小关系提出了额外要求。对于任意一个节点可以理解为左子树中的关键码 当前节点关键码 右子树中的关键码并且当前节点的左子树和右子树本身也必须继续满足二叉搜索树的规则。例如8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13以根节点8为例左边 1、3、4、6、7 都小于 8 右边 10、13、14 都大于 8再看节点31 3 4、6、7 3所以不仅根节点满足规则每一棵子树也要继续满足相同规则。这里还有一个需要提前说明的问题BST 是否允许重复关键码并没有唯一答案要由具体设计决定。例如我们自己实现一种类似set的结构可以规定key 当前节点 ↓ 插入失败也就是整棵树中不允许出现两个相同的 Key。如果设计的是允许重复数据的结构则必须规定统一策略例如相同元素统一放左边或者相同元素统一放右边关键不是必须放哪边而是重复元素的处理规则必须始终一致否则搜索树原本的顺序关系会变得混乱。这篇实现采用不允许重复 Key的方案。中序遍历天然有序二叉搜索树最漂亮的性质之一就是按照“左子树 → 根节点 → 右子树”进行中序遍历可以直接得到升序序列。还是前面的树8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13进行中序遍历左 → 根 → 右最终得到1 3 4 6 7 8 10 13 14正好是升序。如果把遍历顺序反过来右子树 → 根节点 → 左子树则能够得到降序14 13 10 8 7 6 4 3 1这也是 BST 和普通二叉树一个非常本质的区别普通二叉树的中序遍历只是访问顺序而 BST 的中序遍历同时具有排序意义。二、性能分析二叉搜索树的插入、删除、查找效率本质上都取决于一个东西树的高度h。因为无论查找还是插入本质上都是从根节点开始不断比较 ↓ 向左 或者 向右直到找到目标或者走到空节点。所以更准确地说BST 的这些核心操作复杂度通常是O(h)真正决定效率的是树到底有多高假设一棵 BST 比较均衡8 / \ 4 12 / \ / \ 2 6 10 14每向下一层搜索范围都会明显缩小。如果共有N个节点树高通常在O(logN)这个量级。因此查找、插入、删除也可以达到O(logN)但如果插入顺序变成1 2 3 4 5BST 会形成1 \ 2 \ 3 \ 4 \ 5此时已经非常接近单链表。树高h ≈ N所以查找一个元素可能需要1 → 2 → 3 → 4 → 5一路查到底。时间复杂度也就退化成O(N)因此普通 BST 的性能不能简单写成查找一定 O(logN)更加准确的是查找 / 插入 / 删除 O(h) 树较平衡 h O(logN) 极端退化 h O(N)这个结论后面会直接引出 AVL 树和红黑树。BST 和二分查找有什么区别BST 和二分查找都利用了有序 不断缩小搜索范围所以容易让人觉得二者差不多。但它们适合的场景并不完全相同。例如有一个有序数组1 3 4 6 7 8 10 13 14使用二分查找寻找7不断取中间位置 ↓ 一半一半排除查找效率可以达到O(logN)非常优秀。问题出现在动态插入 动态删除例如现在向数组中插入5为了继续保持有序1 3 4 5 6 7 8 10 13 14后面的很多元素都可能需要移动。而 BST 插入节点时通常只需要找到正确位置 修改父节点的一条指针因此 BST 更适合数据持续变化 频繁插入 频繁删除 同时还要求快速查找的场景。可以简单理解为有序数组 二分查找 ↓ 更适合数据相对稳定 二叉搜索树 ↓ 更适合动态有序数据三、Key 型 BST先实现最基本的一种二叉搜索树每个节点只保存一个 Key。它比较接近set这种“主要关心某个关键码是否存在”的结构。节点设计BST 采用链式结构每一个节点保存关键码 左孩子指针 右孩子指针代码templateclass K struct BSTNode { K _key; BSTNodeK* _left; BSTNodeK* _right; explicit BSTNode(const K key) : _key(key) , _left(nullptr) , _right(nullptr) {} };可以把一个节点理解成┌──────────────┐ │ key │ ├──────┬───────┤ │ left │ right │ └──┬───┴───┬───┘ ↓ ↓ 左子树 右子树树本身只需要保存Node* _root;也就是整棵树的根节点。类基本框架templateclass K class BSTree { using Node BSTNodeK; public: BSTree() : _root(nullptr) {} ~BSTree() { Destroy(_root); _root nullptr; } bool Insert(const K key); bool Find(const K key) const; bool Erase(const K key); void InOrder() const { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) const { if (root nullptr) return; _InOrder(root-_left); cout root-_key ; _InOrder(root-_right); } void Destroy(Node* root) { if (root nullptr) return; Destroy(root-_left); Destroy(root-_right); delete root; } private: Node* _root; };这里有一个细节非常值得注意销毁树时使用的是左子树 ↓ 右子树 ↓ 当前节点也就是后序遍历。为什么不能一上来就delete root;因为删除root之后root-_left root-_right就已经不能再安全访问了。所以释放树必须先处理孩子先把左右子树释放干净 ↓ 最后释放当前节点这就是后序遍历特别适合树形资源释放的原因。插入BST 的插入逻辑可以概括成待插入 key 当前节点 ↓ 往左走 待插入 key 当前节点 ↓ 往右走 相等 ↓ 拒绝重复插入例如向8 / \ 3 10中插入6第一步6 8 ↓ 往左到36 3 ↓ 往右发现右孩子为空8 / \ 3 10 \ 6于是将新节点挂在那里。代码templateclass K bool BSTreeK::Insert(const K key) { if (_root nullptr) { _root new Node(key); return true; } Node* parent nullptr; Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { parent cur; cur cur-_left; } else if (key cur-_key) { parent cur; cur cur-_right; } else { return false; } } Node* newNode new Node(key); if (key parent-_key) { parent-_left newNode; } else { parent-_right newNode; } return true; }这里为什么要同时维护Node* parent; Node* cur;这是插入代码中很关键的一点。cur的任务是一路向下寻找空位置最终一定会变成nullptr但找到空位置以后我们还需要知道新节点到底应该挂到谁下面所以需要提前保存parent整个过程实际上是parent ↓ 当前节点的父节点 cur ↓ 负责继续向下寻找当cur nullptr时parent刚好停在最后一个有效节点。于是才能决定parent-_left newNode;还是parent-_right newNode;这也是 BST 插入代码里parent存在的真正原因。查找查找的逻辑和插入非常相似只是不需要创建节点。例如查找7当前树8 / \ 3 10 / \ 1 6 \ 7过程7 8 ↓ 去左子树 7 3 ↓ 去右子树 7 6 ↓ 继续右 7 7 ↓ 找到代码templateclass K bool BSTreeK::Find(const K key) const { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { cur cur-_left; } else if (key cur-_key) { cur cur-_right; } else { return true; } } return false; }和插入相比查找不需要parent因为我们不需要在某个位置挂新节点。只要找到目标return true;一路走到nullptr仍然没有找到return false;即可。如果树允许重复 Key查找语义还会进一步复杂例如到底返回任意一个相同节点还是中序顺序中的第一个必须由数据结构本身明确规定。四、删除操作BST 中最值得认真理解的操作不是插入也不是查找而是删除。因为删除之后不能只是把节点从内存中释放掉还必须保证剩余节点继续满足左 根 右的搜索树性质。假设待删除节点记为cur按照孩子情况可以分成四种表面场景1. 没有左孩子也没有右孩子 2. 没有左孩子但有右孩子 3. 有左孩子但没有右孩子 4. 左右孩子都存在其中叶子节点其实可以合并进只有一侧子树的处理逻辑。因此代码层面通常最终归纳成三类左为空 右为空 左右都不为空左子树为空例如8 \ 10 \ 14删除10。10没有左子树10 \ 14所以可以直接让10的父节点8指向10 的右子树变成8 \ 14本质上就是父节点 ↓ 跳过待删除节点 ↓ 直接连接其唯一子树如果待删除的节点本身就是根节点则_root cur-_right;即可。右子树为空这个逻辑完全对称。例如8 / 3 / 1删除38 / 1本质上父节点 ↓ 直接连接 cur 的左子树左右子树都存在这是删除中真正的难点。假设要删除8 / \ 3 10 / \ \ 1 6 14直接把8删掉是不行的。因为左边整棵子树 右边整棵子树接下来应该挂到哪里这时候通常采用替换法。可以从右子树中找到最小节点作为当前节点的替代者。或者从左子树找到最大节点也可以。为什么右子树最小节点适合替换例如8 / \ 3 12 / \ 10 14要删除8。右子树最小值就是10将8 → 10以后10 / \ 3 12 \ 14仍然满足左边 10 右边因为这个节点本来就是右子树中最小的那个元素。同理左子树最大节点也可以作为替代者。完整实现templateclass K bool BSTreeK::Erase(const K key) { Node* parent nullptr; Node* cur _root; // 先找到待删除节点 while (cur ! nullptr) { if (key cur-_key) { parent cur; cur cur-_left; } else if (key cur-_key) { parent cur; cur cur-_right; } else { break; } } if (cur nullptr) { return false; } // 情况1左子树为空 if (cur-_left nullptr) { if (parent nullptr) { _root cur-_right; } else if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } delete cur; return true; } // 情况2右子树为空 if (cur-_right nullptr) { if (parent nullptr) { _root cur-_left; } else if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } delete cur; return true; } // 情况3左右子树都存在 Node* successorParent cur; Node* successor cur-_right; // 找右子树最小节点 while (successor-_left ! nullptr) { successorParent successor; successor successor-_left; } // 用后继节点的key覆盖待删除节点 cur-_key successor-_key; // 删除原来的后继节点 if (successorParent-_left successor) { successorParent-_left successor-_right; } else { // successor 就是 cur-_right successorParent-_right successor-_right; } delete successor; return true; }这段删除代码最值得理解的不是每一行怎么背而是三个思想没有左孩子 ↓ 右孩子顶上去 没有右孩子 ↓ 左孩子顶上去 左右孩子都有 ↓ 找前驱/后继替换 ↓ 再删除替代节点只要把这三条逻辑真正搞懂删除代码就不需要死记。测试 BST可以构造int values[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };依次插入BSTreeint bst; for (int value : values) { bst.Insert(value); }中序遍历bst.InOrder();应该得到1 3 4 6 7 8 10 13 14再测试cout bst.Find(6) endl; cout bst.Find(9) endl;分别得到true false删除bst.Erase(1); // 叶子节点 bst.Erase(14); // 单孩子 bst.Erase(3); // 双孩子每删除一次再进行中序遍历如果结果始终保持有序就说明删除以后 BST 的基本性质仍然成立。五、Key/Value 型 BST前面的 BST 只保存Key它适合解决某个数据存在吗例如这个车牌是否登记 这个单词是否在词库 这个ID是否存在但很多实际问题需要保存的是Key 与Key对应的数据例如英文单词 → 中文释义 车牌号 → 入场时间 商品编号 → 商品信息 单词 → 出现次数这时候就需要Key/Value 型二叉搜索树。节点结构templateclass K, class V struct BSTNode { K _key; V _value; BSTNodeK, V* _left; BSTNodeK, V* _right; BSTNode(const K key, const V value) : _key(key) , _value(value) , _left(nullptr) , _right(nullptr) {} };和 Key 型相比只是多出V _value;但搜索树的排序依据仍然是_key而不是_value也就是说Key 负责定位 Value 负责保存与 Key 关联的数据为什么 Find 要返回节点指针Key 型只关心存在 还是 不存在所以返回bool已经够用了。但是 Key/Value 型通常还希望找到 Key ↓ 读取 Value ↓ 甚至修改 Value所以bool Find(const K key);已经不够方便。更适合Node* Find(const K key);例如templateclass K, class V BSTNodeK, V* BSTreeK, V::Find(const K key) { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { cur cur-_left; } else if (key cur-_key) { cur cur-_right; } else { return cur; } } return nullptr; }于是auto ret tree.Find(apple); if (ret ! nullptr) { ret-_value; }就可以直接修改 Value。这也是Key型 Find和Key/Value型 Find设计上的重要区别。插入插入时需要同时提供key value例如bool Insert(const K key, const V value);核心搜索逻辑仍然只比较 Keytemplateclass K, class V bool BSTreeK, V::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 ! nullptr) { if (key cur-_key) { parent cur; cur cur-_left; } else if (key cur-_key) { parent cur; cur cur-_right; } else { return false; } } Node* newNode new Node(key, value); if (key parent-_key) { parent-_left newNode; } else { parent-_right newNode; } return true; }深拷贝树中保存的是大量new Node(...)动态申请出来的节点。因此如果直接依赖编译器生成的浅拷贝BSTreeK, V t2 t1;两个对象可能只是复制_root这个指针。结果就会变成t1._root ──┐ ↓ 同一棵树 ↑ t2._root ──┘最后两个对象析构第一次 delete ↓ 节点释放 第二次 delete ↓ 重复释放显然非常危险。所以需要深拷贝整棵树。可以递归实现Node* Copy(Node* root) { if (root nullptr) { return nullptr; } Node* newRoot new Node(root-_key, root-_value); newRoot-_left Copy(root-_left); newRoot-_right Copy(root-_right); return newRoot; }这个过程非常符合树的递归结构复制根 ↓ 递归复制左子树 ↓ 递归复制右子树于是拷贝构造BSTree(const BSTree other) { _root Copy(other._root); }赋值可以使用 copy-and-swapBSTree operator(BSTree other) { std::swap(_root, other._root); return *this; }这样other先通过拷贝构造得到一棵独立的新树再交换根指针。函数结束时other析构并自动释放原来属于当前对象的旧树。这种写法比手动先释放自己 再复制 再处理自赋值更加简洁也具有较好的异常安全性。Key/Value 删除时的一个细节Key/Value 型删除的结构调整和 Key 型一样。但是如果双孩子节点使用后继节点替换只复制 Key是不够的。因为一个节点表示的是Key ↔ Value完整映射关系。所以应该同步cur-_key successor-_key; cur-_value successor-_value;否则就可能出现新的 Key 旧的 Value错配。这是实现 Key/Value BST 时非常容易忽略的细节。六、典型应用BST 的核心能力可以概括成动态 有序 按 Key 查找而 Key 型和 Key/Value 型解决的问题并不完全一样。Key 型判断“有没有”例如小区车库系统。我们只关心车牌是否在白名单可以把所有允许进入的车牌作为 Key赣A12345 赣A88888 赣A66666插入 BST。车辆到达时扫描车牌 ↓ Find(车牌) ↓ 存在 → 放行 不存在 → 拒绝如果业主车辆发生变化Insert() Erase()就可以动态更新。另一个典型场景是拼写检查。将合法词库中的单词作为 Keyapple binary computer search tree文章中每出现一个单词就dict.Find(word);如果不存在标记为可能的拼写错误同时词库还可以动态加入新词 删除废弃词Key/Value建立映射最直观的就是中英词典。例如BSTreestring, string dict; dict.Insert(apple, 苹果); dict.Insert(tree, 树); dict.Insert(search, 查找); dict.Insert(binary, 二进制);查找auto ret dict.Find(search); if (ret ! nullptr) { cout ret-_value endl; }得到查找如果需要修改释义ret-_value 搜索 / 查找;即可。而中序遍历又会天然按照Key的大小顺序输出。单词计数再来看一个很典型的统计问题string words[] { apple, banana, apple, orange, apple, banana };希望得到apple → 3 banana → 2 orange → 1可以建立BSTreestring, int countTree;遍历每个单词for (const auto word : words) { auto ret countTree.Find(word); if (ret nullptr) { countTree.Insert(word, 1); } else { ret-_value; } }逻辑非常自然第一次遇见 ↓ Insert(word, 1) 以前出现过 ↓ Find ↓ value最后进行中序遍历既得到统计结果 又天然按照单词顺序排列Key/Value 结构还适合停车场计时收费。可以定义Key 车牌号 Value 入场时间车辆入场Insert(车牌, 当前时间)车辆离场Find(车牌) ↓ 取得入场时间 ↓ 计算停车时长 ↓ 计算费用 ↓ Erase(车牌)从这个例子也可以看出Key/Value 搜索树不只是“查找某个东西存不存在”还可以维护某个 Key 当前对应的状态。七、BST 的缺陷到这里 BST 看起来似乎已经非常优秀查找快 插入快 删除快 还能保持有序但它有一个致命问题树形完全取决于数据插入顺序。例如4 2 6 1 3 5 7得到4 / \ 2 6 / \ / \ 1 3 5 7非常漂亮。但如果变成1 2 3 4 5 6 7得到1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7搜索树直接退化成链表。此时原本期待的O(logN)就会退化到O(N)所以普通 BST 最大的问题并不是查找算法不够聪明。而是它没有能力主动控制自己的高度。这也自然引出了平衡二叉搜索树AVL 树AVL 树是一种对平衡要求比较严格的搜索树。它要求任意节点左子树高度 和 右子树高度不能相差太大典型约束是平衡因子绝对值不超过1。当插入或删除破坏平衡后会通过旋转重新调整结构。优势是树高控制严格 查找性能稳定代价则是插入删除时 可能需要较频繁调整红黑树红黑树也是平衡搜索树但它不像 AVL 那样追求严格高度平衡而是通过节点颜色 一组颜色规则 旋转与变色保证树不会严重失衡。因此它追求的是查询、插入和删除之间更加均衡的综合性能。这也是工程实现中经常采用红黑树的重要原因。和 STL 的关系我们前面自己实现的Key 型 BST可以帮助理解set / multiset这一类只围绕 Key 组织数据的容器。而Key/Value 型 BST则和map / multimap的设计思想非常接近。其中set map要求 Key 唯一。而multiset multimap允许出现重复 Key。这些有序关联容器的迭代顺序也是按 Key 有序从学习思路上看可以把它们串成普通 BST ↓ 理解有序搜索树 ↓ 平衡搜索树 ↓ 红黑树 ↓ set / map 等有序关联容器需要稍微严谨一点的是C 标准规定的是这些容器的行为、复杂度和有序语义并没有强制所有标准库必须使用某一种具体树结构主流实现通常采用红黑树一类的平衡搜索树。这样理解会比单纯记住map 红黑树更加准确。总结二叉搜索树真正重要的地方并不是学会写几个if (key cur-_key)而是理解它是如何利用“有序”改变普通二叉树的。整条逻辑可以串成普通二叉树 ↓ 增加大小关系约束 ↓ 二叉搜索树 BST ↓ 左 根 右 ↓ 中序遍历天然有序 ↓ 按大小关系缩小搜索范围 ↓ Insert / Find / Erase ↓ Key 型 解决“是否存在” ↓ Key/Value 型 解决“映射关系” ↓ 普通 BST 可能退化 ↓ AVL / 红黑树 ↓ set / map 等有序关联容器如果只记三个最核心的点我觉得应该是第一 左子树 根 右子树 第二 中序遍历天然有序 第三 增删查复杂度本质取决于树高 h尤其是第三点。普通 BST 真正的性能公式其实可以写成Insert Find Erase ↓ O(h)如果h ≈ logN它非常高效。如果h ≈ N它就退化成接近链表。所以后续学习 AVL 树和红黑树时真正要解决的问题并不是推翻 BST而是想办法维持 BST 的有序性质同时控制树的高度。理解了这一点再继续学习平衡树会发现 AVL 和红黑树并不是突然冒出来的新结构而是在普通二叉搜索树之上对“平衡性”这一缺陷进行进一步修正。