1. 从一条查询开始为什么非要“二叉搜索树”拿到“C 二叉搜索树”这个题目我的第一反应不是节点、指针、递归这些语法细节而是一个很朴素的问题在 100 万个数字里找 1 个数怎么找最快答案是排序后二分查找。可问题来了——排序后的数组插入一个新数代价是 O(n)因为它要挪动后面所有元素。实际开发中数据是动态变化的今天删一个、明天加一批你怎么维持整个容器始终有序二叉搜索树BST就是用来解决这个问题的。它本质上是一种“动态排序数组”的替代方案用一棵树存储元素使得任意时刻、任意元素的查找、插入、删除在平均情况下都只要 O(log n)。注意我的用词是“平均情况”因为普通 BST 最坏会退化成链表这件事我们后面会花一整个章节去说。这篇文章适合谁读如果你正在学 C 的数据结构或者你已经会写链表、栈、队列想往树这个维度上走一步那这篇就是为你准备的。我会讲清楚 BST 的核心逻辑、完整 C 实现、删除节点的难点拆解以及工程上怎么避免“退化”这口大锅。不需要你有多深的算法底子只要你写过 C 的类、会递归就能看懂。2. 一棵树的骨架节点设计与数据结构选型2.1 节点建得越简单后面越少翻车BST 的物理存储形态是链式结构不是数组。每个节点保存三样东西一个关键字key、一个左孩子指针、一个右孩子指针。在 C 里写出来就是这样template typename Key struct BSTreeNode { Key key; BSTreeNode* left; BSTreeNode* right; explicit BSTreeNode(const Key k) : key(k), left(nullptr), right(nullptr) {} };这里我把 key 的类型定义成模板参数而不是硬编码成 int是因为实际项目中你很可能需要存的是字符串、ID 结构体、甚至某种自定义对象。把模板用上树的意义就不只局限于整数的排序了。有些人会问要不要加 parent 指针我的建议是——初学者阶段不要加。parent 指针确实能让删除操作写得顺手一些但它会让插入和删除的代码里到处都要维护父节点关系调试的时候指针满天飞容易把自己绕晕。文章后面我会给出一个完全不需要 parent 指针的递归删除方案。工程上如果确实需要 parent等第一个版本跑通了、测试过了再考虑加也不迟。注意C 里节点析构链的递归删除很容易爆栈如果树特别深析构函数就要用后序遍历甚至工程上会转而使用迭代栈。这个点我们留到第 5 章再展开。2.2 为什么链式存储天生适合“动态集合”一个成熟的二叉搜索树类对外应该暴露哪些操作我把最核心的接口列在这里操作C 接口描述平均时间复杂度插入void insert(const Key k)O(log n)删除bool erase(const Key k)O(log n)查找bool contains(const Key k)O(log n)最小值Key minKey()O(log n)最大值Key maxKey()O(log n)中序遍历std::vectorKey inorderKeys()O(n)数组排序虽然查询是 O(log n)但动态插入删除是 O(n)。哈希表插入删除是 O(1)可哈希表无法输出有序序列。BST 能被广泛使用就在于它在一个结构上同时兼顾了三个能力查找高效、修改高效、而且能按顺序输出全部元素。你要做排行榜、订单按时间查询、范围统计BST 这种有序动态集合是正好契合的。2.3 递归和迭代怎么选写树最自然的是递归因为树本身就是递归定义的结构一棵树由根节点和左右两棵子树构成。但 C 的递归调用对栈有开销极端情况下一棵深度为 10 万的树递归函数可能把系统栈打爆。我的做法是查找、插入、删除先用递归写清楚逻辑保证正确性。等代码跑通后如果测试表明调用栈压力大再把【查找】改成迭代版本因为查找的迭代版本最简单不会引入太多复杂性。中序遍历的迭代版本要用显式栈模拟这是最后才优化的目标平时不折腾。其实很多项目的真实性能瓶颈不在树的这几个操作上而在 IO 和业务逻辑。过度优化树操作的递归改成迭代属于比较经典的“过早优化”行为。所以先写清楚再考虑快不快。3. 插入的解剖把“约束”玩明白3.1 BST 的核心不变量左边小右边大插入操作的逻辑非常朴素从根节点出发如果要插入的 key 比当前节点小就往左走比当前节点大就往右走遇到空位就放在那里。这个规则你可以在脑子里想成“排队找座位”数字越大靠右坐越小越往左每个新来的都在叶子位置坐下。但这里面的关键问题是这个规则居然让整棵树一直保持有序——任意节点的左子树所有值都小于它右子树所有值都大于它。这个性质就叫“BST 不变量invariant”。只要每次插入都严格维护这个性质整棵树就是一颗“活的排序数组”。我写过一版把 key 相同的节点视为重复值的插入版本也在别的项目里见过允许重复的 multiset 版本。它们有细微差别如果允许重复就有“重复值放左边还是右边”的麻烦。实际开发里我强烈建议你明确自己的语义把 BST 当 set 用重复值直接放弃插入把它当 multiset 用就必须要考虑重复节点的计数问题。文章这里我们先实现一个“重复值视为已存在”的版本语义最干净。3.2 插入代码与递归回溯template typename Key BSTreeNodeKey* insertNode(BSTreeNodeKey* node, const Key key, bool inserted) { if (node nullptr) { inserted true; return new BSTreeNodeKey(key); } if (key node-key) { node-left insertNode(node-left, key, inserted); } else if (key node-key) { node-right insertNode(node-right, key, inserted); } else { inserted false; // 已存在 } return node; }外面再包一层公开接口template typename Key class BSTree { public: bool insert(const Key key) { bool inserted false; root_ insertNode(root_, key, inserted); return inserted; } private: BSTreeNodeKey* root_ nullptr; };有两点我想提醒你都是从实操里踩出来的第一这里返回的是BSTreeNodeKey*不是void。很多人第一次写递归插入会这样写void insertNode(BSTreeNodeKey* node, const Key key);然后在递归调用里改node-left结果发现改动根本没生效。原因很典型C 默认传值拷贝你在函数内部把指针变量本身改了外面的指针一点变化都感知不到。正确的做法就是要返回新的子树根节点用返回值把新节点“传”回上一层。想要避免这个坑你甚至可以把参数写成指针的引用BSTreeNodeKey* node。第二插入虽然是“递归往深处走”但在返回的路上要逐层把当前的 node 传回去。这行代码相当于在做一件事让父节点的 left 或 right 指针始终指向这层递归返回后的根。这么写的优点是无论哪个子树被修改父节点都能同步拿到最新指针。4. 查找与遍历让树里的每个元素“看得见”4.1 查找的两种写法迭代优先查找不需要改变树结构所以逻辑尤其简单从根出发key 比当前小往左比当前大往右相等就命中走到空就返回 false。template typename Key bool contains(const Key key) const { BSTreeNodeKey* cur root_; while (cur) { if (key cur-key) return true; if (key cur-key) cur cur-left; else cur cur-right; } return false; }这里用迭代没有递归原因很简单——没有回溯需求不需要利用调用栈写一个 while 循环就够了。这段逻辑你也可以理解成“二分查找的链表版”只不过中间元素的导航从数组下标换成了左右指针。在实际业务中我经常需要同时查到“这个值存不存在”以及“如果不存在离它最近的小值是什么”有时候还会想要“比它大的第一个元素是什么”。这些都是 BST 可以支持的高阶查询不过你需要额外记录路径或维护辅助信息。我们在第 7 章会简单点名这类扩展但这一篇先不展开。4.2 中序遍历为什么就是“排好序的输出”二叉树有三种经典遍历前序、中序、后序。BST 最特别的是中序遍历因为中序遍历的顺序是“左子树 → 根 → 右子树”这个顺序天然符合 BST 的约束左边所有值都比根小右边所有值都比根大所以输出恰好就是升序序列。50 / \ 30 70 / \ \ 20 40 80中序遍历输出20, 30, 40, 50, 70, 80。你把它看作是“把树压平”的过程就很有画面感。下面是实现template typename Key void inorder(BSTreeNodeKey* node, std::vectorKey out) const { if (!node) return; inorder(node-left, out); out.push_back(node-key); inorder(node-right, out); }用这个函数你可以一行代码拿到一个排好序的 vector。工程里我经常把它当成“把树导出给外部系统”的通道。比如某个模块需要把 BST 里的所有值按序发给下游我就会构造这个 vector 再统一发出去。比起自己在业务代码里写递归这种做法更容易测试也更容易和其他系统对接。5. 删除BST 里最需要冷静面对的操作5.1 三种情形先看懂再动手删除是 BST 里最复杂的操作。复杂不在于代码长而在于你要分三种情况处理要删除的节点是叶子直接删除令父节点指向空。要删除的节点只有一个孩子让孩子顶替它原来的位置。要删除的节点有两个孩子这是最棘手的情况——你不能直接删掉它因为两个子树都会变成孤儿解决办法是找一个“替身”节点把替身的值复制到当前节点然后删掉替身。第三种情况的经典替身有两种选法左子树中的最大值或者右子树中的最小值。我习惯选右子树的最小值因为这样替身一定最多只有一个右孩子删除替身的代码就退化成了情况 1 或 2难度骤降。5.2 递归删除完整实现template typename Key BSTreeNodeKey* eraseNode(BSTreeNodeKey* node, const Key key, bool erased) { if (node nullptr) { erased false; return nullptr; } if (key node-key) { node-left eraseNode(node-left, key, erased); } else if (key node-key) { node-right eraseNode(node-right, key, erased); } else { erased true; // 情况 1 和 2 合并处理有一个孩子为空返回另一个孩子即可 if (node-left nullptr) { BSTreeNodeKey* rightChild node-right; delete node; return rightChild; } if (node-right nullptr) { BSTreeNodeKey* leftChild node-left; delete node; return leftChild; } // 情况 3找右子树的最小值作为替身 BSTreeNodeKey* successor node-right; while (successor-left) { successor successor-left; } node-key successor-key; node-right eraseNode(node-right, successor-key, erased); } return node; }最后对外接口bool erase(const Key key) { bool erased false; root_ eraseNode(root_, key, erased); return erased; }这段代码比较巧妙的点在于我没有单独写“找最小值的函数再删两步”而是把替身的值复制到当前节点后递归到右子树去删除那个替身。这个过程相当于把“难删的节点”转换成了“删除一个最多只有一个孩子的节点”复用相同的递归删除逻辑代码很简洁。5.3 删除操作的两个实战提醒第一个提醒删除前必须先把孩子指针保存好。上面代码在delete node之前先把node-right或node-left存到了一个局部变量里。这个顺序一旦写反就是经典的 use-after-free 崩溃。第二个提醒如果 Key 类型是自定义对象它的拷贝赋值成本可能很高。上面用node-key successor-key做的是整对象赋值如果 Key 里面有 string、vector代价可能不小。工程上更精细的做法是移动语义node-key std::move(successor-key);不过移动后 successor 的内容会变成悬空状态删除它的时候要注意它的析构是否安全。一般情况下对内置类型或者短字符串来说直接赋值就够用不用为了优化把代码搞得复杂。6. 构建与析构被很多人忽略的隐患6.1 构造与析构的正确形态BST 的默认构造很简单根指针初始化为 nullptr。但析构就有讲究了。如果你直接delete root_那么只有根节点被释放所有子树节点全部泄漏。正确做法是递归释放所有节点也就是后序遍历。template typename Key void destroy(BSTreeNodeKey* node) { if (!node) return; destroy(node-left); destroy(node-right); delete node; } ~BSTree() { destroy(root_); }这个递归析构看起来清晰但如果树的深度到了几万层递归调用深度太深可能会触发栈溢出。我在某个数据量较大的项目里亲身踩过这个坑插入几万个有序数据后析构时直接栈溢出。后来我改成迭代版本的析构用栈模拟后序。不过这里有个经验之谈如果树是平衡的深度只有几十层递归析构毫无压力真正有压力的是树已经退化成长链表的时候。你如果提前做了 AVL 或红黑树那种平衡化递归析构基本安全。但如果你的树就是裸 BST而且数据点是按序插入的那迭代析构就会是更有必要的选择。迭代析构的思路是用一个栈保存节点把根放入然后循环弹出节点把左右孩子入栈再删除自己。这样就是广度优先式的释放不依赖递归深度。代码写成这样template typename Key void destroyIterative(BSTreeNodeKey* root) { if (!root) return; std::vectorBSTreeNodeKey* stack; stack.push_back(root); while (!stack.empty()) { BSTreeNodeKey* cur stack.back(); stack.pop_back(); if (cur-left) stack.push_back(cur-left); if (cur-right) stack.push_back(cur-right); delete cur; } }注意这个迭代版本的释放顺序是先释放根、再释放子节点和递归后序的严格顺序不同。但 BST 节点之间其实没有“必须子先死后父死”的硬性依赖因为节点的生命周期完全由整棵树的所有权管理子节点在自己被释放前并不依赖父亲的意义。所以广度优先一样安全这点和递归析构看起来不同实际效果一致。6.2 拷贝控制别让浅拷贝把你坑到崩溃还有一个很隐蔽的大坑C 的默认拷贝构造函数是浅拷贝。如果你写BSTreeint b2 b1;那 b2 的 root_ 会和 b1 的 root_ 指向同一棵树的根节点。等这两个对象都析构时同一个节点会被 delete 两次直接 double free 崩溃。解决方法是把手动写拷贝构造和拷贝赋值做一棵树的深拷贝。递归实现如下template typename Key BSTreeNodeKey* clone(BSTreeNodeKey* node) { if (!node) return nullptr; BSTreeNodeKey* newNode new BSTreeNodeKey(node-key); newNode-left clone(node-left); newNode-right clone(node-right); return newNode; }如果业务上根本不需要复制 BST 对象最省事的方式是删除拷贝BSTree(const BSTree) delete; BSTree operator(const BSTree) delete;在工程里很多容器对象根本不应该被复制把它禁掉比实现一个几乎不用的深拷贝更严谨。你可以在项目里按自己的需求选择要么完整支持拷贝要么彻底禁止拷贝千万别默认允许浅拷贝。7. 为什么普通 BST 会退化以及“平衡化”的意义7.1 最坏情况的诞生有序插入是退化的元凶普通 BST 的最大弱点如果数据是按顺序插入的树会变成一条只有右孩子或者左孩子的链。比如依次插入 1, 2, 3, 4, 5BST 会变成这样1 \ 2 \ 3 \ 4 \ 5此时查找 5 需要走 5 层时间复杂度退化到 O(n)。如果插入 10 万个有序元素查找复杂度就不是 log 而是线性了性能直接崩到和链表一样。为什么有序插入会退化本质原因是 BST 的插入规则只保证局部的大小关系却不保证树形结构的平衡性。你一直往右侧插入树就只会往右长完全没有机会长左边。7.2 平衡树的思路旋转与局部重构解决退化的经典方案是让树在每次插入、删除后尽量保持左右子树高度接近。这个“接近”的标准不同就产生了不同的平衡树AVL 树严格要求任意节点的左右子树高度差绝对值不超过 1查询性能最稳定但插入删除后的旋转调整较频繁。红黑树放宽约束保证最长路径不超过最短路径的两倍插入删除旋转次数更少C 标准库的 std::map 和 std::set 就是用它实现的。我不会在这一篇里手写红黑树因为那是一个很庞大、很容易出错的工程但我想强调一个关键思维你在自己实现 BST 的时候最好从一开始就预留“旋转”的接口思路。所谓旋转就是把某个节点“提上去”让它的孩子“降下来”局部调整而不破坏 BST 不变量。后面的 AVL 或者红黑树都是在这个旋转基础上面叠颜色和高度信息。如果不想自己造轮子直接用 STL#include set std::setint s; auto [iter, inserted] s.insert(42); if (s.find(42) ! s.end()) { /* 找到了 */ }标准库的 set 底层就是红黑树它才是生产环境里真正被广泛使用的“二叉搜索树”实体。我建议你在学习阶段一定手写一遍裸 BST但到了工程落地阶段如果没有特殊原因优先使用 std::set 或 std::multiset。这个取舍是我自己反复折腾后得到的体会。7.3 手写 BST 仍然值得的原因那你可能会问既然 std::set 这么好用为什么还要手写 BST我的回答是因为“手写一次”和“生产使用”的目标不一样。手写裸 BST 会逼迫你理解递归、理解指针所有权、理解树的约束与旋转。一旦这些底层概念在心里扎根你再去读红黑树代码、去调 set 的迭代器、去做区间查询都会快得多。我在带项目的时候看到过不少只会调 STL 的同学一旦要自定义比较器、要实现按时间窗口遍历节点立刻就卡壳。原因不是 STL 不好而是他根本不知道树内部是怎么组织的。所以这一章不是劝你别手写恰恰是劝你亲手写但写完要知道它的局限。Know your data structure比“会用 API”重要得多。8. 工程实战把 BST 用在一个真实场景里8.1 场景设定订单按金额区间统计假设你在开发一个订单系统需要支持这样的查询按照订单金额排序实时查“金额在 100 到 500 之间的订单有多少个”。订单数量很大而且不断有新订单进来。这种情况下如果每次查询都把订单全量遍历一遍那数据量上来以后卡顿是必然的。更好的方案是维护一棵以订单金额为 key 的 BST每个节点再额外存储一个subtreeSize字段表示这棵子树有多少个节点。有了这个字段就能在 O(log n) 时间内回答区间计数问题。这里的关键优化是“分而治之”count(≤ X)可以通过递归判断左右子树来统计而count(L ≤ 金额 ≤ R)就等于count(≤ R) - count( L)。只要每个节点维护子树大小这个计算成本就非常低。这种“扩充节点字段”的思路是 BST 最强大的工程价值所在。你不只可以存大小还可以存子树最大值、最小值、区间总和等本质上是把一棵树变成一个有序的“前端汇总节点”。我知道这个案例可能超出了“一课一练”的范畴但它能帮助你理解为什么 BST 不只是教学玩具。8.2 节点字段扩展以子树大小为例如果你要支持“查第 k 小的元素”这种 top-k 类需求你就可以在节点里加一个int size字段。插入和删除时需要从递归回溯路径上更新 sizenode-size 1 (node-left ? node-left-size : 0) (node-right ? node-right-size : 0);这个更新的代码要放的位置是递归函数的 return node 之前。这点顺序很容易错如果你在递归调用前更新 size那个时候子树还没变算出来的 size 是旧的。正确逻辑是先让子树的递归调用完成并返回子树内部节点的 size 已经更新完然后再基于新的左右子树来更新当前节点。这其实也是一个“自底向上”的经典思维。8.3 选型感言裸 BST、set 还是平衡树场景推荐选型理由学习、笔试、理解结构手写裸 BST无增值依赖思维直观生产环境需要有序集合std::set红黑树保证最坏 O(log n)需要区间计数、排名查询手写加权平衡树std::set 不提供子树 size需要大量自定义遍历策略手写 BST / AVLSTL 的迭代器抽象较固定你会发现STL 的 set 虽然是红黑树但它不暴露子树信息给你。你真想做“第 k 小”或“区间计数”就需要在 STL 之上用 pbds部分平衡树扩展或者手写。这就解释了为什么很多竞赛选手和基础设施工程师会选择手写带 size 的平衡树——不是因为 STL 不好而是因为它的封装恰好不满足这一类高级查询需求。9. 避坑笔记我写 BST 时踩过的六个大地雷第一个坑指针传值改动不生效。前面已经提过如果你想把node在函数里改成新节点参数必须写成指针引用或者用返回值。最直观的检验方式插入后调用查找如果查不到自己刚刚插入的值十有八九是这个坑。解决方法是把插入函数的参数改成BSTreeNodeKey* node或者统一用返回值。我用“返回值传递新子树”的方式因为它也能兼容“删除后子树根变化”的场景。第二个坑递归删除节点时 delete 顺序出错。很多人会写成先 delete node然后才 return node-right。这个时候 node 已经被释放访问 node-right 就是悬空指针。记得先把孩子指针保存下来再删当前节点。同理拷贝构造里也要先 deep clone 再删别把两个对象搞混。第三个坑重复值的处理策略不一致。如果你插入一个已经存在的 key你是直接忽略还是加计数器还是把它插到右边某个位置三种策略在不同业务下都可能合理但你必须在类内部保持唯一语义否则后面写删除就不知道要删哪个节点。从工程角度讲最好在头文件注释里写清楚语义。第四个坑递归栈溢出。这是所有递归树操作的通用隐患。当你插入的数据恰好是有序的树深就变成 O(n)递归插入、析构、遍历都可能爆栈。我在一个较大的数据集上调试时遇到过程序运行到一半直接崩溃用调试器一看栈指针已经越过栈顶边界。这个现象的排查方法很简单打印树高最大深度如果树高接近 n那递归就危险了赶紧考虑平衡化或迭代化。第五个坑默认拷贝带来的 double free。这个问题一开始很难察觉因为它在程序结束时才崩溃。如果你不想实现深拷贝就一定要把拷贝构造/赋值禁掉。如果业务需要就实现深拷贝并在每个成员变量上正确复制左右子树。第六个坑内存泄漏检测不到位。树的每个节点都是堆上分配只要有一条路径上的指针没有正确释放就会造成内存泄漏。在 Visual Studio 下可以用_CrtDumpMemoryLeaks()在 Linux 下可以用 Valgrind 或 ASan。我个人的习惯是写完 BST 的第一时间就用 ASan 跑一轮插入删除的随机测试保证没有 leak再继续往下加功能。这六个坑其实是 C 内存管理基本功在树结构上的集中体现。你调过一轮 BST就相当于把new/delete、指针引用、递归回溯、对象拷贝这些关键概念全部串起来了这也是学 BST 最磨人也最有价值的地方。10. 从 BST 出发还能走多远学完裸 BST接下来的路线通常是这么个顺序先是 AVL 树严格控制高度平衡然后是红黑树引入颜色标记放宽约束但保持 log 复杂度再到 B 树和 B 树把“一个节点存多个 key”的思想应用到磁盘存储和数据库索引里。你会发现数据库的聚簇索引、文件系统的目录索引本质上都脱胎于“有序查找树”这一思路。扩展方向上还有一个很有意思的“treap”——它把 BST 和堆结合通过给每个节点随机的优先级来维持树的形态期望高度是 O(log n)。treap 的代码实现比 AVL 和红黑树都短很多非常适合作为你手写平衡结构的“下一个目标”。如果你对“区间操作”感兴趣还可以学习线段树和树状数组。它们的排序逻辑不是 BST 的“左小右大”而是“区间分段”用来解决范围求和、范围更新等问题。这些树形思想是逐层递进的BST 是你走进这个“树的世界”的第一把钥匙。我个人在实际项目中的体会真正有价值的不在于你能默写多少行树代码而在于遇到一个具体问题时你脑子里能浮现“这是一棵树的形状它可以承担什么职责”。BST 作为最精炼的树形结构它的插入规则、删除策略、遍历方式几乎就是所有高级查找树的最小公共集。把这个最小集吃透再往哪个方向走都不亏。 
长河君 · 2026/10/16 7:50:23 · 阅读 1.2k C++二叉搜索树实战：从插入删除到平衡优化
1. 从一条查询开始为什么非要“二叉搜索树”拿到“C 二叉搜索树”这个题目我的第一反应不是节点、指针、递归这些语法细节而是一个很朴素的问题在 100 万个数字里找 1 个数怎么找最快答案是排序后二分查找。可问题来了——排序后的数组插入一个新数代价是 O(n)因为它要挪动后面所有元素。实际开发中数据是动态变化的今天删一个、明天加一批你怎么维持整个容器始终有序二叉搜索树BST就是用来解决这个问题的。它本质上是一种“动态排序数组”的替代方案用一棵树存储元素使得任意时刻、任意元素的查找、插入、删除在平均情况下都只要 O(log n)。注意我的用词是“平均情况”因为普通 BST 最坏会退化成链表这件事我们后面会花一整个章节去说。这篇文章适合谁读如果你正在学 C 的数据结构或者你已经会写链表、栈、队列想往树这个维度上走一步那这篇就是为你准备的。我会讲清楚 BST 的核心逻辑、完整 C 实现、删除节点的难点拆解以及工程上怎么避免“退化”这口大锅。不需要你有多深的算法底子只要你写过 C 的类、会递归就能看懂。2. 一棵树的骨架节点设计与数据结构选型2.1 节点建得越简单后面越少翻车BST 的物理存储形态是链式结构不是数组。每个节点保存三样东西一个关键字key、一个左孩子指针、一个右孩子指针。在 C 里写出来就是这样template typename Key struct BSTreeNode { Key key; BSTreeNode* left; BSTreeNode* right; explicit BSTreeNode(const Key k) : key(k), left(nullptr), right(nullptr) {} };这里我把 key 的类型定义成模板参数而不是硬编码成 int是因为实际项目中你很可能需要存的是字符串、ID 结构体、甚至某种自定义对象。把模板用上树的意义就不只局限于整数的排序了。有些人会问要不要加 parent 指针我的建议是——初学者阶段不要加。parent 指针确实能让删除操作写得顺手一些但它会让插入和删除的代码里到处都要维护父节点关系调试的时候指针满天飞容易把自己绕晕。文章后面我会给出一个完全不需要 parent 指针的递归删除方案。工程上如果确实需要 parent等第一个版本跑通了、测试过了再考虑加也不迟。注意C 里节点析构链的递归删除很容易爆栈如果树特别深析构函数就要用后序遍历甚至工程上会转而使用迭代栈。这个点我们留到第 5 章再展开。2.2 为什么链式存储天生适合“动态集合”一个成熟的二叉搜索树类对外应该暴露哪些操作我把最核心的接口列在这里操作C 接口描述平均时间复杂度插入void insert(const Key k)O(log n)删除bool erase(const Key k)O(log n)查找bool contains(const Key k)O(log n)最小值Key minKey()O(log n)最大值Key maxKey()O(log n)中序遍历std::vectorKey inorderKeys()O(n)数组排序虽然查询是 O(log n)但动态插入删除是 O(n)。哈希表插入删除是 O(1)可哈希表无法输出有序序列。BST 能被广泛使用就在于它在一个结构上同时兼顾了三个能力查找高效、修改高效、而且能按顺序输出全部元素。你要做排行榜、订单按时间查询、范围统计BST 这种有序动态集合是正好契合的。2.3 递归和迭代怎么选写树最自然的是递归因为树本身就是递归定义的结构一棵树由根节点和左右两棵子树构成。但 C 的递归调用对栈有开销极端情况下一棵深度为 10 万的树递归函数可能把系统栈打爆。我的做法是查找、插入、删除先用递归写清楚逻辑保证正确性。等代码跑通后如果测试表明调用栈压力大再把【查找】改成迭代版本因为查找的迭代版本最简单不会引入太多复杂性。中序遍历的迭代版本要用显式栈模拟这是最后才优化的目标平时不折腾。其实很多项目的真实性能瓶颈不在树的这几个操作上而在 IO 和业务逻辑。过度优化树操作的递归改成迭代属于比较经典的“过早优化”行为。所以先写清楚再考虑快不快。3. 插入的解剖把“约束”玩明白3.1 BST 的核心不变量左边小右边大插入操作的逻辑非常朴素从根节点出发如果要插入的 key 比当前节点小就往左走比当前节点大就往右走遇到空位就放在那里。这个规则你可以在脑子里想成“排队找座位”数字越大靠右坐越小越往左每个新来的都在叶子位置坐下。但这里面的关键问题是这个规则居然让整棵树一直保持有序——任意节点的左子树所有值都小于它右子树所有值都大于它。这个性质就叫“BST 不变量invariant”。只要每次插入都严格维护这个性质整棵树就是一颗“活的排序数组”。我写过一版把 key 相同的节点视为重复值的插入版本也在别的项目里见过允许重复的 multiset 版本。它们有细微差别如果允许重复就有“重复值放左边还是右边”的麻烦。实际开发里我强烈建议你明确自己的语义把 BST 当 set 用重复值直接放弃插入把它当 multiset 用就必须要考虑重复节点的计数问题。文章这里我们先实现一个“重复值视为已存在”的版本语义最干净。3.2 插入代码与递归回溯template typename Key BSTreeNodeKey* insertNode(BSTreeNodeKey* node, const Key key, bool inserted) { if (node nullptr) { inserted true; return new BSTreeNodeKey(key); } if (key node-key) { node-left insertNode(node-left, key, inserted); } else if (key node-key) { node-right insertNode(node-right, key, inserted); } else { inserted false; // 已存在 } return node; }外面再包一层公开接口template typename Key class BSTree { public: bool insert(const Key key) { bool inserted false; root_ insertNode(root_, key, inserted); return inserted; } private: BSTreeNodeKey* root_ nullptr; };有两点我想提醒你都是从实操里踩出来的第一这里返回的是BSTreeNodeKey*不是void。很多人第一次写递归插入会这样写void insertNode(BSTreeNodeKey* node, const Key key);然后在递归调用里改node-left结果发现改动根本没生效。原因很典型C 默认传值拷贝你在函数内部把指针变量本身改了外面的指针一点变化都感知不到。正确的做法就是要返回新的子树根节点用返回值把新节点“传”回上一层。想要避免这个坑你甚至可以把参数写成指针的引用BSTreeNodeKey* node。第二插入虽然是“递归往深处走”但在返回的路上要逐层把当前的 node 传回去。这行代码相当于在做一件事让父节点的 left 或 right 指针始终指向这层递归返回后的根。这么写的优点是无论哪个子树被修改父节点都能同步拿到最新指针。4. 查找与遍历让树里的每个元素“看得见”4.1 查找的两种写法迭代优先查找不需要改变树结构所以逻辑尤其简单从根出发key 比当前小往左比当前大往右相等就命中走到空就返回 false。template typename Key bool contains(const Key key) const { BSTreeNodeKey* cur root_; while (cur) { if (key cur-key) return true; if (key cur-key) cur cur-left; else cur cur-right; } return false; }这里用迭代没有递归原因很简单——没有回溯需求不需要利用调用栈写一个 while 循环就够了。这段逻辑你也可以理解成“二分查找的链表版”只不过中间元素的导航从数组下标换成了左右指针。在实际业务中我经常需要同时查到“这个值存不存在”以及“如果不存在离它最近的小值是什么”有时候还会想要“比它大的第一个元素是什么”。这些都是 BST 可以支持的高阶查询不过你需要额外记录路径或维护辅助信息。我们在第 7 章会简单点名这类扩展但这一篇先不展开。4.2 中序遍历为什么就是“排好序的输出”二叉树有三种经典遍历前序、中序、后序。BST 最特别的是中序遍历因为中序遍历的顺序是“左子树 → 根 → 右子树”这个顺序天然符合 BST 的约束左边所有值都比根小右边所有值都比根大所以输出恰好就是升序序列。50 / \ 30 70 / \ \ 20 40 80中序遍历输出20, 30, 40, 50, 70, 80。你把它看作是“把树压平”的过程就很有画面感。下面是实现template typename Key void inorder(BSTreeNodeKey* node, std::vectorKey out) const { if (!node) return; inorder(node-left, out); out.push_back(node-key); inorder(node-right, out); }用这个函数你可以一行代码拿到一个排好序的 vector。工程里我经常把它当成“把树导出给外部系统”的通道。比如某个模块需要把 BST 里的所有值按序发给下游我就会构造这个 vector 再统一发出去。比起自己在业务代码里写递归这种做法更容易测试也更容易和其他系统对接。5. 删除BST 里最需要冷静面对的操作5.1 三种情形先看懂再动手删除是 BST 里最复杂的操作。复杂不在于代码长而在于你要分三种情况处理要删除的节点是叶子直接删除令父节点指向空。要删除的节点只有一个孩子让孩子顶替它原来的位置。要删除的节点有两个孩子这是最棘手的情况——你不能直接删掉它因为两个子树都会变成孤儿解决办法是找一个“替身”节点把替身的值复制到当前节点然后删掉替身。第三种情况的经典替身有两种选法左子树中的最大值或者右子树中的最小值。我习惯选右子树的最小值因为这样替身一定最多只有一个右孩子删除替身的代码就退化成了情况 1 或 2难度骤降。5.2 递归删除完整实现template typename Key BSTreeNodeKey* eraseNode(BSTreeNodeKey* node, const Key key, bool erased) { if (node nullptr) { erased false; return nullptr; } if (key node-key) { node-left eraseNode(node-left, key, erased); } else if (key node-key) { node-right eraseNode(node-right, key, erased); } else { erased true; // 情况 1 和 2 合并处理有一个孩子为空返回另一个孩子即可 if (node-left nullptr) { BSTreeNodeKey* rightChild node-right; delete node; return rightChild; } if (node-right nullptr) { BSTreeNodeKey* leftChild node-left; delete node; return leftChild; } // 情况 3找右子树的最小值作为替身 BSTreeNodeKey* successor node-right; while (successor-left) { successor successor-left; } node-key successor-key; node-right eraseNode(node-right, successor-key, erased); } return node; }最后对外接口bool erase(const Key key) { bool erased false; root_ eraseNode(root_, key, erased); return erased; }这段代码比较巧妙的点在于我没有单独写“找最小值的函数再删两步”而是把替身的值复制到当前节点后递归到右子树去删除那个替身。这个过程相当于把“难删的节点”转换成了“删除一个最多只有一个孩子的节点”复用相同的递归删除逻辑代码很简洁。5.3 删除操作的两个实战提醒第一个提醒删除前必须先把孩子指针保存好。上面代码在delete node之前先把node-right或node-left存到了一个局部变量里。这个顺序一旦写反就是经典的 use-after-free 崩溃。第二个提醒如果 Key 类型是自定义对象它的拷贝赋值成本可能很高。上面用node-key successor-key做的是整对象赋值如果 Key 里面有 string、vector代价可能不小。工程上更精细的做法是移动语义node-key std::move(successor-key);不过移动后 successor 的内容会变成悬空状态删除它的时候要注意它的析构是否安全。一般情况下对内置类型或者短字符串来说直接赋值就够用不用为了优化把代码搞得复杂。6. 构建与析构被很多人忽略的隐患6.1 构造与析构的正确形态BST 的默认构造很简单根指针初始化为 nullptr。但析构就有讲究了。如果你直接delete root_那么只有根节点被释放所有子树节点全部泄漏。正确做法是递归释放所有节点也就是后序遍历。template typename Key void destroy(BSTreeNodeKey* node) { if (!node) return; destroy(node-left); destroy(node-right); delete node; } ~BSTree() { destroy(root_); }这个递归析构看起来清晰但如果树的深度到了几万层递归调用深度太深可能会触发栈溢出。我在某个数据量较大的项目里亲身踩过这个坑插入几万个有序数据后析构时直接栈溢出。后来我改成迭代版本的析构用栈模拟后序。不过这里有个经验之谈如果树是平衡的深度只有几十层递归析构毫无压力真正有压力的是树已经退化成长链表的时候。你如果提前做了 AVL 或红黑树那种平衡化递归析构基本安全。但如果你的树就是裸 BST而且数据点是按序插入的那迭代析构就会是更有必要的选择。迭代析构的思路是用一个栈保存节点把根放入然后循环弹出节点把左右孩子入栈再删除自己。这样就是广度优先式的释放不依赖递归深度。代码写成这样template typename Key void destroyIterative(BSTreeNodeKey* root) { if (!root) return; std::vectorBSTreeNodeKey* stack; stack.push_back(root); while (!stack.empty()) { BSTreeNodeKey* cur stack.back(); stack.pop_back(); if (cur-left) stack.push_back(cur-left); if (cur-right) stack.push_back(cur-right); delete cur; } }注意这个迭代版本的释放顺序是先释放根、再释放子节点和递归后序的严格顺序不同。但 BST 节点之间其实没有“必须子先死后父死”的硬性依赖因为节点的生命周期完全由整棵树的所有权管理子节点在自己被释放前并不依赖父亲的意义。所以广度优先一样安全这点和递归析构看起来不同实际效果一致。6.2 拷贝控制别让浅拷贝把你坑到崩溃还有一个很隐蔽的大坑C 的默认拷贝构造函数是浅拷贝。如果你写BSTreeint b2 b1;那 b2 的 root_ 会和 b1 的 root_ 指向同一棵树的根节点。等这两个对象都析构时同一个节点会被 delete 两次直接 double free 崩溃。解决方法是把手动写拷贝构造和拷贝赋值做一棵树的深拷贝。递归实现如下template typename Key BSTreeNodeKey* clone(BSTreeNodeKey* node) { if (!node) return nullptr; BSTreeNodeKey* newNode new BSTreeNodeKey(node-key); newNode-left clone(node-left); newNode-right clone(node-right); return newNode; }如果业务上根本不需要复制 BST 对象最省事的方式是删除拷贝BSTree(const BSTree) delete; BSTree operator(const BSTree) delete;在工程里很多容器对象根本不应该被复制把它禁掉比实现一个几乎不用的深拷贝更严谨。你可以在项目里按自己的需求选择要么完整支持拷贝要么彻底禁止拷贝千万别默认允许浅拷贝。7. 为什么普通 BST 会退化以及“平衡化”的意义7.1 最坏情况的诞生有序插入是退化的元凶普通 BST 的最大弱点如果数据是按顺序插入的树会变成一条只有右孩子或者左孩子的链。比如依次插入 1, 2, 3, 4, 5BST 会变成这样1 \ 2 \ 3 \ 4 \ 5此时查找 5 需要走 5 层时间复杂度退化到 O(n)。如果插入 10 万个有序元素查找复杂度就不是 log 而是线性了性能直接崩到和链表一样。为什么有序插入会退化本质原因是 BST 的插入规则只保证局部的大小关系却不保证树形结构的平衡性。你一直往右侧插入树就只会往右长完全没有机会长左边。7.2 平衡树的思路旋转与局部重构解决退化的经典方案是让树在每次插入、删除后尽量保持左右子树高度接近。这个“接近”的标准不同就产生了不同的平衡树AVL 树严格要求任意节点的左右子树高度差绝对值不超过 1查询性能最稳定但插入删除后的旋转调整较频繁。红黑树放宽约束保证最长路径不超过最短路径的两倍插入删除旋转次数更少C 标准库的 std::map 和 std::set 就是用它实现的。我不会在这一篇里手写红黑树因为那是一个很庞大、很容易出错的工程但我想强调一个关键思维你在自己实现 BST 的时候最好从一开始就预留“旋转”的接口思路。所谓旋转就是把某个节点“提上去”让它的孩子“降下来”局部调整而不破坏 BST 不变量。后面的 AVL 或者红黑树都是在这个旋转基础上面叠颜色和高度信息。如果不想自己造轮子直接用 STL#include set std::setint s; auto [iter, inserted] s.insert(42); if (s.find(42) ! s.end()) { /* 找到了 */ }标准库的 set 底层就是红黑树它才是生产环境里真正被广泛使用的“二叉搜索树”实体。我建议你在学习阶段一定手写一遍裸 BST但到了工程落地阶段如果没有特殊原因优先使用 std::set 或 std::multiset。这个取舍是我自己反复折腾后得到的体会。7.3 手写 BST 仍然值得的原因那你可能会问既然 std::set 这么好用为什么还要手写 BST我的回答是因为“手写一次”和“生产使用”的目标不一样。手写裸 BST 会逼迫你理解递归、理解指针所有权、理解树的约束与旋转。一旦这些底层概念在心里扎根你再去读红黑树代码、去调 set 的迭代器、去做区间查询都会快得多。我在带项目的时候看到过不少只会调 STL 的同学一旦要自定义比较器、要实现按时间窗口遍历节点立刻就卡壳。原因不是 STL 不好而是他根本不知道树内部是怎么组织的。所以这一章不是劝你别手写恰恰是劝你亲手写但写完要知道它的局限。Know your data structure比“会用 API”重要得多。8. 工程实战把 BST 用在一个真实场景里8.1 场景设定订单按金额区间统计假设你在开发一个订单系统需要支持这样的查询按照订单金额排序实时查“金额在 100 到 500 之间的订单有多少个”。订单数量很大而且不断有新订单进来。这种情况下如果每次查询都把订单全量遍历一遍那数据量上来以后卡顿是必然的。更好的方案是维护一棵以订单金额为 key 的 BST每个节点再额外存储一个subtreeSize字段表示这棵子树有多少个节点。有了这个字段就能在 O(log n) 时间内回答区间计数问题。这里的关键优化是“分而治之”count(≤ X)可以通过递归判断左右子树来统计而count(L ≤ 金额 ≤ R)就等于count(≤ R) - count( L)。只要每个节点维护子树大小这个计算成本就非常低。这种“扩充节点字段”的思路是 BST 最强大的工程价值所在。你不只可以存大小还可以存子树最大值、最小值、区间总和等本质上是把一棵树变成一个有序的“前端汇总节点”。我知道这个案例可能超出了“一课一练”的范畴但它能帮助你理解为什么 BST 不只是教学玩具。8.2 节点字段扩展以子树大小为例如果你要支持“查第 k 小的元素”这种 top-k 类需求你就可以在节点里加一个int size字段。插入和删除时需要从递归回溯路径上更新 sizenode-size 1 (node-left ? node-left-size : 0) (node-right ? node-right-size : 0);这个更新的代码要放的位置是递归函数的 return node 之前。这点顺序很容易错如果你在递归调用前更新 size那个时候子树还没变算出来的 size 是旧的。正确逻辑是先让子树的递归调用完成并返回子树内部节点的 size 已经更新完然后再基于新的左右子树来更新当前节点。这其实也是一个“自底向上”的经典思维。8.3 选型感言裸 BST、set 还是平衡树场景推荐选型理由学习、笔试、理解结构手写裸 BST无增值依赖思维直观生产环境需要有序集合std::set红黑树保证最坏 O(log n)需要区间计数、排名查询手写加权平衡树std::set 不提供子树 size需要大量自定义遍历策略手写 BST / AVLSTL 的迭代器抽象较固定你会发现STL 的 set 虽然是红黑树但它不暴露子树信息给你。你真想做“第 k 小”或“区间计数”就需要在 STL 之上用 pbds部分平衡树扩展或者手写。这就解释了为什么很多竞赛选手和基础设施工程师会选择手写带 size 的平衡树——不是因为 STL 不好而是因为它的封装恰好不满足这一类高级查询需求。9. 避坑笔记我写 BST 时踩过的六个大地雷第一个坑指针传值改动不生效。前面已经提过如果你想把node在函数里改成新节点参数必须写成指针引用或者用返回值。最直观的检验方式插入后调用查找如果查不到自己刚刚插入的值十有八九是这个坑。解决方法是把插入函数的参数改成BSTreeNodeKey* node或者统一用返回值。我用“返回值传递新子树”的方式因为它也能兼容“删除后子树根变化”的场景。第二个坑递归删除节点时 delete 顺序出错。很多人会写成先 delete node然后才 return node-right。这个时候 node 已经被释放访问 node-right 就是悬空指针。记得先把孩子指针保存下来再删当前节点。同理拷贝构造里也要先 deep clone 再删别把两个对象搞混。第三个坑重复值的处理策略不一致。如果你插入一个已经存在的 key你是直接忽略还是加计数器还是把它插到右边某个位置三种策略在不同业务下都可能合理但你必须在类内部保持唯一语义否则后面写删除就不知道要删哪个节点。从工程角度讲最好在头文件注释里写清楚语义。第四个坑递归栈溢出。这是所有递归树操作的通用隐患。当你插入的数据恰好是有序的树深就变成 O(n)递归插入、析构、遍历都可能爆栈。我在一个较大的数据集上调试时遇到过程序运行到一半直接崩溃用调试器一看栈指针已经越过栈顶边界。这个现象的排查方法很简单打印树高最大深度如果树高接近 n那递归就危险了赶紧考虑平衡化或迭代化。第五个坑默认拷贝带来的 double free。这个问题一开始很难察觉因为它在程序结束时才崩溃。如果你不想实现深拷贝就一定要把拷贝构造/赋值禁掉。如果业务需要就实现深拷贝并在每个成员变量上正确复制左右子树。第六个坑内存泄漏检测不到位。树的每个节点都是堆上分配只要有一条路径上的指针没有正确释放就会造成内存泄漏。在 Visual Studio 下可以用_CrtDumpMemoryLeaks()在 Linux 下可以用 Valgrind 或 ASan。我个人的习惯是写完 BST 的第一时间就用 ASan 跑一轮插入删除的随机测试保证没有 leak再继续往下加功能。这六个坑其实是 C 内存管理基本功在树结构上的集中体现。你调过一轮 BST就相当于把new/delete、指针引用、递归回溯、对象拷贝这些关键概念全部串起来了这也是学 BST 最磨人也最有价值的地方。10. 从 BST 出发还能走多远学完裸 BST接下来的路线通常是这么个顺序先是 AVL 树严格控制高度平衡然后是红黑树引入颜色标记放宽约束但保持 log 复杂度再到 B 树和 B 树把“一个节点存多个 key”的思想应用到磁盘存储和数据库索引里。你会发现数据库的聚簇索引、文件系统的目录索引本质上都脱胎于“有序查找树”这一思路。扩展方向上还有一个很有意思的“treap”——它把 BST 和堆结合通过给每个节点随机的优先级来维持树的形态期望高度是 O(log n)。treap 的代码实现比 AVL 和红黑树都短很多非常适合作为你手写平衡结构的“下一个目标”。如果你对“区间操作”感兴趣还可以学习线段树和树状数组。它们的排序逻辑不是 BST 的“左小右大”而是“区间分段”用来解决范围求和、范围更新等问题。这些树形思想是逐层递进的BST 是你走进这个“树的世界”的第一把钥匙。我个人在实际项目中的体会真正有价值的不在于你能默写多少行树代码而在于遇到一个具体问题时你脑子里能浮现“这是一棵树的形状它可以承担什么职责”。BST 作为最精炼的树形结构它的插入规则、删除策略、遍历方式几乎就是所有高级查找树的最小公共集。把这个最小集吃透再往哪个方向走都不亏。