拓冰网站定制 核心原理与C++实现：插入、删除、查找全解析)
1. 二叉搜索树到底解决了什么问题1.1 从数组和链表的性能瓶颈说起先抛一个老生常谈但确实扎心的问题我们要维护一个动态集合支持插入、删除、查找三种操作用什么结构最舒服数组的查找快O(1)随机访问但插入和删除要搬动大量元素平均O(n)。链表的插入和删除倒是O(1)前提是已经知道位置但查找得从头遍历平均O(n)。有序数组能通过二分查找把搜索降到O(log n)可一旦涉及插入和删除数组的劣势立刻暴露——你插入一个元素到有序数组中间后面所有元素都要后移。也就是说在二叉搜索树Binary Search TreeBST出现之前没有一个结构能同时把插入、删除、查找都维持在较好的效率上。BST的核心价值就在这里它利用节点之间的大小关系把查找目标值从线性扫描转化为沿着树的路径走每一步都能排除掉一半的搜索空间。我曾跟刚学数据结构的朋友开玩笑说BST就是把二分查找的有序数组这层壳子拆掉换成了一套指针结构让插入和删除不再需要搬动数据。这套指针结构保留了二分查找的高效路径这就是它被称作二叉搜索树而不是二叉排序树的根本原因——它的搜索性质是第一位的。1.2 BST的核心性质与二分思想的落地BST的定义并不复杂每个节点最多有两个孩子左子树中的所有节点值都小于根节点值右子树中的所有节点值都大于根节点值并且左右子树本身也各自满足同样的条件。这个递归定义才是关键。你看这个性质天然就让比较大小这个操作变成了前进路标如果当前节点值大于目标值目标只可能出现在左子树小于则去右子树等于就直接命中。这里有一点容易被忽略BST的有序体现在中序遍历结果是一个严格递增序列。也就是说如果我们对一棵BST做中序遍历左子树、根、右子树拿到的是一串从小到大排列的值。这个特性在后面做校验、调试、甚至设计迭代器时都会用上建议先记在心里。我在实际刷题和工程编码中还有个体会BST的所有操作都依赖同一个比较函数。如果你想支持自定义类型或者排序规则直接替换这个比较逻辑就行整体框架不用动。这一点在后面的类设计里我会再次强调。2. 动手前的设计节点结构与类接口2.1 节点结构体怎么定义最顺手代码风格这件事每个人都有习惯但BST节点结构体我建议尽量精简、通用别塞太多跟树操作无关的字段。一个标准节点只需要三样东西值、左孩子指针、右孩子指针。泛型版本还要多一个模板参数。template typename T struct BSTNode { T value; BSTNode* left; BSTNode* right; explicit BSTNode(const T val) : value(val), left(nullptr), right(nullptr) {} };构造函数我习惯写成explicit避免隐式转换引发奇怪的编译问题。值用const引用传递是为了避免值拷贝浪费对于类似string这样的类型尤其明显。有些教材会在节点里加一个parent指针方便实现迭代器和非递归删除。但工程上我很少默认加它原因有二第一parent指针会让节点的生命周期管理变得复杂左右旋、删除时需要同步维护的指针数量翻倍第二递归写法根本不需要parent也能实现全部操作。加了parent调试的时候反而更容易懵。如果后续需要实现迭代器再动态加一个带parent的版本也不迟。2.2 类接口设计哪些方法必须有哪些可以偷懒类的对外接口我一般按必须提供和可选提供两档来划分。作为一个能被实际使用的容器BST至少应该支持以下几类操作插入insert(const T)删除erase(const T) 或 erase(const T) 返回是否删除成功查找contains(const T) 返回bool或者find返回迭代器/指针遍历中序遍历用于数据有序输出和验证辅助信息size()返回节点个数empty()判断空树很多教材喜欢把删除设计成返回bool因为用户删除一个不存在的值时他需要得到反馈。查找返回bool通常也够用如果你需要找到目标节点后修改它的值这种操作那find得返回节点指针我会单独提供一个findNode接口。类内部的核心实现我推荐把对节点的操作封装成私有递归函数对外只暴露简洁的接口。为什么因为递归函数天然需要一个以某个节点为根的子树作为参数而对外接口不应该暴露根节点指针。接口和实现分离改动内部实现时不影响调用方这是C工程里最基本的封装素养。template typename T class BST { public: BST() : root(nullptr), size_(0) {} void insert(const T val) { root insertRec(root, val); } bool erase(const T val) { return eraseRec(root, val); } bool contains(const T val) const { return findRec(root, val) ! nullptr; } void inorder(std::vectorT out) const { inorderRec(root, out); } size_t size() const { return size_; } bool empty() const { return root nullptr; } private: BSTNodeT* root; size_t size_; // 私有递归函数声明... };这里有个细节值得提醒insert和erase的返回值都覆盖了root。这个习惯非常重要因为当你在空树中插入第一个节点或者删除根节点时根节点指针会被修改。如果你只用局部变量接收返回值而不更新root你会发现插入了节点但树还是空的或者删除了根节点之后树整个丢失。这是新手写BST最容易踩的坑没有之一。3. 插入和查找构建与查询的核心路径3.1 插入操作非递归写法实战插入操作是BST最基础的操作之一我先给出非递归版本。非递归的好处是栈空间不增长对于树很高的场景更安全而且不用考虑递归函数返回值如何传回上层的问题。template typename T void BSTT::insertIter(const T val) { BSTNodeT* newNode new BSTNodeT(val); if (root nullptr) { root newNode; size_; return; } BSTNodeT* cur root; BSTNodeT* parent nullptr; while (cur ! nullptr) { parent cur; if (val cur-value) { cur cur-left; } else if (val cur-value) { cur cur-right; } else { delete newNode; // 重复值不做插入 return; } } if (val parent-value) { parent-left newNode; } else { parent-right newNode; } size_; }这段代码的核心逻辑是先通过循环找到目标插入位置循环结束时cur为空但parent保存了最后一个非空节点这个节点就是新节点的父亲。然后再比较一次新值和parent的值决定挂在左边还是右边。注意我处理了重复值的情况——如果待插入的值在树中已经存在直接放弃插入释放新节点的内存避免内存泄漏。关于重复值的处理策略其实可以讨论有人喜欢左边放小于等于右边放大于形成左闭右开的性质这样插入相同值时能保持稳定顺序。但作为集合容器默认语义就是元素唯一我建议做成去重。这个非递归版本有一个隐含假设树中节点的比较运算符定义正确。如果T是自定义类型记得重载和或者用仿函数/函数对象替代直接比较否则编译和运行都会出问题。3.2 查找操作从根到目标的路径查找的逻辑跟插入很像但少了一个记录parent的步骤因为查找只需要返回最终节点不需要知道它的父亲是谁。递归版本写出来极其简洁template typename T BSTNodeT* BSTT::findRec(BSTNodeT* node, const T val) const { if (node nullptr) return nullptr; if (val node-value) return node; if (val node-value) return findRec(node-left, val); return findRec(node-right, val); }三步走当前节点为空说明没找到当前值等于目标值直接返回否则根据大小关系走左或右。这个函数的时间复杂度是O(h)h是树高。我在LeetCode上做题时发现很多人执着于把所有查找都改成非递归但其实这里的递归深度在最坏情况下也就是树高而普通场景下插入的树高度一般远小于节点数栈溢出风险很低。与其牺牲可读性做非递归不如把精力放在后续的删除和旋转这些真正复杂的地方。查找还有一个工程上的细节如果BST存放的是对象而不是简单类型直接比较整个对象可能开销较大。某些高性能场景会用键值分离即节点存一个key用于比较和一个value用于存储这就是map和set的差别了。不过对于本文的入门级别直接存T就够了。3.3 中序遍历验证BST正确性的最好工具中序遍历代码很简短但它是验证整棵树是否正确的金牌工具。template typename T void BSTT::inorderRec(BSTNodeT* node, std::vectorT out) const { if (node nullptr) return; inorderRec(node-left, out); out.push_back(node-value); inorderRec(node-right, out); }为什么说它是验证工具因为BST的中序遍历结果必须严格递增。插入之后再中序输出一遍看看序列是否从小到大排列就能快速发现插入逻辑里挂错左右子树的问题。删除之后再中序输出一遍可以确认删除没有破坏树的有序性。我习惯在写完插入、删除后立刻用中序序列做回归验证。比如插入 {5, 3, 8, 1, 4, 7, 9}中序输出应该是 1, 3, 4, 5, 7, 8, 9。如果输出不是严格递增说明代码有bug。这个方法比肉眼盯着节点指针靠谱得多尤其是在删除操作涉及子树拼接的时候。4. 删除操作BST中最容易翻车的环节4.1 三种情况从简单到复杂删除操作是BST的核心难点原因在于被删除的节点可能带有一个或两个孩子直接拔掉会让子树失联。教科书通常把删除分成三种情况情况一叶子节点。没有孩子直接释放内存父节点对应指针置空即可。最简单最没有歧义。情况二只有一个孩子。把当前节点删除让它的父节点直接指向它的唯一孩子。相当于链表删除中间节点。情况三有两个孩子。这是最麻烦的。你无法直接把当前节点摘掉因为摘掉后左右子树都失去连接。标准做法是找到当前节点的中序前驱左子树中最大值或中序后继右子树中最小值用前驱/后继的值把当前节点的值覆盖掉然后递归删除那个前驱/后继节点。因为前驱/后继节点必然最多只有一个孩子删除问题就退化成了情况一或情况二。理解第三种情况的精髓在于直接删一个拥有两个孩子的节点是做不到的但我们可以偷梁换柱——用另一个更简单的节点替换它再去删除那个简单节点。树的节点总数减一但是被真正物理删除的节点不是名义上被删的值所在的节点。举个例子删除下面这棵树的根节点88 / \ 3 10 / \ \ 1 6 14根节点8有两个孩子。我们找左子树的最大值6或者右子树的最小值10把6的值覆盖到根节点上然后递归删除左子树里的节点6。最终得到6 / \ 3 10 / \ 1 14注意这里节点的值变了但是树的结构调整很少其他节点之间的父子关系几乎不受影响。这就是用前驱/后继替换的意义——尽量减少结构调整。4.2 前驱与后继的选择策略找前驱左子树最大值从当前节点的左孩子出发一路向右走到黑最后一个节点就是左子树中的最大值。找后继右子树最小值从当前节点的右孩子出发一路向左走到黑。用前驱还是用后继理论上是等价的没有优劣之分。我的习惯是固定用前驱左子树最大值因为实现起来只需一个循环。也有资料推荐交替使用前驱和后继说这样能避免树在某些特殊输入下退化得过于严重。这个说法在工程上效果存疑因为删除本身对树的形态影响远不如插入大我一般不折腾。有一个坑必须提当你用前驱值覆盖当前节点后要删除的是左子树中那个前驱节点。如果左子树的前驱节点恰好是当前节点的左孩子即左孩子没有右子树那么递归删除时要正确处理parent指针。如果没写对可能出现左孩子指针悬空或者指向错误的情况。4.3 递归删除的完整实现递归删除是写起来最干净、也最容易出bug的版本。下面给出完整代码配合注释逐行解释template typename T bool BSTT::eraseRec(BSTNodeT* node, const T val) { if (node nullptr) { return false; // 没找到 } if (val node-value) { return eraseRec(node-left, val); } else if (val node-value) { return eraseRec(node-right, val); } // 找到目标节点开始删除 if (node-left nullptr node-right nullptr) { // 情况一叶子节点 delete node; node nullptr; --size_; } else if (node-left nullptr) { // 情况二只有右孩子 BSTNodeT* tmp node; node node-right; delete tmp; --size_; } else if (node-right nullptr) { // 情况二只有左孩子 BSTNodeT* tmp node; node node-left; delete tmp; --size_; } else { // 情况三两个孩子都有 BSTNodeT* predecessor findMax(node-left); node-value predecessor-value; eraseRec(node-left, predecessor-value); } return true; }这个实现的精妙之处在于删除函数接收的是指向指针的引用BSTNode * node这样当上层调用eraseRec(node-left, val)时函数内部对node的赋值比如node node-right会直接修改上层node-left指针本身而不是修改指针的副本。这段话可能有点绕换个说法如果参数是指针的引用那么node nullptr这句话会真正把父节点的左/右孩子指针置空如果参数只是指针副本这句话只会把副本置空真正挂在树上的指针纹丝不动这就是经典的指针传参丢失修改问题。需要配套实现的辅助函数findMaxtemplate typename T BSTNodeT* BSTT::findMax(BSTNodeT* node) const { while (node-right ! nullptr) { node node-right; } return node; }这段删除逻辑还有一个容易忽略的点情况三找到前驱后用前驱值覆盖当前节点值然后递归删除前驱节点。我需要确保左子树中前驱节点被正确删除且当左子树为空时不会出问题。仔细看代码能走到情况三说明左右孩子都存在findMax(node-left)一定不会返回nullptr所以eraseRec(node-left, predecessor-value)一定会进入找到目标的分支不会走到第一行的nullptr判断。这就是递归调用安全性的来源。5. 复杂度分析与退化问题5.1 平均情况下的复杂度先给结论对于一棵随机的BST即节点按随机顺序插入查找、插入、删除的平均时间复杂度都是O(log n)其中n是节点总数。为什么是O(log n)而不是O(1)因为BST每次比较都能排除掉当前子树的一半在理想情况下。如果树是平衡的枚举一条从根到叶子的路径最多走树高步树高约为log2(n)。每一步做常数时间的比较操作所以总复杂度是O(log n)。中序遍历是O(n)因为它需要访问每一个节点这个无法避免。空间复杂度方面BST本身需要O(n)存储节点。递归实现的插入、查找、删除都有隐式栈空间开销最坏情况下递归深度等于树高也是O(h)。5.2 有序插入引发的退化问题BST最大的坑不是操作逻辑而是树的形态完全取决于插入顺序。如果你按升序插入 1, 2, 3, 4, 5, 6, ...这棵树会退化成一个完全向右倾斜的链表1 \ 2 \ 3 \ 4 \ 5此时树高h n查找时间复杂度从O(log n)恶化到O(n)。换句话说BST在最坏情况下并不比链表强多少。这个问题怎么破业界主流做法是引入平衡机制让树在插入、删除后自动调整形态保证树高始终接近O(log n)。这就是AVL树、红黑树等平衡二叉搜索树存在的原因。STL里的std::map和std::set底层用的是红黑树C11之后还提供基于哈希表的unordered_map和unordered_set本质都是围绕解决BST退化问题这一目标展开的。我在学习BST时的一个建议是先把普通BST写熟理解它为什么退化然后立刻去研究平衡树你会对旋转操作有一种原来如此的顿悟。如果上来就啃红黑树大概率会被复杂的颜色调整绕晕。另外提一个我在实际项目中遇到的场景如果你知道自己会按时间戳顺序持续插入大量数据比如日志记录建议不要用普通BST直接用有序容器或者平衡树。否则随着数据量增加树的深度会越来越深程序从卡顿到崩溃的节奏会非常生动。6. 常见问题与调试技巧实录6.1 返回值没有覆盖根节点指针前面我反复强调过插入和删除函数如果返回更新后的根节点调用处一定要用返回值更新root。最常见的错误是只调用insertRec但不接收返回值。错误示范insertRec(root, val); // 这样写插入结果丢失正确示范root insertRec(root, val);这个错误的表现非常隐蔽插入少数几个节点时可能碰巧正确因为那些操作修改的是子节点指针但当插入操作需要改变根节点时比如空树插入第一个节点程序就彻底坏了。排查方法写一个打印树结构的函数或者用中序遍历结果对比看缺失的元素是不是恰好是那些应该被挂在根位置的元素。6.2 递归删除时的空指针问题递归删除最容易在情况二上栽跟头。如果节点只有右孩子你执行node node-right后原节点被delete。但如果之前有代码保存了这个节点的指针那它就成了悬空指针。复查一下代码BSTNodeT* tmp node; node node-right; delete tmp;这里先保存old指针再把上级指针指向右孩子最后释放old。顺序不能反。如果先把node保存到tmp然后删除tmp再赋值node node-right此时node-right已经是野指针了。这个顺序是很多内存错误的根源。6.3 使用中序序列辅助验证算法正确性调试BST最质朴也最有效的方式就是用中序遍历序列检查有序性。我推荐每次写完核心操作都跑一遍下面的测试用例int main() { BSTint tree; std::vectorint values {5, 3, 8, 1, 4, 7, 9, 2, 6}; for (int v : values) { tree.insert(v); } std::vectorint out; tree.inorder(out); // 期望输出: 1 2 3 4 5 6 7 8 9 for (int v : out) { std::cout v ; } std::cout std::endl; tree.erase(3); tree.erase(5); tree.erase(9); std::vectorint out2; tree.inorder(out2); // 期望输出: 1 2 4 6 7 8 for (int v : out2) { std::cout v ; } std::cout std::endl; return 0; }每次增删后重新跑一遍中序输出如果序列递增没问题基本可以断定树结构没有崩溃。这个方法比debugger逐行跟踪高效得多。6.4 重复值处理策略的统一性重复值处理策略必须贯穿所有操作不能插入时去重删除时又期望重复值存在。我推荐最简单的策略——插入时遇到重复值直接忽略返回false删除时删除其中一个即可。如果你需要支持多重集合即允许重复那就在节点里加一个count字段插入时count删除时count--count归零才真正删除节点。这比插入两个相同值的节点干净得多因为同样的值在BST里物理上只占一个节点的位置搜索、遍历的逻辑都不需要额外改动。6.5 深拷贝与内存管理一个极其容易被忽视的问题如果遇到拷贝构造和赋值操作直接用编译器默认生成的版本两个BST对象会共享同一块动态内存。析构时双删导致崩溃。解决方案是写深拷贝构造函数或者干脆删除拷贝操作只允许移动BST(const BST other) { root clone(other.root); size_ other.size_; } BST(BST other) noexcept : root(other.root), size_(other.size_) { other.root nullptr; other.size_ 0; } BST operator(BST other) { swap(root, other.root); swap(size_, other.size_); return *this; } ~BST() { clearRec(root); }其中clone递归复制每个节点clearRec递归释放每个节点。C的Rule of Three在这里体现得淋漓尽致析构函数、拷贝构造函数、拷贝赋值运算符必须同时出现。这里有个小技巧copy-and-swap惯用法里传入的是按值传递的other拷贝发生在参数构造阶段赋值操作内部直接交换指针既安全又简洁。7. 扩展方向与我的体会BST学完之后后面其实还有一座大山——平衡树总族。AVL树是最容易理解的平衡方案通过左旋、右旋、双旋维持每个节点的平衡因子绝对值不超过1。红黑树则是STL实际使用的方案它的约束更弱但实现更复杂背后是工程实践中写操作性能与查询性能的权衡。如果方向是刷算法题BST相关的题目也相当丰富验证是否是BST注意只递归比较左右孩子是不够的还要维护上下界、BST的中序迭代器、二叉搜索树转双向链表、恢复一棵被交换了两个节点的BST等等。这些题目本质都是对BST性质的运用把中序遍历和递归这两个工具玩溜了基本可以应付。我个人觉得学BST最大的价值不仅是掌握一种数据结构更是理解有序性与动态维护如何兼顾。数组和有序数组只能二选一而BST用一套节点结构同时解决动态插入删除和快速查找这种思路在工程里的延伸到处都是数据库的索引结构、内存分配器的空闲块管理、编译器符号表的组织……只要能想到需要支持动态集合操作且要求有序的场景都可以套用BST或其变体。写这篇文章的过程中我反复回忆自己刚学BST时踩过的坑——返回值不接收、指针引用弄错、忘记delete、复制对象后双删诸如此类。这些坑其实并不深但每一个都能让你调试半宿。希望这篇文章能帮你少走一段弯路。如果后面有空我会继续写AVL树和红黑树的实现笔记把平衡旋转的细节也一并拆开讲清楚。 二叉搜索树(BST)核心原理与C++实现：插入、删除、查找全解析
1. 二叉搜索树到底解决了什么问题1.1 从数组和链表的性能瓶颈说起先抛一个老生常谈但确实扎心的问题我们要维护一个动态集合支持插入、删除、查找三种操作用什么结构最舒服数组的查找快O(1)随机访问但插入和删除要搬动大量元素平均O(n)。链表的插入和删除倒是O(1)前提是已经知道位置但查找得从头遍历平均O(n)。有序数组能通过二分查找把搜索降到O(log n)可一旦涉及插入和删除数组的劣势立刻暴露——你插入一个元素到有序数组中间后面所有元素都要后移。也就是说在二叉搜索树Binary Search TreeBST出现之前没有一个结构能同时把插入、删除、查找都维持在较好的效率上。BST的核心价值就在这里它利用节点之间的大小关系把查找目标值从线性扫描转化为沿着树的路径走每一步都能排除掉一半的搜索空间。我曾跟刚学数据结构的朋友开玩笑说BST就是把二分查找的有序数组这层壳子拆掉换成了一套指针结构让插入和删除不再需要搬动数据。这套指针结构保留了二分查找的高效路径这就是它被称作二叉搜索树而不是二叉排序树的根本原因——它的搜索性质是第一位的。1.2 BST的核心性质与二分思想的落地BST的定义并不复杂每个节点最多有两个孩子左子树中的所有节点值都小于根节点值右子树中的所有节点值都大于根节点值并且左右子树本身也各自满足同样的条件。这个递归定义才是关键。你看这个性质天然就让比较大小这个操作变成了前进路标如果当前节点值大于目标值目标只可能出现在左子树小于则去右子树等于就直接命中。这里有一点容易被忽略BST的有序体现在中序遍历结果是一个严格递增序列。也就是说如果我们对一棵BST做中序遍历左子树、根、右子树拿到的是一串从小到大排列的值。这个特性在后面做校验、调试、甚至设计迭代器时都会用上建议先记在心里。我在实际刷题和工程编码中还有个体会BST的所有操作都依赖同一个比较函数。如果你想支持自定义类型或者排序规则直接替换这个比较逻辑就行整体框架不用动。这一点在后面的类设计里我会再次强调。2. 动手前的设计节点结构与类接口2.1 节点结构体怎么定义最顺手代码风格这件事每个人都有习惯但BST节点结构体我建议尽量精简、通用别塞太多跟树操作无关的字段。一个标准节点只需要三样东西值、左孩子指针、右孩子指针。泛型版本还要多一个模板参数。template typename T struct BSTNode { T value; BSTNode* left; BSTNode* right; explicit BSTNode(const T val) : value(val), left(nullptr), right(nullptr) {} };构造函数我习惯写成explicit避免隐式转换引发奇怪的编译问题。值用const引用传递是为了避免值拷贝浪费对于类似string这样的类型尤其明显。有些教材会在节点里加一个parent指针方便实现迭代器和非递归删除。但工程上我很少默认加它原因有二第一parent指针会让节点的生命周期管理变得复杂左右旋、删除时需要同步维护的指针数量翻倍第二递归写法根本不需要parent也能实现全部操作。加了parent调试的时候反而更容易懵。如果后续需要实现迭代器再动态加一个带parent的版本也不迟。2.2 类接口设计哪些方法必须有哪些可以偷懒类的对外接口我一般按必须提供和可选提供两档来划分。作为一个能被实际使用的容器BST至少应该支持以下几类操作插入insert(const T)删除erase(const T) 或 erase(const T) 返回是否删除成功查找contains(const T) 返回bool或者find返回迭代器/指针遍历中序遍历用于数据有序输出和验证辅助信息size()返回节点个数empty()判断空树很多教材喜欢把删除设计成返回bool因为用户删除一个不存在的值时他需要得到反馈。查找返回bool通常也够用如果你需要找到目标节点后修改它的值这种操作那find得返回节点指针我会单独提供一个findNode接口。类内部的核心实现我推荐把对节点的操作封装成私有递归函数对外只暴露简洁的接口。为什么因为递归函数天然需要一个以某个节点为根的子树作为参数而对外接口不应该暴露根节点指针。接口和实现分离改动内部实现时不影响调用方这是C工程里最基本的封装素养。template typename T class BST { public: BST() : root(nullptr), size_(0) {} void insert(const T val) { root insertRec(root, val); } bool erase(const T val) { return eraseRec(root, val); } bool contains(const T val) const { return findRec(root, val) ! nullptr; } void inorder(std::vectorT out) const { inorderRec(root, out); } size_t size() const { return size_; } bool empty() const { return root nullptr; } private: BSTNodeT* root; size_t size_; // 私有递归函数声明... };这里有个细节值得提醒insert和erase的返回值都覆盖了root。这个习惯非常重要因为当你在空树中插入第一个节点或者删除根节点时根节点指针会被修改。如果你只用局部变量接收返回值而不更新root你会发现插入了节点但树还是空的或者删除了根节点之后树整个丢失。这是新手写BST最容易踩的坑没有之一。3. 插入和查找构建与查询的核心路径3.1 插入操作非递归写法实战插入操作是BST最基础的操作之一我先给出非递归版本。非递归的好处是栈空间不增长对于树很高的场景更安全而且不用考虑递归函数返回值如何传回上层的问题。template typename T void BSTT::insertIter(const T val) { BSTNodeT* newNode new BSTNodeT(val); if (root nullptr) { root newNode; size_; return; } BSTNodeT* cur root; BSTNodeT* parent nullptr; while (cur ! nullptr) { parent cur; if (val cur-value) { cur cur-left; } else if (val cur-value) { cur cur-right; } else { delete newNode; // 重复值不做插入 return; } } if (val parent-value) { parent-left newNode; } else { parent-right newNode; } size_; }这段代码的核心逻辑是先通过循环找到目标插入位置循环结束时cur为空但parent保存了最后一个非空节点这个节点就是新节点的父亲。然后再比较一次新值和parent的值决定挂在左边还是右边。注意我处理了重复值的情况——如果待插入的值在树中已经存在直接放弃插入释放新节点的内存避免内存泄漏。关于重复值的处理策略其实可以讨论有人喜欢左边放小于等于右边放大于形成左闭右开的性质这样插入相同值时能保持稳定顺序。但作为集合容器默认语义就是元素唯一我建议做成去重。这个非递归版本有一个隐含假设树中节点的比较运算符定义正确。如果T是自定义类型记得重载和或者用仿函数/函数对象替代直接比较否则编译和运行都会出问题。3.2 查找操作从根到目标的路径查找的逻辑跟插入很像但少了一个记录parent的步骤因为查找只需要返回最终节点不需要知道它的父亲是谁。递归版本写出来极其简洁template typename T BSTNodeT* BSTT::findRec(BSTNodeT* node, const T val) const { if (node nullptr) return nullptr; if (val node-value) return node; if (val node-value) return findRec(node-left, val); return findRec(node-right, val); }三步走当前节点为空说明没找到当前值等于目标值直接返回否则根据大小关系走左或右。这个函数的时间复杂度是O(h)h是树高。我在LeetCode上做题时发现很多人执着于把所有查找都改成非递归但其实这里的递归深度在最坏情况下也就是树高而普通场景下插入的树高度一般远小于节点数栈溢出风险很低。与其牺牲可读性做非递归不如把精力放在后续的删除和旋转这些真正复杂的地方。查找还有一个工程上的细节如果BST存放的是对象而不是简单类型直接比较整个对象可能开销较大。某些高性能场景会用键值分离即节点存一个key用于比较和一个value用于存储这就是map和set的差别了。不过对于本文的入门级别直接存T就够了。3.3 中序遍历验证BST正确性的最好工具中序遍历代码很简短但它是验证整棵树是否正确的金牌工具。template typename T void BSTT::inorderRec(BSTNodeT* node, std::vectorT out) const { if (node nullptr) return; inorderRec(node-left, out); out.push_back(node-value); inorderRec(node-right, out); }为什么说它是验证工具因为BST的中序遍历结果必须严格递增。插入之后再中序输出一遍看看序列是否从小到大排列就能快速发现插入逻辑里挂错左右子树的问题。删除之后再中序输出一遍可以确认删除没有破坏树的有序性。我习惯在写完插入、删除后立刻用中序序列做回归验证。比如插入 {5, 3, 8, 1, 4, 7, 9}中序输出应该是 1, 3, 4, 5, 7, 8, 9。如果输出不是严格递增说明代码有bug。这个方法比肉眼盯着节点指针靠谱得多尤其是在删除操作涉及子树拼接的时候。4. 删除操作BST中最容易翻车的环节4.1 三种情况从简单到复杂删除操作是BST的核心难点原因在于被删除的节点可能带有一个或两个孩子直接拔掉会让子树失联。教科书通常把删除分成三种情况情况一叶子节点。没有孩子直接释放内存父节点对应指针置空即可。最简单最没有歧义。情况二只有一个孩子。把当前节点删除让它的父节点直接指向它的唯一孩子。相当于链表删除中间节点。情况三有两个孩子。这是最麻烦的。你无法直接把当前节点摘掉因为摘掉后左右子树都失去连接。标准做法是找到当前节点的中序前驱左子树中最大值或中序后继右子树中最小值用前驱/后继的值把当前节点的值覆盖掉然后递归删除那个前驱/后继节点。因为前驱/后继节点必然最多只有一个孩子删除问题就退化成了情况一或情况二。理解第三种情况的精髓在于直接删一个拥有两个孩子的节点是做不到的但我们可以偷梁换柱——用另一个更简单的节点替换它再去删除那个简单节点。树的节点总数减一但是被真正物理删除的节点不是名义上被删的值所在的节点。举个例子删除下面这棵树的根节点88 / \ 3 10 / \ \ 1 6 14根节点8有两个孩子。我们找左子树的最大值6或者右子树的最小值10把6的值覆盖到根节点上然后递归删除左子树里的节点6。最终得到6 / \ 3 10 / \ 1 14注意这里节点的值变了但是树的结构调整很少其他节点之间的父子关系几乎不受影响。这就是用前驱/后继替换的意义——尽量减少结构调整。4.2 前驱与后继的选择策略找前驱左子树最大值从当前节点的左孩子出发一路向右走到黑最后一个节点就是左子树中的最大值。找后继右子树最小值从当前节点的右孩子出发一路向左走到黑。用前驱还是用后继理论上是等价的没有优劣之分。我的习惯是固定用前驱左子树最大值因为实现起来只需一个循环。也有资料推荐交替使用前驱和后继说这样能避免树在某些特殊输入下退化得过于严重。这个说法在工程上效果存疑因为删除本身对树的形态影响远不如插入大我一般不折腾。有一个坑必须提当你用前驱值覆盖当前节点后要删除的是左子树中那个前驱节点。如果左子树的前驱节点恰好是当前节点的左孩子即左孩子没有右子树那么递归删除时要正确处理parent指针。如果没写对可能出现左孩子指针悬空或者指向错误的情况。4.3 递归删除的完整实现递归删除是写起来最干净、也最容易出bug的版本。下面给出完整代码配合注释逐行解释template typename T bool BSTT::eraseRec(BSTNodeT* node, const T val) { if (node nullptr) { return false; // 没找到 } if (val node-value) { return eraseRec(node-left, val); } else if (val node-value) { return eraseRec(node-right, val); } // 找到目标节点开始删除 if (node-left nullptr node-right nullptr) { // 情况一叶子节点 delete node; node nullptr; --size_; } else if (node-left nullptr) { // 情况二只有右孩子 BSTNodeT* tmp node; node node-right; delete tmp; --size_; } else if (node-right nullptr) { // 情况二只有左孩子 BSTNodeT* tmp node; node node-left; delete tmp; --size_; } else { // 情况三两个孩子都有 BSTNodeT* predecessor findMax(node-left); node-value predecessor-value; eraseRec(node-left, predecessor-value); } return true; }这个实现的精妙之处在于删除函数接收的是指向指针的引用BSTNode * node这样当上层调用eraseRec(node-left, val)时函数内部对node的赋值比如node node-right会直接修改上层node-left指针本身而不是修改指针的副本。这段话可能有点绕换个说法如果参数是指针的引用那么node nullptr这句话会真正把父节点的左/右孩子指针置空如果参数只是指针副本这句话只会把副本置空真正挂在树上的指针纹丝不动这就是经典的指针传参丢失修改问题。需要配套实现的辅助函数findMaxtemplate typename T BSTNodeT* BSTT::findMax(BSTNodeT* node) const { while (node-right ! nullptr) { node node-right; } return node; }这段删除逻辑还有一个容易忽略的点情况三找到前驱后用前驱值覆盖当前节点值然后递归删除前驱节点。我需要确保左子树中前驱节点被正确删除且当左子树为空时不会出问题。仔细看代码能走到情况三说明左右孩子都存在findMax(node-left)一定不会返回nullptr所以eraseRec(node-left, predecessor-value)一定会进入找到目标的分支不会走到第一行的nullptr判断。这就是递归调用安全性的来源。5. 复杂度分析与退化问题5.1 平均情况下的复杂度先给结论对于一棵随机的BST即节点按随机顺序插入查找、插入、删除的平均时间复杂度都是O(log n)其中n是节点总数。为什么是O(log n)而不是O(1)因为BST每次比较都能排除掉当前子树的一半在理想情况下。如果树是平衡的枚举一条从根到叶子的路径最多走树高步树高约为log2(n)。每一步做常数时间的比较操作所以总复杂度是O(log n)。中序遍历是O(n)因为它需要访问每一个节点这个无法避免。空间复杂度方面BST本身需要O(n)存储节点。递归实现的插入、查找、删除都有隐式栈空间开销最坏情况下递归深度等于树高也是O(h)。5.2 有序插入引发的退化问题BST最大的坑不是操作逻辑而是树的形态完全取决于插入顺序。如果你按升序插入 1, 2, 3, 4, 5, 6, ...这棵树会退化成一个完全向右倾斜的链表1 \ 2 \ 3 \ 4 \ 5此时树高h n查找时间复杂度从O(log n)恶化到O(n)。换句话说BST在最坏情况下并不比链表强多少。这个问题怎么破业界主流做法是引入平衡机制让树在插入、删除后自动调整形态保证树高始终接近O(log n)。这就是AVL树、红黑树等平衡二叉搜索树存在的原因。STL里的std::map和std::set底层用的是红黑树C11之后还提供基于哈希表的unordered_map和unordered_set本质都是围绕解决BST退化问题这一目标展开的。我在学习BST时的一个建议是先把普通BST写熟理解它为什么退化然后立刻去研究平衡树你会对旋转操作有一种原来如此的顿悟。如果上来就啃红黑树大概率会被复杂的颜色调整绕晕。另外提一个我在实际项目中遇到的场景如果你知道自己会按时间戳顺序持续插入大量数据比如日志记录建议不要用普通BST直接用有序容器或者平衡树。否则随着数据量增加树的深度会越来越深程序从卡顿到崩溃的节奏会非常生动。6. 常见问题与调试技巧实录6.1 返回值没有覆盖根节点指针前面我反复强调过插入和删除函数如果返回更新后的根节点调用处一定要用返回值更新root。最常见的错误是只调用insertRec但不接收返回值。错误示范insertRec(root, val); // 这样写插入结果丢失正确示范root insertRec(root, val);这个错误的表现非常隐蔽插入少数几个节点时可能碰巧正确因为那些操作修改的是子节点指针但当插入操作需要改变根节点时比如空树插入第一个节点程序就彻底坏了。排查方法写一个打印树结构的函数或者用中序遍历结果对比看缺失的元素是不是恰好是那些应该被挂在根位置的元素。6.2 递归删除时的空指针问题递归删除最容易在情况二上栽跟头。如果节点只有右孩子你执行node node-right后原节点被delete。但如果之前有代码保存了这个节点的指针那它就成了悬空指针。复查一下代码BSTNodeT* tmp node; node node-right; delete tmp;这里先保存old指针再把上级指针指向右孩子最后释放old。顺序不能反。如果先把node保存到tmp然后删除tmp再赋值node node-right此时node-right已经是野指针了。这个顺序是很多内存错误的根源。6.3 使用中序序列辅助验证算法正确性调试BST最质朴也最有效的方式就是用中序遍历序列检查有序性。我推荐每次写完核心操作都跑一遍下面的测试用例int main() { BSTint tree; std::vectorint values {5, 3, 8, 1, 4, 7, 9, 2, 6}; for (int v : values) { tree.insert(v); } std::vectorint out; tree.inorder(out); // 期望输出: 1 2 3 4 5 6 7 8 9 for (int v : out) { std::cout v ; } std::cout std::endl; tree.erase(3); tree.erase(5); tree.erase(9); std::vectorint out2; tree.inorder(out2); // 期望输出: 1 2 4 6 7 8 for (int v : out2) { std::cout v ; } std::cout std::endl; return 0; }每次增删后重新跑一遍中序输出如果序列递增没问题基本可以断定树结构没有崩溃。这个方法比debugger逐行跟踪高效得多。6.4 重复值处理策略的统一性重复值处理策略必须贯穿所有操作不能插入时去重删除时又期望重复值存在。我推荐最简单的策略——插入时遇到重复值直接忽略返回false删除时删除其中一个即可。如果你需要支持多重集合即允许重复那就在节点里加一个count字段插入时count删除时count--count归零才真正删除节点。这比插入两个相同值的节点干净得多因为同样的值在BST里物理上只占一个节点的位置搜索、遍历的逻辑都不需要额外改动。6.5 深拷贝与内存管理一个极其容易被忽视的问题如果遇到拷贝构造和赋值操作直接用编译器默认生成的版本两个BST对象会共享同一块动态内存。析构时双删导致崩溃。解决方案是写深拷贝构造函数或者干脆删除拷贝操作只允许移动BST(const BST other) { root clone(other.root); size_ other.size_; } BST(BST other) noexcept : root(other.root), size_(other.size_) { other.root nullptr; other.size_ 0; } BST operator(BST other) { swap(root, other.root); swap(size_, other.size_); return *this; } ~BST() { clearRec(root); }其中clone递归复制每个节点clearRec递归释放每个节点。C的Rule of Three在这里体现得淋漓尽致析构函数、拷贝构造函数、拷贝赋值运算符必须同时出现。这里有个小技巧copy-and-swap惯用法里传入的是按值传递的other拷贝发生在参数构造阶段赋值操作内部直接交换指针既安全又简洁。7. 扩展方向与我的体会BST学完之后后面其实还有一座大山——平衡树总族。AVL树是最容易理解的平衡方案通过左旋、右旋、双旋维持每个节点的平衡因子绝对值不超过1。红黑树则是STL实际使用的方案它的约束更弱但实现更复杂背后是工程实践中写操作性能与查询性能的权衡。如果方向是刷算法题BST相关的题目也相当丰富验证是否是BST注意只递归比较左右孩子是不够的还要维护上下界、BST的中序迭代器、二叉搜索树转双向链表、恢复一棵被交换了两个节点的BST等等。这些题目本质都是对BST性质的运用把中序遍历和递归这两个工具玩溜了基本可以应付。我个人觉得学BST最大的价值不仅是掌握一种数据结构更是理解有序性与动态维护如何兼顾。数组和有序数组只能二选一而BST用一套节点结构同时解决动态插入删除和快速查找这种思路在工程里的延伸到处都是数据库的索引结构、内存分配器的空闲块管理、编译器符号表的组织……只要能想到需要支持动态集合操作且要求有序的场景都可以套用BST或其变体。写这篇文章的过程中我反复回忆自己刚学BST时踩过的坑——返回值不接收、指针引用弄错、忘记delete、复制对象后双删诸如此类。这些坑其实并不深但每一个都能让你调试半宿。希望这篇文章能帮你少走一段弯路。如果后面有空我会继续写AVL树和红黑树的实现笔记把平衡旋转的细节也一并拆开讲清楚。