尧图网页设计 
平时刷题或者写业务代码的时候是不是经常遇到这种场景有一堆动态变化的数据需要快速判断某个值在不在、比它小的有多少、它的前驱后继是谁。哈希表固然能做到 O(1) 查找但数据一多哈希碰撞和扩容就很烦人而且它没法有序遍历。这时候二叉搜索树就是一个非常自然的选择。这篇文章我围绕 C 怎么完整“手撕”一棵二叉搜索树从节点设计、插入、查找、删除到遍历和性能分析全部用文字加示意拆开来讲包含我实际调试中的避坑心得适合刚学完 C 基础、想啃树结构的读者也适合面试前系统过一遍二叉搜索树的同学。1. 二叉搜索树的底层逻辑与典型应用1.1 二叉搜索树的定义与核心性质先给一个严格的直觉定义二叉搜索树是一棵二叉树满足每个节点的左子树里所有值都严格小于当前节点值右子树里所有值都严格大于当前节点值而且左右子树本身也必须满足同样性质。这样说有点干巴换个方式理解。你手里有一本按拼音排序的通讯录要找“张三”你不会从第一页翻起而是会先翻到中间页根据拼音“z”应该靠后这个判断直接把后半本拎出来再继续折半。二叉搜索树就是把这种“折半定位”的逻辑用树形结构组织起来——每个节点都是一次二分判断的分界点左半边全走左边右半边全走右边。示意一下这棵最简单的树50 / \ 30 70 / \ / \ 20 40 60 80根节点是 50左边全小于 50右边全大于 50。到了 30 这个节点它的左边还是小于 30、右边大于 30。这个“左小右大”的结构从根到叶子递归保持一致就是二叉搜索树的核心约束。有一个细节必须拎出来强调是“左子树所有值”都小于根不是“左孩子”小于根。也就是说下面这种结构虽然每个节点都满足“左孩子 自己 右孩子”但它不是合法的二叉搜索树10 / \ 5 15 / \ 3 1212 是 10 的左子树里的节点却比根 10 大。所以做性质校验时不能只检查相邻关系要检查整棵子树的上下界这个我后面在 5.2 节单独讲。1.2 面试高频与工业应用为什么值得手撕说点实在的手撕一棵二叉搜索树最直接的价值有三个。第一STL 里的std::map、std::set底层几乎都是红黑树——红黑树本身就是一棵“带平衡约束的二叉搜索树”。你去看红黑树的插入第一步就是按普通二叉搜索树的方式找到插入位置然后再做颜色调整和旋转。所以二叉搜索树不会写红黑树更是无从谈起。第二手撕这棵树是检验“指针和递归”这两件事掌握程度的最佳试炼场。插入要递归挂节点删除要处理悬空指针析构要递归释放拷贝要深拷贝每一个环节都在考验你对内存生命周期的理解。很多初学者 C 语法学得很顺一到树结构就卡壳根源就是指针操作不够熟。第三面试题里二叉搜索树是常驻嘉宾。“验证一棵树是不是 BST”“恢复一棵被交换节点的 BST”“求第 K 小的元素”“判断一棵树是否平衡”全都是它的变体。树本身没几行代码但能不能快速、无 bug 地把它写出来面试官一看便知你的基本功。2. 手撕前的准备工作节点设计与结构规划2.1 节点数据结构的选择动手写代码前先把节点长什么样定下来。我用的是模板类方便后面存 int、存自定义类型都可以template typename T struct TreeNode { T val; TreeNode* left; TreeNode* right; explicit TreeNode(const T v) : val(v), left(nullptr), right(nullptr) {} };这里有个选型问题值得说。为什么用struct而不是class因为struct成员默认是公有public的在我们自己手写的数据结构里节点内部字段被外部访问不是坏事反而是简化代码的途径。你要是用class还得一个个写public:纯属冗余。构造函数里一定要把left和right初始化为nullptr。这不是偷懒而是防止出现“野指针”状态——你new一个节点出来如果不初始化指针成员它的值是不确定的后面哪怕只是判断if (node-left)都会是未定义行为。养成构造函数内初始化的习惯能帮你省下一大半的空指针崩溃调试时间。关于要不要加parent指针我多说两句。加了parent删除节点时可以用迭代方式做不用递归删除有两个子节点的节点时回溯比较方便但代价是插入和删除时都要额外维护父指针代码量直接翻倍还容易漏更新。面试和大部分教科书实现都不用parent用递归天然携带“父节点信息”简洁得多。所以我建议面试手撕不加parent除非题目明确要求迭代实现再考虑。2.2 类模板设计与成员规划节点定好了再封装一棵树。我的类设计是这样的template typename T class BinarySearchTree { public: BinarySearchTree() : root_(nullptr), size_(0) {} // 禁止拷贝先留个坑后面 7.2 节再补深拷贝 BinarySearchTree(const BinarySearchTree) delete; BinarySearchTree operator(const BinarySearchTree) delete; ~BinarySearchTree(); void insert(const T val); bool contains(const T val) const; void remove(const T val); void inorder() const; size_t size() const { return size_; } bool empty() const { return root_ nullptr; } private: struct TreeNode { T val; TreeNode* left; TreeNode* right; explicit TreeNode(const T v) : val(v), left(nullptr), right(nullptr) {} }; TreeNode* root_; size_t size_; // 辅助函数全部放到 private TreeNode* insertHelper(TreeNode* node, const T val); bool containsHelper(TreeNode* node, const T val) const; TreeNode* removeHelper(TreeNode* node, const T val); void inorderHelper(TreeNode* node) const; void clear(TreeNode* node); };为什么要把插入、删除这类函数放到private再包一层public接口因为递归函数需要把当前节点作为参数传进来直接暴露给调用方没意义而且调用方也拿不到私有节点指针。外部用户只需要bst.insert(5)没必要看到insertHelper(root_, 5)这种细节。这就是典型的“公共接口 私有实现”模式。size_这个成员很多人会漏掉。维护一个节点计数能在 O(1) 时间回答“树里有多少元素”而不是每次遍历统计。插入成功size_删除成功--size_多这一行代码的事但很实用。关于拷贝构造和赋值运算符我先禁用掉了。原因是默认的浅拷贝会让两棵树共享同一批节点任何一颗析构时释放内存另一颗就变成悬空指针用起来就是灾难。如果你确实需要复制一棵树得写深拷贝递归这个我留在 7.2 节给完整实现。3. 核心操作手撕插入与查找3.1 递归插入的正确姿势插入的逻辑和二分查找一个思路从根开始如果待插入值比当前节点小就往左走比它大就往右走直到某一步发现当前位置是空直接new一个节点挂上去。递归版本写起来非常短但真正要理解的是“返回值为什么要接回左孩子/右孩子”template typename T auto BinarySearchTreeT::insertHelper(TreeNode* node, const T val) - TreeNode* { if (node nullptr) { size_; return new TreeNode(val); } if (val node-val) { node-left insertHelper(node-left, val); } else if (val node-val) { node-right insertHelper(node-right, val); } // 相等的情况我们选择忽略不插入重复值 return node; } template typename T void BinarySearchTreeT::insert(const T val) { root_ insertHelper(root_, val); }“接回去”这句话很关键。递归调用insertHelper(node-left, val)返回的是“左子树经过插入之后应该长成的新根”。如果一个节点都没有它返回新节点如果递归找到了合适位置它返回原来的左孩子。不管哪种情况当前节点的left指针都要用返回值更新。如果不接回来新插入的节点就悬空了和整棵树完全断连。重复值怎么处理我这里的策略是直接忽略。如果你想支持重复有两个选择一是节点里加一个计数count二是允许相等的值进右子树。但我要提醒如果选择第二种一定要保证“相等的值永远走右子树”否则你后续删除、查找前驱后继都会出逻辑问题。工程上更常见的是加计数直观而且不影响findMin/findMax的正确性。迭代版插入我也顺手写一下它需要维护一个parent指针记录最后挂载的位置template typename T void BinarySearchTreeT::insert(const T val) { TreeNode* node root_; TreeNode* parent nullptr; while (node ! nullptr) { parent node; if (val node-val) { node node-left; } else if (val node-val) { node node-right; } else { return; // 重复 } } TreeNode* newNode new TreeNode(val); size_; if (parent nullptr) { root_ newNode; } else if (val parent-val) { parent-left newNode; } else { parent-right newNode; } }循环结束的时候node已经为空但它的前驱parent还在所以可以确定新节点要挂在parent的哪一侧。这个版本没有递归调用栈空间是 O(1)缺点就是代码比递归长一点。两种写法都建议自己敲一遍。3.2 查找操作递归与迭代的取舍查找不需要修改任何节点所以逻辑上比插入简单。递归写法template typename T bool BinarySearchTreeT::containsHelper(TreeNode* node, const T val) const { if (node nullptr) return false; if (val node-val) return true; if (val node-val) return containsHelper(node-left, val); return containsHelper(node-right, val); }递归版本可读性很好但我在实际工程和面试答疑里更推荐迭代版本template typename T bool BinarySearchTreeT::contains(const T val) const { TreeNode* node root_; while (node ! nullptr) { if (val node-val) { node node-left; } else if (val node-val) { node node-right; } else { return true; } } return false; }原因很简单递归版本每次调用都要压栈查找一棵深度为 10000 的树就要压 10000 层栈迭代版本用 while 循环扫描过程完全不消耗额外栈空间。二叉搜索树查找本身就是一条“向下的路径”天然能用循环表达没必要递归。面试时你写递归也不会扣分但能说清楚“迭代版本避免了栈溢出和函数调用开销”这是加分项。再顺手实现两个最常用的变体——找最小值和最大值template typename T auto BinarySearchTreeT::findMin(TreeNode* node) const - TreeNode* { while (node ! nullptr node-left ! nullptr) { node node-left; } return node; } template typename T auto BinarySearchTreeT::findMax(TreeNode* node) const - TreeNode* { while (node ! nullptr node-right ! nullptr) { node node-right; } return node; }最小节点就是一路往左走到黑最大节点一路往右走到黑。因为 BST 的性质保证了“最小的值一定在左子树的最左端最大的值一定在右子树的最右端”。这两个函数在删除操作里是核心工具先写出来备用。3.3 查找前驱与后继节点前驱和后继在面试里出现频率不低也是最容易被人忽略的两个函数。定义如下节点x的前驱小于x-val的所有节点里最大的那个。节点x的后继大于x-val的所有节点里最小的那个。求法分两种情况讨论。第一种情况x有左子树/右子树。前驱就是左子树里的最大值后继就是右子树里的最小值直接用上面写的findMax/findMin就能拿到。第二种情况x没有左子树/右子树。这时候要找它的“祖先里的第一个转折点”。以前驱为例如果x没有左子树说明左边已经到底了只能往上走找第一个“从右子树方向上来”的祖先这个祖先就是前驱。后继对称理解。如果节点里没存parent指针从根往下搜就好了template typename T auto BinarySearchTreeT::successor(const T val) const - std::optionalT { TreeNode* cur root_; TreeNode* ans nullptr; while (cur ! nullptr) { if (cur-val val) { ans cur; // 候选后继 cur cur-left; } else { cur cur-right; } } if (ans nullptr) return std::nullopt; return ans-val; }这个迭代的精髓在于每次遇到比val大的节点就先把它记为候选后继然后往左收紧边界遇到比val小的节点就往右走但不用更新候选。最后ans就是比val大的最小节点。用std::optional是 C17 的做法能优雅地表示“不存在后继”的情况。4. 最棘手的一环二叉搜索树的删除4.1 删除节点的三种情况删除是 BST 里最需要细抠的环节坑很多。按被删节点的孩子数量可以分成三种情况情况一叶子节点。直接delete掉让父节点对应的指针置空即可。情况二只有一个子节点。把这个唯一的孩子顶上来替代自己被删的位置。想象一个只有左孩子的节点你只要把左孩子“扶正”BST 性质不会破坏——因为左子树的所有值本来就比自己小而自己又比父节点的某些部分小/大整体顺序依然成立。情况三有两个子节点。最麻烦的一类。不能直接删因为你一旦删掉节点两个子树都悬空了无论把哪个提上来另外一个都没地方挂。解决办法是“移花接木”找一个既比左子树所有值大、又比右子树所有值小的节点来顶替自己。天然满足条件的候选有两个——左子树的最大节点和右子树的最小节点也就是前驱或后继。我们通常选右子树的最小节点后继来顶替。先看代码实现我用的整体框架是递归删除template typename T auto BinarySearchTreeT::removeHelper(TreeNode* node, const T val) - TreeNode* { if (node nullptr) return nullptr; if (val node-val) { node-left removeHelper(node-left, val); } else if (val node-val) { node-right removeHelper(node-right, val); } else { // 找到要删的节点 if (node-left nullptr node-right nullptr) { // 情况一叶子 delete node; --size_; return nullptr; } if (node-left nullptr) { // 情况二只有右孩子 TreeNode* rightChild node-right; delete node; --size_; return rightChild; } if (node-right nullptr) { // 情况二只有左孩子 TreeNode* leftChild node-left; delete node; --size_; return leftChild; } // 情况三两个孩子都在 TreeNode* successorNode findMin(node-right); node-val successorNode-val; node-right removeHelper(node-right, successorNode-val); } return node; }注意这里我处理情况二的方式不是先删再赋值而是先把要保留的孩子保存到临时变量再delete当前节点最后把这个孩子返回给上层由上层完成“接回父节点”。这个顺序很重要写反了就会访问已被释放的内存。4.2 两个子节点场景的经典解法与原理两个子节点的情况多数教材会推荐“把后继的值拷贝到当前节点然后递归删掉右子树里的后继节点”。上代码里就是这样做的。很多人会问一句为什么不直接delete当前节点、把后继节点整个挪上来答案是不划算。如果你想把后继节点“挪”上来需要处理后继节点原本左右子树的重新挂载问题还要处理后继节点的父节点指针复杂度一下就上来了。而“拷贝值 递归删除后继”的方案后继节点必然是右子树的最小节点它最多只有一个右孩子不可能有左孩子因为它是右子树里最小的这就退化成了情况一或情况二的简单删除代码直接复用上面的分支即可。为什么选右子树最小节点而不是左子树最大节点两个都可以选后继是约定俗成的习惯。还有一个细节拷贝值会改变节点本身的存储但树的形状结构只发生微小变化——这个操作本质上是“把删除节点的复杂度降低到删除一个叶子/单孩子节点的复杂度”非常优雅。我在实际调试中还发现一个容易被坑的点递归删除后继时findMin(node-right)找到的后继节点的val与当前节点存在“可能相等”的情况吗如果树里不允许重复值不会相等。但如果你在插入时允许了重复值这里就要特别小心删除逻辑会变得很绕。所以我在 3.1 节强烈建议用计数法处理重复就是为了让删除保持简单。再补充一个极端场景如果右子树就是当前节点的右孩子而且这个右孩子就是最小节点比如5 \ 6 \ 7删除 5 时findMin(node-right)找到的就是 6。拷贝 6 到 5 的位置再递归删除右子树里的 6。因为在右子树里寻找 6 时6 在根的位置它的右孩子是 7所以走“只有右孩子”的分支把 7 接回来。整个过程依然正确但值得手动模拟一遍否则很容易在递归回溯时弄晕。5. 遍历与性质验证5.1 三种深度优先遍历的工程取舍遍历树是高频需求。先看标准递归template typename T void BinarySearchTreeT::preorderHelper(TreeNode* node) const { if (node nullptr) return; std::cout node-val ; // 前序先根 preorderHelper(node-left); preorderHelper(node-right); } template typename T void BinarySearchTreeT::inorderHelper(TreeNode* node) const { if (node nullptr) return; inorderHelper(node-left); std::cout node-val ; // 中序左根右 inorderHelper(node-right); } template typename T void BinarySearchTreeT::postorderHelper(TreeNode* node) const { if (node nullptr) return; postorderHelper(node-left); postorderHelper(node-right); std::cout node-val ; // 后序左右根 }三种遍历的时间复杂度都是 O(n)因为每个节点恰好访问一次空间复杂度都是 O(h)h是树高——递归栈的深度取决于树的形状。工程上常见的问题就是递归深度。如果一棵树退化成链表后面的 6.1 节会讲为什么会退化高度可能达到 n递归一万层轻则栈溢出重则程序直接崩。所以巨深的树要用迭代版本遍历。这里我不展开全部代码但给一个标准模板用显式栈模拟递归。template typename T void BinarySearchTreeT::inorderIterative() const { std::stackTreeNode* st; TreeNode* cur root_; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; // 一路向左 } cur st.top(); st.pop(); std::cout cur-val ; cur cur-right; // 转向右子树 } }这个迭代中序是面试写代码的高频题思路要和“递归压栈”对照着理解递归的本质是系统栈帮我们记录了每个待访问的节点迭代就是自己动手维护这个栈。5.2 用中序遍历校验树的正确性二叉搜索树的中序遍历结果严格递增这是判断一棵树是否合格的黄金法则。为什么会这样因为中序访问顺序是左子树、根、右子树而 BST 的定义保证左子树所有值都小于根、右子树所有值都大于根递归到每个节点都成立整个序列自然就严格递增。利用这一点最简单粗暴的二叉搜索树合法性检查就是跑一遍中序看结果是否严格递增。但如果你只想判断“是不是合法 BST”更高效的写法是带上下界递归template typename T bool BinarySearchTreeT::isValidBSTHelper(TreeNode* node, const T minVal, const T maxVal) const { if (node nullptr) return true; if (node-val minVal || node-val maxVal) return false; return isValidBSTHelper(node-left, minVal, node-val) isValidBSTHelper(node-right, node-val, maxVal); }调用时初始上下界用std::numeric_limitsT::lowest()和max()。这个实现为什么对因为每个节点都被限制在一个开区间里左子树的上界是当前节点值右子树的下界是当前节点值。这样能捕获 1.1 节举的那个“12 藏在 10 的左子树里”的非法结构。一个容易踩的坑如果树的泛型类型是int初始上下界用INT_MIN和INT_MAX是没有问题的但如果存的是long long或者自定义类型直接给“最小/最大”就不合适。更稳妥的做法是加一个std::optionalT或者用指针传上下界为空表示无限制。这个小改动在面试里提出来考官会觉得你考虑问题很周全。5.3 层序遍历与队列配合层序遍历也叫广度优先BFS需要配合队列template typename T void BinarySearchTreeT::levelOrder() const { if (root_ nullptr) return; std::queueTreeNode* q; q.push(root_); while (!q.empty()) { TreeNode* cur q.front(); q.pop(); std::cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }层序遍历的应用场景很广按层打印树结构、统计每层的节点数、序列化和反序列化二叉树、检查完全二叉树等等。比如要算出树的最大宽度就是 BFS 过程中记录每一层的节点数取最大值。如果要求“按层分组输出”可以在while里先记录当前q.size()然后一次性处理完这一层while (!q.empty()) { size_t levelSize q.size(); for (size_t i 0; i levelSize; i) { // 依次取出当前层节点 } // 到这里q 里刚好是下一层所有节点 }这个“先取 size 再处理一层”的技巧在很多题目里都比不分组输出实用得多。6. 性能分析为什么有序输入会把树变成链表6.1 平均复杂度与最坏复杂度二叉搜索树的插入、查找、删除复杂度完全取决于树的高度理想平衡情况下高度是 O(log n)三个操作都是 O(log n)。最坏情况下树退化成一条链高度是 O(n)三个操作全是 O(n)。什么时候退化连续插入有序数据。比如你按 1、2、3、4、5……的顺序插入每个新节点都比当前节点大于是一直往右子树走到底树就长成了这样1 \ 2 \ 3 \ 4这就完全退化成了单链表二叉搜索树的一半优势直接没了。我见过不少初学者用二叉搜索树跑大数据量的程序开始还挺快后来越跑越慢最后发现就是插入顺序太“好”了树已经变成一条直线。平均情况呢如果插入元素的顺序是随机的树的高度大致是 O(log n)这个有概率分析的结论实践中基本符合直觉。所以普通二叉搜索树能用的前提是输入数据接近随机或者你能打乱插入顺序。如果要应对最坏情况就得用平衡树比如 AVL 树、红黑树或者 Treap树堆利用随机优先级打乱插入形态。这个话题我在 7.3 节再展开。6.2 与数组、链表、哈希表的横向对比放在一起看更直观数据结构查找插入无序位置删除有序遍历备注有序数组O(log n) 二分O(n) 移动元素O(n)O(n)静态数据友好动态差链表O(n)O(1)有位置/ O(n) 查找O(1)有位置/ O(n) 查找O(n)无随机访问能力哈希表O(1) 平均O(1) 平均O(1) 平均不支持碰撞和扩容是隐患二叉搜索树O(log n) 平均O(log n) 平均O(log n) 平均O(n) 有序怕有序输入退化红黑树O(log n) 最坏O(log n) 最坏O(log n) 最坏O(n) 有序工业界主流这张表能回答很多实际问题。需要有序遍历、又要动态增删哈希表做不到数组/链表也各有短板BST 是自然选择。STL 里的map/set选红黑树而不是普通 BST就是因为红黑树把“最坏情况下依然 O(log n)”这个保证兜住了普通 BST 平均优秀但最坏太拉胯工程上不能直接用。7. 常见问题排查与调试心得7.1 空指针与内存泄漏树结构里最常见的两类问题我几乎每次调试都会遇到。第一类是空指针访问。典型场景删除节点时忘了判断左右子树是否为空直接访问node-left-val空指针直接崩。排查方法很笨但有效把所有访问成员变量的地方都往前看一步确认当前指针不是nullptr。写多了之后你会形成条件反射——凡是遇到-先问自己这个指针有没有可能为空第二类是内存泄漏。手写 C 树最容易漏的就是析构。默认析构只释放root_这一个节点其余节点全部泄漏。正确做法是递归释放全部节点template typename T void BinarySearchTreeT::clear(TreeNode* node) { if (node nullptr) return; clear(node-left); clear(node-right); delete node; } template typename T BinarySearchTreeT::~BinarySearchTree() { clear(root_); }注意这里用的是后序遍历——先删左右子树再删自己。如果用先序先删自己再去访问左右节点就是悬空指针访问必崩。深拷贝如果说要支持也补一下完整实现用先序方式重建整棵树template typename T auto BinarySearchTreeT::copyHelper(TreeNode* node) - TreeNode* { if (node nullptr) return nullptr; TreeNode* newNode new TreeNode(node-val); newNode-left copyHelper(node-left); newNode-right copyHelper(node-right); return newNode; }深拷贝选先序是顺理成章的得先创建当前节点再递归复刻它的左右子树。7.2 调试二叉搜索树的实用技巧调试树结构和调试普通代码不太一样光靠断点很难看出全局形状。我自己常用的三个方法方法一打印中序遍历。插入或删除之后先跑一遍中序如果结果不是严格递增数据结构一定有问题。这是第一道防线能快速定位“整棵树逻辑不正确”的问题。方法二写一个“树形打印”辅助函数。用缩进表示层级把树的结构可视化出来。这对检查删除后左右子树是否接对特别有帮助。template typename T void BinarySearchTreeT::printHelper(TreeNode* node, int depth) const { if (node nullptr) return; printHelper(node-right, depth 1); for (int i 0; i depth; i) std::cout ; std::cout node-val \n; printHelper(node-left, depth 1); }这个函数先递归右再递归左是因为控制台从上往下打印时要把树“横过来”看右子树在上、左子树在下才符合我们平时画树的方位感。方法三对拍验证。如果你不确定自己树的删除逻辑是否正确可以同时维护一个std::multiset插入和删除相同序列然后不断比较“树的 contains 结果”和 multiset 的结果是否一致。对拍是验证复杂算法最省心的方式比人肉肉眼 debug 高效得多。7.3 优化扩展思路从普通 BST 到平衡树文章里讲的都是普通二叉搜索树但如果你要把它用在生产环境最后一定绕不开平衡问题。AVL 树的思路每个节点记录平衡因子左右子树高度差插入/删除后如果某节点平衡因子绝对值超过 1就通过单旋转或双旋转重新调整。优点是树严格平衡最坏高度约 1.44log(n)缺点是每次插入/删除可能触发多次旋转开销略大。红黑树的思路用颜色标记节点保证从根到叶子最长路径不超过最短路径的两倍是“近似平衡”。旋转次数比 AVL 少整体性能更平滑STL 选它是有原因的。Treap 的思路更贴合这篇文章每个节点额外生成一个随机优先级然后同时满足 BST按键值和堆按优先级的性质。插入时用旋转调整随机性让树形态大概率平衡。实现比 AVL 简单应对有序输入的效果却很好非常推荐学完普通 BST 之后进阶的第一个结构。我个人在实际调试中的体会是手撕一棵普通二叉搜索树真正的收获不在于代码本身而在于把“递归返回值的传递”“空指针的防御”“节点所有权归属”这些 C 的底层肌肉记忆建立起来。这几件事搞通了再看红黑树、B 树都只是在不同约束条件下对“有序”这个需求的变体实现骨架都是通的。最后分享一个小技巧写删除函数的时候先在纸上分情况推演一棵三层的树一步步模拟“递归向下找、找到后分支处理、返回值接回父节点”这个过程再动键盘。我教过不少朋友写这个函数凡是卡住的基本都是没做过这个模拟直接埋头写代码。树结构这种东西画图永远比硬想高效。 C++手撕二叉搜索树：从原理到实现，核心操作与避坑指南
平时刷题或者写业务代码的时候是不是经常遇到这种场景有一堆动态变化的数据需要快速判断某个值在不在、比它小的有多少、它的前驱后继是谁。哈希表固然能做到 O(1) 查找但数据一多哈希碰撞和扩容就很烦人而且它没法有序遍历。这时候二叉搜索树就是一个非常自然的选择。这篇文章我围绕 C 怎么完整“手撕”一棵二叉搜索树从节点设计、插入、查找、删除到遍历和性能分析全部用文字加示意拆开来讲包含我实际调试中的避坑心得适合刚学完 C 基础、想啃树结构的读者也适合面试前系统过一遍二叉搜索树的同学。1. 二叉搜索树的底层逻辑与典型应用1.1 二叉搜索树的定义与核心性质先给一个严格的直觉定义二叉搜索树是一棵二叉树满足每个节点的左子树里所有值都严格小于当前节点值右子树里所有值都严格大于当前节点值而且左右子树本身也必须满足同样性质。这样说有点干巴换个方式理解。你手里有一本按拼音排序的通讯录要找“张三”你不会从第一页翻起而是会先翻到中间页根据拼音“z”应该靠后这个判断直接把后半本拎出来再继续折半。二叉搜索树就是把这种“折半定位”的逻辑用树形结构组织起来——每个节点都是一次二分判断的分界点左半边全走左边右半边全走右边。示意一下这棵最简单的树50 / \ 30 70 / \ / \ 20 40 60 80根节点是 50左边全小于 50右边全大于 50。到了 30 这个节点它的左边还是小于 30、右边大于 30。这个“左小右大”的结构从根到叶子递归保持一致就是二叉搜索树的核心约束。有一个细节必须拎出来强调是“左子树所有值”都小于根不是“左孩子”小于根。也就是说下面这种结构虽然每个节点都满足“左孩子 自己 右孩子”但它不是合法的二叉搜索树10 / \ 5 15 / \ 3 1212 是 10 的左子树里的节点却比根 10 大。所以做性质校验时不能只检查相邻关系要检查整棵子树的上下界这个我后面在 5.2 节单独讲。1.2 面试高频与工业应用为什么值得手撕说点实在的手撕一棵二叉搜索树最直接的价值有三个。第一STL 里的std::map、std::set底层几乎都是红黑树——红黑树本身就是一棵“带平衡约束的二叉搜索树”。你去看红黑树的插入第一步就是按普通二叉搜索树的方式找到插入位置然后再做颜色调整和旋转。所以二叉搜索树不会写红黑树更是无从谈起。第二手撕这棵树是检验“指针和递归”这两件事掌握程度的最佳试炼场。插入要递归挂节点删除要处理悬空指针析构要递归释放拷贝要深拷贝每一个环节都在考验你对内存生命周期的理解。很多初学者 C 语法学得很顺一到树结构就卡壳根源就是指针操作不够熟。第三面试题里二叉搜索树是常驻嘉宾。“验证一棵树是不是 BST”“恢复一棵被交换节点的 BST”“求第 K 小的元素”“判断一棵树是否平衡”全都是它的变体。树本身没几行代码但能不能快速、无 bug 地把它写出来面试官一看便知你的基本功。2. 手撕前的准备工作节点设计与结构规划2.1 节点数据结构的选择动手写代码前先把节点长什么样定下来。我用的是模板类方便后面存 int、存自定义类型都可以template typename T struct TreeNode { T val; TreeNode* left; TreeNode* right; explicit TreeNode(const T v) : val(v), left(nullptr), right(nullptr) {} };这里有个选型问题值得说。为什么用struct而不是class因为struct成员默认是公有public的在我们自己手写的数据结构里节点内部字段被外部访问不是坏事反而是简化代码的途径。你要是用class还得一个个写public:纯属冗余。构造函数里一定要把left和right初始化为nullptr。这不是偷懒而是防止出现“野指针”状态——你new一个节点出来如果不初始化指针成员它的值是不确定的后面哪怕只是判断if (node-left)都会是未定义行为。养成构造函数内初始化的习惯能帮你省下一大半的空指针崩溃调试时间。关于要不要加parent指针我多说两句。加了parent删除节点时可以用迭代方式做不用递归删除有两个子节点的节点时回溯比较方便但代价是插入和删除时都要额外维护父指针代码量直接翻倍还容易漏更新。面试和大部分教科书实现都不用parent用递归天然携带“父节点信息”简洁得多。所以我建议面试手撕不加parent除非题目明确要求迭代实现再考虑。2.2 类模板设计与成员规划节点定好了再封装一棵树。我的类设计是这样的template typename T class BinarySearchTree { public: BinarySearchTree() : root_(nullptr), size_(0) {} // 禁止拷贝先留个坑后面 7.2 节再补深拷贝 BinarySearchTree(const BinarySearchTree) delete; BinarySearchTree operator(const BinarySearchTree) delete; ~BinarySearchTree(); void insert(const T val); bool contains(const T val) const; void remove(const T val); void inorder() const; size_t size() const { return size_; } bool empty() const { return root_ nullptr; } private: struct TreeNode { T val; TreeNode* left; TreeNode* right; explicit TreeNode(const T v) : val(v), left(nullptr), right(nullptr) {} }; TreeNode* root_; size_t size_; // 辅助函数全部放到 private TreeNode* insertHelper(TreeNode* node, const T val); bool containsHelper(TreeNode* node, const T val) const; TreeNode* removeHelper(TreeNode* node, const T val); void inorderHelper(TreeNode* node) const; void clear(TreeNode* node); };为什么要把插入、删除这类函数放到private再包一层public接口因为递归函数需要把当前节点作为参数传进来直接暴露给调用方没意义而且调用方也拿不到私有节点指针。外部用户只需要bst.insert(5)没必要看到insertHelper(root_, 5)这种细节。这就是典型的“公共接口 私有实现”模式。size_这个成员很多人会漏掉。维护一个节点计数能在 O(1) 时间回答“树里有多少元素”而不是每次遍历统计。插入成功size_删除成功--size_多这一行代码的事但很实用。关于拷贝构造和赋值运算符我先禁用掉了。原因是默认的浅拷贝会让两棵树共享同一批节点任何一颗析构时释放内存另一颗就变成悬空指针用起来就是灾难。如果你确实需要复制一棵树得写深拷贝递归这个我留在 7.2 节给完整实现。3. 核心操作手撕插入与查找3.1 递归插入的正确姿势插入的逻辑和二分查找一个思路从根开始如果待插入值比当前节点小就往左走比它大就往右走直到某一步发现当前位置是空直接new一个节点挂上去。递归版本写起来非常短但真正要理解的是“返回值为什么要接回左孩子/右孩子”template typename T auto BinarySearchTreeT::insertHelper(TreeNode* node, const T val) - TreeNode* { if (node nullptr) { size_; return new TreeNode(val); } if (val node-val) { node-left insertHelper(node-left, val); } else if (val node-val) { node-right insertHelper(node-right, val); } // 相等的情况我们选择忽略不插入重复值 return node; } template typename T void BinarySearchTreeT::insert(const T val) { root_ insertHelper(root_, val); }“接回去”这句话很关键。递归调用insertHelper(node-left, val)返回的是“左子树经过插入之后应该长成的新根”。如果一个节点都没有它返回新节点如果递归找到了合适位置它返回原来的左孩子。不管哪种情况当前节点的left指针都要用返回值更新。如果不接回来新插入的节点就悬空了和整棵树完全断连。重复值怎么处理我这里的策略是直接忽略。如果你想支持重复有两个选择一是节点里加一个计数count二是允许相等的值进右子树。但我要提醒如果选择第二种一定要保证“相等的值永远走右子树”否则你后续删除、查找前驱后继都会出逻辑问题。工程上更常见的是加计数直观而且不影响findMin/findMax的正确性。迭代版插入我也顺手写一下它需要维护一个parent指针记录最后挂载的位置template typename T void BinarySearchTreeT::insert(const T val) { TreeNode* node root_; TreeNode* parent nullptr; while (node ! nullptr) { parent node; if (val node-val) { node node-left; } else if (val node-val) { node node-right; } else { return; // 重复 } } TreeNode* newNode new TreeNode(val); size_; if (parent nullptr) { root_ newNode; } else if (val parent-val) { parent-left newNode; } else { parent-right newNode; } }循环结束的时候node已经为空但它的前驱parent还在所以可以确定新节点要挂在parent的哪一侧。这个版本没有递归调用栈空间是 O(1)缺点就是代码比递归长一点。两种写法都建议自己敲一遍。3.2 查找操作递归与迭代的取舍查找不需要修改任何节点所以逻辑上比插入简单。递归写法template typename T bool BinarySearchTreeT::containsHelper(TreeNode* node, const T val) const { if (node nullptr) return false; if (val node-val) return true; if (val node-val) return containsHelper(node-left, val); return containsHelper(node-right, val); }递归版本可读性很好但我在实际工程和面试答疑里更推荐迭代版本template typename T bool BinarySearchTreeT::contains(const T val) const { TreeNode* node root_; while (node ! nullptr) { if (val node-val) { node node-left; } else if (val node-val) { node node-right; } else { return true; } } return false; }原因很简单递归版本每次调用都要压栈查找一棵深度为 10000 的树就要压 10000 层栈迭代版本用 while 循环扫描过程完全不消耗额外栈空间。二叉搜索树查找本身就是一条“向下的路径”天然能用循环表达没必要递归。面试时你写递归也不会扣分但能说清楚“迭代版本避免了栈溢出和函数调用开销”这是加分项。再顺手实现两个最常用的变体——找最小值和最大值template typename T auto BinarySearchTreeT::findMin(TreeNode* node) const - TreeNode* { while (node ! nullptr node-left ! nullptr) { node node-left; } return node; } template typename T auto BinarySearchTreeT::findMax(TreeNode* node) const - TreeNode* { while (node ! nullptr node-right ! nullptr) { node node-right; } return node; }最小节点就是一路往左走到黑最大节点一路往右走到黑。因为 BST 的性质保证了“最小的值一定在左子树的最左端最大的值一定在右子树的最右端”。这两个函数在删除操作里是核心工具先写出来备用。3.3 查找前驱与后继节点前驱和后继在面试里出现频率不低也是最容易被人忽略的两个函数。定义如下节点x的前驱小于x-val的所有节点里最大的那个。节点x的后继大于x-val的所有节点里最小的那个。求法分两种情况讨论。第一种情况x有左子树/右子树。前驱就是左子树里的最大值后继就是右子树里的最小值直接用上面写的findMax/findMin就能拿到。第二种情况x没有左子树/右子树。这时候要找它的“祖先里的第一个转折点”。以前驱为例如果x没有左子树说明左边已经到底了只能往上走找第一个“从右子树方向上来”的祖先这个祖先就是前驱。后继对称理解。如果节点里没存parent指针从根往下搜就好了template typename T auto BinarySearchTreeT::successor(const T val) const - std::optionalT { TreeNode* cur root_; TreeNode* ans nullptr; while (cur ! nullptr) { if (cur-val val) { ans cur; // 候选后继 cur cur-left; } else { cur cur-right; } } if (ans nullptr) return std::nullopt; return ans-val; }这个迭代的精髓在于每次遇到比val大的节点就先把它记为候选后继然后往左收紧边界遇到比val小的节点就往右走但不用更新候选。最后ans就是比val大的最小节点。用std::optional是 C17 的做法能优雅地表示“不存在后继”的情况。4. 最棘手的一环二叉搜索树的删除4.1 删除节点的三种情况删除是 BST 里最需要细抠的环节坑很多。按被删节点的孩子数量可以分成三种情况情况一叶子节点。直接delete掉让父节点对应的指针置空即可。情况二只有一个子节点。把这个唯一的孩子顶上来替代自己被删的位置。想象一个只有左孩子的节点你只要把左孩子“扶正”BST 性质不会破坏——因为左子树的所有值本来就比自己小而自己又比父节点的某些部分小/大整体顺序依然成立。情况三有两个子节点。最麻烦的一类。不能直接删因为你一旦删掉节点两个子树都悬空了无论把哪个提上来另外一个都没地方挂。解决办法是“移花接木”找一个既比左子树所有值大、又比右子树所有值小的节点来顶替自己。天然满足条件的候选有两个——左子树的最大节点和右子树的最小节点也就是前驱或后继。我们通常选右子树的最小节点后继来顶替。先看代码实现我用的整体框架是递归删除template typename T auto BinarySearchTreeT::removeHelper(TreeNode* node, const T val) - TreeNode* { if (node nullptr) return nullptr; if (val node-val) { node-left removeHelper(node-left, val); } else if (val node-val) { node-right removeHelper(node-right, val); } else { // 找到要删的节点 if (node-left nullptr node-right nullptr) { // 情况一叶子 delete node; --size_; return nullptr; } if (node-left nullptr) { // 情况二只有右孩子 TreeNode* rightChild node-right; delete node; --size_; return rightChild; } if (node-right nullptr) { // 情况二只有左孩子 TreeNode* leftChild node-left; delete node; --size_; return leftChild; } // 情况三两个孩子都在 TreeNode* successorNode findMin(node-right); node-val successorNode-val; node-right removeHelper(node-right, successorNode-val); } return node; }注意这里我处理情况二的方式不是先删再赋值而是先把要保留的孩子保存到临时变量再delete当前节点最后把这个孩子返回给上层由上层完成“接回父节点”。这个顺序很重要写反了就会访问已被释放的内存。4.2 两个子节点场景的经典解法与原理两个子节点的情况多数教材会推荐“把后继的值拷贝到当前节点然后递归删掉右子树里的后继节点”。上代码里就是这样做的。很多人会问一句为什么不直接delete当前节点、把后继节点整个挪上来答案是不划算。如果你想把后继节点“挪”上来需要处理后继节点原本左右子树的重新挂载问题还要处理后继节点的父节点指针复杂度一下就上来了。而“拷贝值 递归删除后继”的方案后继节点必然是右子树的最小节点它最多只有一个右孩子不可能有左孩子因为它是右子树里最小的这就退化成了情况一或情况二的简单删除代码直接复用上面的分支即可。为什么选右子树最小节点而不是左子树最大节点两个都可以选后继是约定俗成的习惯。还有一个细节拷贝值会改变节点本身的存储但树的形状结构只发生微小变化——这个操作本质上是“把删除节点的复杂度降低到删除一个叶子/单孩子节点的复杂度”非常优雅。我在实际调试中还发现一个容易被坑的点递归删除后继时findMin(node-right)找到的后继节点的val与当前节点存在“可能相等”的情况吗如果树里不允许重复值不会相等。但如果你在插入时允许了重复值这里就要特别小心删除逻辑会变得很绕。所以我在 3.1 节强烈建议用计数法处理重复就是为了让删除保持简单。再补充一个极端场景如果右子树就是当前节点的右孩子而且这个右孩子就是最小节点比如5 \ 6 \ 7删除 5 时findMin(node-right)找到的就是 6。拷贝 6 到 5 的位置再递归删除右子树里的 6。因为在右子树里寻找 6 时6 在根的位置它的右孩子是 7所以走“只有右孩子”的分支把 7 接回来。整个过程依然正确但值得手动模拟一遍否则很容易在递归回溯时弄晕。5. 遍历与性质验证5.1 三种深度优先遍历的工程取舍遍历树是高频需求。先看标准递归template typename T void BinarySearchTreeT::preorderHelper(TreeNode* node) const { if (node nullptr) return; std::cout node-val ; // 前序先根 preorderHelper(node-left); preorderHelper(node-right); } template typename T void BinarySearchTreeT::inorderHelper(TreeNode* node) const { if (node nullptr) return; inorderHelper(node-left); std::cout node-val ; // 中序左根右 inorderHelper(node-right); } template typename T void BinarySearchTreeT::postorderHelper(TreeNode* node) const { if (node nullptr) return; postorderHelper(node-left); postorderHelper(node-right); std::cout node-val ; // 后序左右根 }三种遍历的时间复杂度都是 O(n)因为每个节点恰好访问一次空间复杂度都是 O(h)h是树高——递归栈的深度取决于树的形状。工程上常见的问题就是递归深度。如果一棵树退化成链表后面的 6.1 节会讲为什么会退化高度可能达到 n递归一万层轻则栈溢出重则程序直接崩。所以巨深的树要用迭代版本遍历。这里我不展开全部代码但给一个标准模板用显式栈模拟递归。template typename T void BinarySearchTreeT::inorderIterative() const { std::stackTreeNode* st; TreeNode* cur root_; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; // 一路向左 } cur st.top(); st.pop(); std::cout cur-val ; cur cur-right; // 转向右子树 } }这个迭代中序是面试写代码的高频题思路要和“递归压栈”对照着理解递归的本质是系统栈帮我们记录了每个待访问的节点迭代就是自己动手维护这个栈。5.2 用中序遍历校验树的正确性二叉搜索树的中序遍历结果严格递增这是判断一棵树是否合格的黄金法则。为什么会这样因为中序访问顺序是左子树、根、右子树而 BST 的定义保证左子树所有值都小于根、右子树所有值都大于根递归到每个节点都成立整个序列自然就严格递增。利用这一点最简单粗暴的二叉搜索树合法性检查就是跑一遍中序看结果是否严格递增。但如果你只想判断“是不是合法 BST”更高效的写法是带上下界递归template typename T bool BinarySearchTreeT::isValidBSTHelper(TreeNode* node, const T minVal, const T maxVal) const { if (node nullptr) return true; if (node-val minVal || node-val maxVal) return false; return isValidBSTHelper(node-left, minVal, node-val) isValidBSTHelper(node-right, node-val, maxVal); }调用时初始上下界用std::numeric_limitsT::lowest()和max()。这个实现为什么对因为每个节点都被限制在一个开区间里左子树的上界是当前节点值右子树的下界是当前节点值。这样能捕获 1.1 节举的那个“12 藏在 10 的左子树里”的非法结构。一个容易踩的坑如果树的泛型类型是int初始上下界用INT_MIN和INT_MAX是没有问题的但如果存的是long long或者自定义类型直接给“最小/最大”就不合适。更稳妥的做法是加一个std::optionalT或者用指针传上下界为空表示无限制。这个小改动在面试里提出来考官会觉得你考虑问题很周全。5.3 层序遍历与队列配合层序遍历也叫广度优先BFS需要配合队列template typename T void BinarySearchTreeT::levelOrder() const { if (root_ nullptr) return; std::queueTreeNode* q; q.push(root_); while (!q.empty()) { TreeNode* cur q.front(); q.pop(); std::cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }层序遍历的应用场景很广按层打印树结构、统计每层的节点数、序列化和反序列化二叉树、检查完全二叉树等等。比如要算出树的最大宽度就是 BFS 过程中记录每一层的节点数取最大值。如果要求“按层分组输出”可以在while里先记录当前q.size()然后一次性处理完这一层while (!q.empty()) { size_t levelSize q.size(); for (size_t i 0; i levelSize; i) { // 依次取出当前层节点 } // 到这里q 里刚好是下一层所有节点 }这个“先取 size 再处理一层”的技巧在很多题目里都比不分组输出实用得多。6. 性能分析为什么有序输入会把树变成链表6.1 平均复杂度与最坏复杂度二叉搜索树的插入、查找、删除复杂度完全取决于树的高度理想平衡情况下高度是 O(log n)三个操作都是 O(log n)。最坏情况下树退化成一条链高度是 O(n)三个操作全是 O(n)。什么时候退化连续插入有序数据。比如你按 1、2、3、4、5……的顺序插入每个新节点都比当前节点大于是一直往右子树走到底树就长成了这样1 \ 2 \ 3 \ 4这就完全退化成了单链表二叉搜索树的一半优势直接没了。我见过不少初学者用二叉搜索树跑大数据量的程序开始还挺快后来越跑越慢最后发现就是插入顺序太“好”了树已经变成一条直线。平均情况呢如果插入元素的顺序是随机的树的高度大致是 O(log n)这个有概率分析的结论实践中基本符合直觉。所以普通二叉搜索树能用的前提是输入数据接近随机或者你能打乱插入顺序。如果要应对最坏情况就得用平衡树比如 AVL 树、红黑树或者 Treap树堆利用随机优先级打乱插入形态。这个话题我在 7.3 节再展开。6.2 与数组、链表、哈希表的横向对比放在一起看更直观数据结构查找插入无序位置删除有序遍历备注有序数组O(log n) 二分O(n) 移动元素O(n)O(n)静态数据友好动态差链表O(n)O(1)有位置/ O(n) 查找O(1)有位置/ O(n) 查找O(n)无随机访问能力哈希表O(1) 平均O(1) 平均O(1) 平均不支持碰撞和扩容是隐患二叉搜索树O(log n) 平均O(log n) 平均O(log n) 平均O(n) 有序怕有序输入退化红黑树O(log n) 最坏O(log n) 最坏O(log n) 最坏O(n) 有序工业界主流这张表能回答很多实际问题。需要有序遍历、又要动态增删哈希表做不到数组/链表也各有短板BST 是自然选择。STL 里的map/set选红黑树而不是普通 BST就是因为红黑树把“最坏情况下依然 O(log n)”这个保证兜住了普通 BST 平均优秀但最坏太拉胯工程上不能直接用。7. 常见问题排查与调试心得7.1 空指针与内存泄漏树结构里最常见的两类问题我几乎每次调试都会遇到。第一类是空指针访问。典型场景删除节点时忘了判断左右子树是否为空直接访问node-left-val空指针直接崩。排查方法很笨但有效把所有访问成员变量的地方都往前看一步确认当前指针不是nullptr。写多了之后你会形成条件反射——凡是遇到-先问自己这个指针有没有可能为空第二类是内存泄漏。手写 C 树最容易漏的就是析构。默认析构只释放root_这一个节点其余节点全部泄漏。正确做法是递归释放全部节点template typename T void BinarySearchTreeT::clear(TreeNode* node) { if (node nullptr) return; clear(node-left); clear(node-right); delete node; } template typename T BinarySearchTreeT::~BinarySearchTree() { clear(root_); }注意这里用的是后序遍历——先删左右子树再删自己。如果用先序先删自己再去访问左右节点就是悬空指针访问必崩。深拷贝如果说要支持也补一下完整实现用先序方式重建整棵树template typename T auto BinarySearchTreeT::copyHelper(TreeNode* node) - TreeNode* { if (node nullptr) return nullptr; TreeNode* newNode new TreeNode(node-val); newNode-left copyHelper(node-left); newNode-right copyHelper(node-right); return newNode; }深拷贝选先序是顺理成章的得先创建当前节点再递归复刻它的左右子树。7.2 调试二叉搜索树的实用技巧调试树结构和调试普通代码不太一样光靠断点很难看出全局形状。我自己常用的三个方法方法一打印中序遍历。插入或删除之后先跑一遍中序如果结果不是严格递增数据结构一定有问题。这是第一道防线能快速定位“整棵树逻辑不正确”的问题。方法二写一个“树形打印”辅助函数。用缩进表示层级把树的结构可视化出来。这对检查删除后左右子树是否接对特别有帮助。template typename T void BinarySearchTreeT::printHelper(TreeNode* node, int depth) const { if (node nullptr) return; printHelper(node-right, depth 1); for (int i 0; i depth; i) std::cout ; std::cout node-val \n; printHelper(node-left, depth 1); }这个函数先递归右再递归左是因为控制台从上往下打印时要把树“横过来”看右子树在上、左子树在下才符合我们平时画树的方位感。方法三对拍验证。如果你不确定自己树的删除逻辑是否正确可以同时维护一个std::multiset插入和删除相同序列然后不断比较“树的 contains 结果”和 multiset 的结果是否一致。对拍是验证复杂算法最省心的方式比人肉肉眼 debug 高效得多。7.3 优化扩展思路从普通 BST 到平衡树文章里讲的都是普通二叉搜索树但如果你要把它用在生产环境最后一定绕不开平衡问题。AVL 树的思路每个节点记录平衡因子左右子树高度差插入/删除后如果某节点平衡因子绝对值超过 1就通过单旋转或双旋转重新调整。优点是树严格平衡最坏高度约 1.44log(n)缺点是每次插入/删除可能触发多次旋转开销略大。红黑树的思路用颜色标记节点保证从根到叶子最长路径不超过最短路径的两倍是“近似平衡”。旋转次数比 AVL 少整体性能更平滑STL 选它是有原因的。Treap 的思路更贴合这篇文章每个节点额外生成一个随机优先级然后同时满足 BST按键值和堆按优先级的性质。插入时用旋转调整随机性让树形态大概率平衡。实现比 AVL 简单应对有序输入的效果却很好非常推荐学完普通 BST 之后进阶的第一个结构。我个人在实际调试中的体会是手撕一棵普通二叉搜索树真正的收获不在于代码本身而在于把“递归返回值的传递”“空指针的防御”“节点所有权归属”这些 C 的底层肌肉记忆建立起来。这几件事搞通了再看红黑树、B 树都只是在不同约束条件下对“有序”这个需求的变体实现骨架都是通的。最后分享一个小技巧写删除函数的时候先在纸上分情况推演一棵三层的树一步步模拟“递归向下找、找到后分支处理、返回值接回父节点”这个过程再动键盘。我教过不少朋友写这个函数凡是卡住的基本都是没做过这个模拟直接埋头写代码。树结构这种东西画图永远比硬想高效。