树系列第 7 篇：二叉搜索树——查找、插入与删除

欢迎来到“树系列”第 7 篇。前六篇文章里，我们做了一件非常重要的事：把树从“形状”到“走法”完整地研究了一遍。第 1 篇回答了为什么需要树，第 2 篇把节点、边、根、叶子、深度、高度这些术语逐个钉死，第 3 篇认识了二叉树，第 4 篇讨论了树的存储方式，第 5 篇把前序、中序、后序三种深度优先遍历讲透，第 6 篇又用队列实现了层序遍历。可以说，我们已经学会“看树”和“走树”了。但看树、走树都不是目的，真正的目的是用树做事情。今天，我们就要让树第一次发挥它最核心的价值——快速查找。而做到这一点的树，就是本系列的绝对主角之一：二叉搜索树（Binary Search Tree，简称 BST）。

二叉搜索树是计算机科学里最重要的数据结构之一。它把“有序数组的二分查找”和“链式二叉树的灵活插入”两件事合在了一起：既保留了二分查找那种“每次砍掉一半”的威力，又解决了有序数组插入、删除需要大量搬移元素的问题。数据库的索引、编译器的符号表、操作系统里的内存管理、各种集合与映射的实现，背后都有 BST 或它的亲戚（AVL 树、红黑树、B 树）的身影。如果把树系列比作一部连续剧，前六篇是铺垫人物和场景，这一篇就是主角正式登场的第一集。

本篇的路线图如下：先从有序数组的二分查找讲起，建立“每次砍一半”的直觉；然后给出 BST 的严格定义，并解释一个非常容易踩坑的点——BST 的序关系是“全局的”而不是“局部的”；接着用上一篇刚学过的中序遍历证明 BST 的一个魔法性质：中序遍历的结果就是从小到大；之后分别实现查找、插入、删除三个核心操作，删除的三种情况是重头戏，我们会用图解把“叶子直接删、一个孩子让孩子顶上、两个孩子用前驱或后继替换”完整走一遍；再给出平均 O(log n)、最坏 O(n) 的复杂度分析；然后看 BST 的五个经典应用，包括范围查询、第 k 小、BST 排序，以及与二分查找、哈希表的对比；最后预告 AVL 树与红黑树（第 9–12 篇）如何解决 BST 的退化问题。文章末尾还有一张操作复杂度速查表和七道自测题。如果你在查找实验室里玩过搜索动画，会发现那里面最核心的树，正是本篇的主角。

0 先把前六篇的结论捡回来

照例，正式出发之前先清点装备。第一，树由节点和边组成，有唯一的根节点，除根之外每个节点有且只有一个父亲，没有孩子的节点叫叶子，一个节点和它的全部后代合在一起叫子树。第二，二叉树的每个节点最多有两个孩子，左孩子和右孩子是两个不同的位置，即使某个位置空着，它依然存在；二叉树可以递归地定义为“空树，或者由一个根节点和左右两棵二叉树构成”。第三，存储：本篇代码沿用第 4 篇的链式存储，每个节点保存自己的值、左孩子指针、右孩子指针；查找、插入、删除都沿着指针走，所以它们的时间和树的“高度”直接挂钩。第四，中序遍历：第 5 篇讲过，“左根右”的中序遍历在 BST 上会得到有序序列，本篇要把这个结论证明给你看，并把它当成 BST 的“验算器”。第五，层序遍历：第 6 篇的 BFS 用于逐层扫描，本篇主要用它来检查树的形状，比如判断一棵树是否退化成了“链”。

还有一个术语需要提前统一：本系列第 5、6 篇反复出现“二叉搜索树”这个词，但一直没有给出正式定义。现在正式登场。本篇里，“BST”三个字母就代表“二叉搜索树（Binary Search Tree）”。我们讨论的 BST 都是二叉树，节点只存一个可比较的键（key），为了方便讲解，示例统一用整数；实际应用中键可以是字符串、日期或者任意定义了比较规则的对象。

1 从有序数组的二分查找讲起

1.1 你早就会的“猜数字”游戏

先来玩一个你肯定玩过的游戏：我心里想了一个 1 到 100 之间的整数，你每次猜一个数，我告诉你“大了”还是“小了”，你怎样才能用最少的次数猜中？稍有经验的人都会说：先猜 50。如果大了，答案在 1 到 49 之间；如果小了，答案在 51 到 100 之间。无论哪种情况，你都把候选范围砍掉了一半。接着在剩下的范围里继续猜中间值，比如答案是“大了”，就猜 25；再比如“小了”，就猜 75。每猜一次，范围缩小一半。最多猜多少次？100 个数，第一次剩下 50 个，第二次 25 个，第三次 13 个，第四次 7 个，第五次 4 个，第六次 2 个，第七次 1 个。也就是说，最多 7 次就能猜中 100 个数里的任何一个。如果范围扩大到 100 万个，也只需要约 20 次——因为 2 的 20 次方约等于 100 万。这就是二分思想的力量：每走一步，把问题规模砍掉一半，所以总步数是 log₂n 级别。

猜数字游戏其实就是一个查找问题：在 1 到 100 这 100 个“有序元素”里，找到目标值。它之所以高效，靠的是两个条件：第一，候选集合是有序的，所以“和中间值比较”这个动作能告诉我们答案落在左半边还是右半边；第二，我们手里有“中间值”，能立刻把集合切成两半。把这两个条件翻译成计算机语言，就是有序数组上的二分查找（Binary Search）：维护一个左边界 left 和一个右边界 right，每次取中间位置 mid，把目标值和 array[mid] 比较；等于就返回，小于就在左半边继续，大于就在右半边继续。每轮比较都把区间长度减半。

下面这张图展示了在有序数组 [10, 20, 30, 40, 50, 60, 70, 80] 里查找 35 的过程。每一步，灰色区域是被砍掉的一半，带边框的格子是本次比较的中间值：

注意最后一步：当区间缩小到只剩一个位置时，还要再比较一次才能确定“有没有”。二分查找的结束条件有两个：要么在某个 mid 处命中目标，返回下标；要么 left 越过 right，区间变空，说明目标不存在。“找不到”不是一个例外情况，而是查找的正常出口之一，这个思想在 BST 查找里会原样保留。

1.2 二分查找的代价：有序数组的“原罪”

二分查找这么好，那是不是把数据放进有序数组就万事大吉了？不是。数组有两个尴尬之处。第一个尴尬是插入慢：要把一个新值插进有序数组的正确位置，需要先找到位置（可以用二分查找，O(log n)），然后把从该位置到末尾的所有元素都往后挪一格（O(n)）。挪元素是数组的物理定律——数组是一段连续内存，中间没有“空位”，插入必须腾地方。第二个尴尬是删除慢：删掉一个元素后，后面的所有元素要往前挪一格，同样是 O(n)。查找 O(log n)，插入 O(n)，删除 O(n)——如果你面对的是一批“只查不改”的静态数据，这个组合非常优秀；但现实世界的数据几乎都会变：通讯录要加人、库存要增减、词典要收录新词。一旦数据频繁变化，数组就力不从心了。

链表能解决插入删除的麻烦吗？双向链表插入删除一个已知节点只需要 O(1) 的指针操作，听起来很诱人。但链表里找不到“中间值”：要取第 k 个元素必须从头走 k 步，二分查找在链表上彻底失效，查找退化成从头到尾的 O(n) 线性扫描。于是我们陷入了一个两难：数组擅长“跳到中间”但不擅长“在中间开口子”，链表擅长“在中间开口子”但不擅长“跳到中间”。能不能设计一种结构，既有“跳一半”的能力，又有“开口子”的灵活？

答案正是树。想象一下：二分查找的每一次比较，其实都在做一个二选一的决定——目标在左半边，还是右半边？如果把“在区间 [1,100] 里查找”的整个决策过程画下来，会得到一棵天然的二叉树：根节点是 50，左孩子是 25，右孩子是 75，再往下是 12、37、62、87……树的形状和二分查找的决策树一模一样。二叉搜索树，就是把这张“决策树”从抽象画变成真实的数据结构：不再维护一个数组和两个边界，而是直接把每个“中间值”存成一个节点，把“左半边”和“右半边”变成它的左子树和右子树。

1.3 BST：把二分查找“物化”成树

为了把话说得更具体，我们从空树开始，依次插入 50、30、70、20、40、60、80 这 7 个数。如果每次插入都遵守“比当前节点小走左边，比当前节点大走右边，遇到空位就放下”，最终会得到下面这棵树：

请先感受这棵树的两个特点。第一，它是一棵二叉树，每个节点最多两个孩子。第二，它“有序”：50 的左子树是 30、20、40，全部小于 50；50 的右子树是 70、60、80，全部大于 50；再看 30，它的左子树只有 20，小于 30，右子树只有 40，大于 30。整棵树处处都满足“左小右大”。有了这个性质，查找某个值就可以像二分查找一样走：要找 60，先到根 50，60 比 50 大，于是只进右子树；到了 70，60 比 70 小，只进左子树；到了 60，命中。整个过程只走了 3 个节点（50、70、60），完全没有碰左子树的 30、20、40。“向左还是向右”这个决定，替我们砍掉了整棵无关的子树。

再看插入：要插入 35，从根 50 出发，35 < 50 走左；到 30，35 > 30 走右；到 40，35 < 40 走左；40 没有左孩子，于是 35 作为 40 的左孩子挂上去。插入只需要沿着一条路径找到空位，然后“开口子”挂一个新节点——这正是链表擅长的指针操作，不需要像数组那样搬移任何元素。二分查找的“快”和链表的“活”，在 BST 里合体了。这就是 BST 全部魅力的起点。

2 BST 的严格定义

2.1 一句话定义

二叉搜索树（BST）是一棵二叉树，并且满足：对于树中的任意一个节点，它的左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。 这个性质通常被称为二叉搜索树性质（BST Property）。

注意这句话里有三个关键词，每个都不能少。第一个关键词是“任意一个节点”——性质必须对树里每一个节点成立，不只是根节点。第二个关键词是“左子树中所有节点”——不是“左孩子”，而是左子树里上上下下全部节点。第三个关键词是“都小于 / 都大于”——是严格的、不分大小的“都”。把这三个关键词合起来，再对照我们那棵 7 个节点的示例树：根 50 的左子树（30、20、40）全部小于 50，右子树（70、60、80）全部大于 50；节点 30 的左子树（20）小于 30，右子树（40）大于 30；70 同样如此。性质处处成立，它才是一棵合法的 BST。

这个定义是递归的，和二叉树的递归定义天然咬合：一棵 BST 要么是空树，要么由一个根节点和左右两棵子树组成，其中左子树是一棵 BST 且左子树所有节点值都小于根，右子树是一棵 BST 且右子树所有节点值都大于根。为什么说“递归”很重要？因为它给了我们一套验证 BST 的方法：检查根是否满足“左子树全部小于根、右子树全部大于根”，然后递归检查左右子树是否各自是 BST。后面写代码时，你会看到这个定义几乎逐字翻译成函数。

2.2 全局性质 vs 局部性质：最经典的坑

初学者最容易犯的错误，是把 BST 性质理解成“局部”的——只比较父节点和它的两个孩子。比如下面这棵树，每个节点都比它的左孩子大、比右孩子小，看起来“左小右大”没毛病：

但仔细检查：60 位于 30 的右子树，而 60 大于根节点 50——它违反了“右子树中所有节点的值都大于该节点”吗？不，它违反的是左子树中所有节点都小于根：60 是根 50 的左子树（以 30 为根）里的节点，但它比 50 大。所以这棵树不是 BST。如果我们用查找算法来找 60：从根 50 出发，60 > 50，走向右子树 70；到了 70，60 < 70，走向左子树 55；55 没有右孩子，返回“找不到”。但 60 明明就在树里！树的局部样子看起来有序，全局却破坏了 BST 性质，导致查找算法直接“迷路”。

这个例子值得反复咀嚼，因为它揭示了 BST 查找正确的根本前提：只要任何节点的“左子树全部小于它、右子树全部大于它”被破坏，查找就可能漏掉真实存在的目标。这也是为什么第 5 篇反复强调中序遍历是 BST 的“验算器”——一棵树的 BST 性质成立，当且仅当它的中序遍历结果是严格递增的。这个等价关系我们马上会证明。

2.3 重复键怎么处理：先定约定

前面定义里说的是“小于”和“大于”，都是严格不等式，这意味着相等（重复）的键没有合法位置。实际应用中数据可能重复（同名的人、同分的学生、相同价格的商品），怎么处理？业界有几种约定，每种都有人用，重要的是在一套代码里始终如一。

约定一：不允许重复。把 BST 当作集合（Set）使用，插入时如果发现键已经存在，就不插入（或者更新值）。这是最简单、最常用的做法，也是本篇代码采用的约定。约定二：允许重复，全部放到一边。比如规定“小于走左，大于等于走右”，重复键会全部堆进右子树（或左子树）的某个角落；实现简单，但树容易“歪”，重复很多时查找会退化。约定三：每个节点保存一个计数。节点里除了键，再存一个 count 字段，插入重复键时 count 加一，删除时 count 减一；既保留了重复信息，又不改变树的形状。约定四：为每个键附加唯一标识（比如数据库主键），让键天然互不相同。数据库索引里常用这种思路。

本篇统一采用约定一：树中不存在两个相等的键，插入重复键时直接返回、不做任何修改。这样定义最干净，也最贴近算法面试与教材里的主流写法。等你理解了全部操作，再扩展成计数版不过是加一个字段的事。

2.4 从定义能立刻推出的三个推论

从定义出发，不写一行代码，我们就能推出三个重要推论。推论一：BST 中最小的节点一定在最左下角。因为任何节点的左子树都比它小，一路向左走到头，必然到达全树最小值；最大的节点一定在最右下角，一路向右走到头即可。推论一在删除操作里会用到——找“前驱”和“后继”就是沿着这个思路走的。推论二：任意节点的左子树里所有节点都小于它的右子树里所有节点。这从“左子树 < 根 < 右子树”直接传递而来。推论三：BST 的中序遍历结果严格递增。这是全篇第一个“魔法性质”，下一节专门证明。

这三个推论看起来都是定义的自然产物，但它们各自对应一个高频考点：求最小值、求最大值、判断一棵树是不是 BST。把定义吃透，这些题就都不是“新题”，而是定义的换装。

3 为什么中序遍历 = 从小到大

3.1 先看现象

把 BST 定义和中序遍历放在一起，会碰撞出一个近乎魔法的结论：对一棵 BST 做中序遍历，得到的序列一定严格递增（从小到大）。反过来，一棵二叉树的中序遍历结果严格递增，它一定满足 BST 性质。也就是说，“BST”和“中序有序”是同一枚硬币的两面。这个结论不是新知识，第 5 篇提到过，但那时我们只把它当作一个观察，现在有了定义，可以把它彻底证明明白。

先用我们那棵示例树验证一遍：节点依次是 50、30、70、20、40、60、80。中序遍历的规则是“左根右”：先遍历 50 的左子树，再访问 50，再遍历右子树。左子树以 30 为根，它的中序是“20、30、40”；右子树以 70 为根，它的中序是“60、70、80”。整棵树的中序就是 20、30、40、50、60、70、80——恰好从小到大。下面这张图把访问顺序直接标在节点上，序号 1 到 7 严格对应中序的每一步，你可以顺着序号把整棵树“重走”一遍：

注意观察一个细节：序号不是按“树从上到下”排的，而是按“值从左到右”排的。20 最小，序号 1；80 最大，序号 7。树的高矮不影响序号的相对关系，只影响“先走多深再访问”。这正是 BST 的精华：树的形状只决定“怎么走”，值的大小决定“什么时候访问”。

3.2 直觉证明

为什么一定是这样？直觉上非常清楚：中序遍历访问一个节点的时机，是“左子树全部访问完、右子树还没开始”的时候。而根据 BST 定义，左子树里所有节点的值都小于根，右子树里所有节点的值都大于根。所以中序序列的片段顺序必然是“左子树的序列、根、右子树的序列”，也就是“一堆比根小的、根、一堆比根大的”。只要左右子树各自也是 BST（递归定义保证），它们内部的中序序列也分别有序，于是整个序列自然从小到大。

这个证明可以写成严格的数学归纳，但理解层面只需要三步：第一，中序遍历对任意一棵树，都把“左子树全部节点”排在根前面、“右子树全部节点”排在根后面；第二，BST 保证左子树全部小于根、右子树全部大于根；第三，递归地看，每一棵子树内部也满足同样的规则，所以处处有序。三步拼起来，结论成立。

反过来也成立：如果一棵二叉树的中序遍历严格递增，那么任意一个节点在序列里的位置一定是“它的左子树节点们之后、右子树节点们之前”，因此它的左子树全部小于它、右子树全部大于它，BST 性质成立。中序有序，是 BST 性质的一个完全等价的说法。这个等价关系有非常实用的价值：判断一棵树是不是 BST，最省心的写法就是中序遍历一遍，检查结果是否严格递增；甚至不需要存整个序列，只要在遍历时记住“上一个访问的值”，发现当前值不大于上一个值就立刻判否。

3.3 中序有序性的三个用途

中序有序性不是用来欣赏的，它直接给了我们三件武器。第一件：排序。把一组数插进 BST，再中序遍历，得到的就是有序序列——这就是“BST 排序”的雏形，第 8 节会完整讨论。第二件：范围查询。想知道所有落在 [low, high] 之间的值，可以中序遍历整棵树逐个筛选，但更聪明的做法是利用 BST 性质剪枝：遇到一个节点，如果它的值小于 low，整棵左子树都不用看了；如果大于 high，整棵右子树都可以放弃。第三件：找第 k 小。既然中序遍历就是从小到大，那么中序遍历的第 k 个节点就是第 k 小的元素；配合“每个节点记录子树大小”的增强字段，可以把复杂度优化到 O(h)。第 8 节会给出具体代码。

还有一个小细节值得记住：中序序列是 BST 的“快照”，但一棵 BST 的中序序列无法唯一还原它的形状。7 个有序的数，可以组成很多棵不同的 BST（比如链状的、平衡的），它们的中序序列都是同一个。这意味着“中序 + 某个其他遍历”才能唯一重建树，这个主题树系列后面会专门展开。本篇只需要抓住：中序有序是 BST 的指纹，但不是 BST 的身份证。

4 查找：沿着有序的路径走下去

4.1 算法思想：每一步都是一个二分决策

BST 查找是最简单、也最能体现 BST 价值的操作。目标：给定一棵 BST 和一个键 key，找到这个键对应的节点（或者确认它不存在）。算法只有一句话：从根出发，把当前节点的值和 key 比较；相等就找到了，key 小就往左走，key 大就往右走；走到空节点还没找到，说明 key 不存在。

为什么这个算法正确？每一步的“向左走”都依赖 BST 性质：当前节点值比 key 大，那么当前节点左子树里“所有”节点都比 key 小？等等，这里要小心：当前节点值比 key 大，只能推出 key 不可能在当前节点右子树（右子树都比当前节点大，当然也比 key 大），而当前节点左子树里“可能”存在比 key 大、也可能存在比 key 小的节点。向左走只是“排除掉右子树”，不是“断定 key 在左子树”。同理，当前节点值比 key 小，向左走没有意义，因为左子树全部比当前节点小，也就全部比 key 小，key 只可能在右子树方向。所以每一步都是安全的排除：要么命中，要么把不可能含 key 的整棵子树丢掉。这正是二分查找的灵魂——比较的价值不在于“找到”，而在于“排除”。

4.2 图解：在示例树上查找 40

还是用那棵 7 节点示例树，查找 40。我们一步步走，同时记录“当前节点”的变化：

访问顺序是 50 → 30 → 40，一共比较 3 次，命中。请注意访问顺序在树上的实际形状：它不是“从上到下”的一整列，而是一串“之”字形的路径——先左拐，再右拐。下面这张图把路径上的节点高亮出来，并用箭头标出每一步的方向，旁边标上访问序号：

路径上只有 3 个节点，另外 4 个节点连碰都没碰。这就是“砍掉一半”在树上的体现：走到 50 时，向右就意味着 50 的左子树（30、20、40 里会有一部分被排除）……严格来说，到了 30 又向右走，30 的左子树 20 被排除。每一次比较都至少排除一整棵子树，被排除的节点越多，剩下的路径越短。

再看查找 35——一个不在树里的值：

访问顺序是 50 → 30 → 40 → 空。注意最后一步：35 和 40 比较之后要向左走，但 40 没有左孩子，于是直接判定“不存在”。这里的关键是：35 如果存在，唯一的藏身之处就是 40 的左子树；既然那里是空的，35 就必然不存在。查找失败的路径和查找成功的路径走法完全一样，区别只在于终点是“空位”而不是“目标节点”。这个“空位”的精确位置，正是下一节插入操作要找的位置——查找失败时停下的空位，就是新节点应该挂上去的地方。

4.3 代码：递归版与迭代版

先定义节点类型，和前面几篇保持一致，使用 TypeScript：

// 链式存储的二叉搜索树节点
type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};

递归版查找几乎是把定义逐字翻译：

// 递归查找：返回键对应的节点，找不到返回 null
function searchBST(root: TreeNode | null, key: number): TreeNode | null {
  if (root === null) return null;          // 走到空位：不存在
  if (key === root.val) return root;       // 命中
  if (key < root.val) {
    return searchBST(root.left, key);      // 去左子树找
  }
  return searchBST(root.right, key);       // 去右子树找
}

递归版只有三个分支：空节点返回 null、相等返回当前节点、小于走左、大于走右。它和“二分查找的递归版”几乎一一对应，只是把“区间中点”换成了“当前节点”。递归版的缺点和前几篇说过的一样：树很深时调用栈可能很大。迭代版用 while 循环，额外空间 O(1)：

// 迭代查找：同样的逻辑，不占用调用栈
function searchBSTIterative(root: TreeNode | null, key: number): TreeNode | null {
  let cur = root;
  while (cur !== null) {
    if (key === cur.val) return cur;
    cur = key < cur.val ? cur.left : cur.right;
  }
  return null;  // 走到空位，没找到
}

迭代版里那一行 cur = key < cur.val ? cur.left : cur.right 就是查找的全部“行走逻辑”：每次比较，要么左要么右，绝不分叉。这行代码看起来简单，但请反复读它——它同时是查找、插入、删除三条算法共同的“腿”。

4.4 找到与找不到：两个同等重要的出口

查找的结果只有两种：返回节点，或返回 null。工程上，返回 null 往往不是“错误”，而是“正常回答”——就像电话簿里没有这个号码一样。写代码时要注意两个边界：第一，空树：root 为 null，查找任何键都直接返回 null；第二，根就是目标：第一次比较就命中，路径长度为 1，这是最好的情况。

还有一种常见的增强需求：查不到时，希望知道“如果插入它，应该挂在哪个父亲下面”（为插入做准备），或者想知道“比它小的最大键 / 比它大的最小键”（前驱与后继，第 6 节删除时会用到）。这些都可以在查找过程中记录“最后一个经过的节点”来实现，本质上仍然是同一条路径。查找是 BST 的“读操作”，也是插入、删除这两个“写操作”的骨架——先学会找，后面的一切都水到渠成。

4.5 查找复杂度：先给结论，后面细算

查找的代价是路径长度：从根走到目标（或空位）经过的节点个数。路径长度取决于树的高度，而不是节点总数。理想情况下树接近平衡，高度约 log₂n，查找 O(log n)；最坏情况下树退化成一条链，高度 n，查找 O(n)。这个复杂度分析太重要了，第 7 节会专门展开，这里只需记住一句话：BST 查找快不快的真正决定因素，不是“有多少节点”，而是“树有多高”。

5 插入：找到空位，挂上新节点

5.1 算法思想：查找失败的地方就是家

插入操作的算法可以用一句非常浪漫的话概括：新节点想住进 BST，先假装自己要被查找——走到走不动的地方，那里就是它的家。更严谨的说法是：从根出发，沿着查找路径向下走，每当遇到一个节点，比较新值和节点值；小于走左、大于走右；当我们试图进入一个空子树时，就把新节点挂在这个空位上，插入完成。

为什么这样做一定能保持 BST 性质？关键在于查找路径的性质：路径上的每一个节点，都根据“新值在它的左子树还是右子树”做出了正确的方向选择，而且新值从未和任何节点相等（约定不允许重复）。当我们在节点 parent 的空左孩子位置挂上新节点时，新节点小于 parent，同时它也小于 parent 右子树的所有节点；它和 parent 左子树其他节点的大小关系呢？因为路径上是“从 parent 一路向左/右”到达空位的，空位所在子树的所有已有节点，都在路径上某个节点处被“更接近”地比较过——严格证明需要归纳，但直观上可以这样想：查找路径把整棵树划分成了“确定比新值大”和“确定比新值小”两个区域，空位恰好落在两个区域之间的边界上，新节点挂进去后，BST 性质依然成立。插入 BST 永远不会改变已有节点的相对位置，只会增加一片新叶子——这是 BST 插入和数组插入最大的不同，也是它 O(h) 的关键。

这里有一个非常重要的观察：新节点总是作为叶子插入。因为插入位置是查找失败时停下的空位，而空位的“父亲”是路径上最后一个非空节点，新节点没有孩子，就是一片叶子。这个观察在删除操作里会反过来用：删除叶子最简单，删除内部节点则要想办法“换成叶子或单孩子节点”。

5.2 图解：插入 35

继续用示例树，插入 35。目标树当前有 50、30、70、20、40、60、80，我们要把 35 放进去。先走查找路径：50（35 < 50，向左）→ 30（35 > 30，向右）→ 40（35 < 40，向左）→ 40 的左孩子为空，停！于是把 35 挂成 40 的左孩子。下面这张图展示了“找空位”的完整过程：

插入后的树变成下面这样。35 是 40 的左孩子，树仍然满足 BST 性质：35 大于 30（它在 30 的右子树里）、小于 40（它是 40 的左孩子）、小于 50（它在 50 的左子树里）、小于 70（整体在 70 的左子树方向）……处处都对：

插入 35 的完整路径是 50 → 30 → 40 → 空位；这条路径之外的每一棵子树都原封未动，这正是“插入只影响一条路径”的直观证据。

注意 35 的“邻居”40 和 30：35 正好夹在 30 和 40 之间。这正是 BST 的精妙之处——每个新节点都会被放到它的有序位置上，就像自动排队的精灵。

5.3 手算多轮插入：看一棵树慢慢长出来

只插一个节点太轻松了，我们来点硬核的：从空树开始，按顺序插入 50、30、70、20、40、60、80、35、45、65，每一轮都画出当前的树。这是理解“插入 = 查找 + 挂叶子”最好的训练。

第 1 轮，插入 50：树为空，50 直接成为根。

第 2 轮，插入 30：从根 50 出发，30 < 50，向左；50 没有左孩子，30 成为 50 的左孩子。

第 3 轮，插入 70：70 > 50，向右；50 没有右孩子，70 成为 50 的右孩子。现在树长成了“根 50，左 30，右 70”的对称形状。

第 4 轮，插入 20：50 → 左到 30 → 20 < 30，向左；30 没有左孩子，20 挂上去。

第 5 轮，插入 40：50 → 左到 30 → 40 > 30，向右；30 没有右孩子，40 挂上去。树的第一层“枝叶”齐了：30 有了左右孩子，但 50 的右子树还只有一个 70。

第 6、7 轮，插入 60、80：60 走 50 → 70 → 60 < 70，向左，成为 70 的左孩子；80 走 50 → 70 → 80 > 70，向右，成为 70 的右孩子。到这里，我们得到了最初的 7 节点完美示例树：除最后一层外每一层都填满，是一棵非常漂亮的“准完全”BST。

第 8 轮，插入 35：就是 5.2 节的过程，35 成为 40 的左孩子。

第 9 轮，插入 45：50 → 30 → 40 → 45 > 40，向右；40 没有右孩子，45 挂上去。注意 45 和 35 现在都是 40 的孩子：35 是左孩子，45 是右孩子，40 终于“儿女双全”。

第 10 轮，插入 65：50 → 70 → 60 → 65 > 60，向右；60 没有右孩子，65 挂上去。最终树长这样：

回看这十轮，你会发现三个规律。规律一：插入顺序决定了树的形状。同一个数字集合，按 50、30、70……插入得到这棵丰满的树；如果按 20、30、35、40、45、50、60、65、70、80 这种递增顺序插入，树会一路向右歪成一条链！这个“歪成链”的现象太重要了，它是第 8 篇的主角，本篇先记住结论：插入顺序是 BST 形状的导演。规律二：每次插入都只影响一条路径。新节点挂上去之后，树的其他部分纹丝不动。规律三：新节点总是叶子。十轮插入，没有一次需要“挪动”已有节点。

5.4 代码：递归版与迭代版

递归版插入非常优雅，它利用“返回新子树的根”的技巧，让空位上的“挂接”自动发生：

// 递归插入：返回插入后的树根
function insertBST(root: TreeNode | null, key: number): TreeNode {
  if (root === null) {
    return { val: key, left: null, right: null };  // 空位：创建新节点
  }
  if (key === root.val) {
    return root;                      // 重复键：约定一，什么都不做
  }
  if (key < root.val) {
    root.left = insertBST(root.left, key);   // 挂到左子树，并接收新子树根
  } else {
    root.right = insertBST(root.right, key); // 挂到右子树
  }
  return root;
}

这个写法的核心是“把新子树根返回给父亲”：当递归进入空节点时，它创建一个新节点并返回；上一层收到这个返回值后，把它赋给自己的 left 或 right。于是“挂接”不需要调用者手动找父亲，递归的返回值自然完成了连接。如果你觉得递归版绕，迭代版更直白：

// 迭代插入：显式记录“空位的父亲”，再挂上新节点
function insertBSTIterative(root: TreeNode | null, key: number): TreeNode {
  const node: TreeNode = { val: key, left: null, right: null };
  if (root === null) return node;               // 空树：新节点就是根

  let cur: TreeNode = root;
  while (true) {
    if (key === cur.val) return root;           // 重复键：不插入
    if (key < cur.val) {
      if (cur.left === null) { cur.left = node; break; }
      cur = cur.left;
    } else {
      if (cur.right === null) { cur.right = node; break; }
      cur = cur.right;
    }
  }
  return root;
}

迭代版每一步都问同一个问题：当前节点有我要去的那个孩子吗？有就继续走，没有就挂上去结束。注意一个细节：递归版和迭代版对空树的处理都是“新节点成为根”，这是插入唯一的“结构性例外”——其他所有情况都是给已有节点添孩子。

5.5 插入的边界与陷阱

第一个陷阱是重复键。如果代码里没有处理“相等”分支，插入重复键时会发生什么？根据“小于走左、大于走右”的规则，等于时两个分支都不进，会死循环（迭代版）或无限递归（递归版）。所以重复键处理不是可选优化，而是必须写的分支。本篇采用约定一：相等直接返回。你也可以改成“向右走”把重复值堆到右子树，或更新 count，但一定要让行为明确。

第二个陷阱是忘记接收递归返回值。递归版里如果只写 insertBST(root.left, key) 而不把它赋给 root.left，新节点虽然被创建了，却没有任何指针指向它，插入就像没发生过一样——这是递归树代码最常见的“幽灵 bug”。请记住：递归修改树，结果必须沿着返回值传回父亲。

第三个陷阱是性能错觉。插入一个节点是 O(h)，看起来很快；但如果连续插入 n 个节点，总代价是 O(n·h)。在平衡树上这是 O(n log n)，在链状树上会退化到 O(n²)。所以“单次插入 O(log n)”这句话默认了树是平衡的，而“平衡”不是 BST 的免费午餐——第 8 篇会专门讲它怎么失去、第 9–12 篇讲怎么夺回来。

第四个陷阱是可变数据的键。如果节点的键是对象（比如 {name, age}），比较规则必须恒定且全序：任何两次比较结果一致，且不存在 a<b、b<c、c<a 的循环。Java 的 Comparable、JavaScript 的自定义比较函数都是为此而生。键一旦允许修改且修改后破坏了顺序，整棵树的 BST 性质就崩了——所以工程上 BST 的键通常只读。

6 删除：BST 里最讲究的操作

6.1 为什么删除比插入难

插入之所以简单，是因为新节点永远是叶子，挂上去就行；删除则要面对一个残酷的事实：被删的节点不一定是叶子。如果它是内部节点，直接把它从树上拿掉，它的孩子们就“没人管”了；如果把某个孩子随便顶上来，又可能破坏 BST 性质。删除算法的全部学问，就是回答一个问题：如何在保持 BST 性质的前提下，把一个节点从树中移除？

标准答案把情况分成三种，按被删节点的“孩子数量”划分：

1. 被删节点是叶子（没有孩子）：直接删，什么也不用补。
2. 被删节点只有一个孩子：让孩子顶替它的位置。
3. 被删节点有两个孩子：不能让孩子直接顶（两个都顶就会有两个根），改用“前驱或后继”的值替换它，然后删掉那个前驱/后继节点。

这三种情况的划分是完备的：任何一个节点要么没有孩子、要么一个孩子、要么两个孩子，没有第四种可能。下面逐一图解。为了方便讲解，我们使用一棵新的“删除专用树”，它包含更多节点，方便展示各种情况：

6.2 情况一：删除叶子节点

最没有悬念的情况。比如删除 35：35 没有左孩子也没有右孩子，是纯正的叶子。删除它的操作就是“从父亲 40 的左指针上摘掉它”，然后把 35 这个节点从内存中释放（垃圾回收语言则直接失去引用）。树的其余部分完全不动。

“直接删”为什么安全？因为叶子没有后代，删掉它不影响任何其他节点的父子关系，也不影响任何“大于/小于”约束——它本来就不约束别人。删除叶子的复杂度是 O(h)：先沿路径找到它，再改父亲的一个指针。注意一个边界：如果被删的叶子恰好是根（整棵树只有一个节点），删除后树变成空树，返回 null 即可。

6.3 情况二：删除只有一个孩子的节点

比如删除 30：30 有左孩子 20，但没有右孩子。如果直接删掉 30，20 就变成无父无主的孤儿。正确的做法是让 20 “顶上来”，占据 30 原来的位置，成为 50 的左孩子。为什么这样不会破坏 BST 性质？因为 20 是 30 左子树里的节点，它小于 30，同时也小于 30 右子树的所有节点——但 30 没有右子树，所以只需检查 20 与 30 的所有祖先的大小关系。关键观察：20 本来就在 30 的左子树里，而 30 的整个左子树都满足“大于 30 的所有左祖先、小于 30 的所有右祖先”，所以把左子树直接顶上来，它依然满足与所有祖先的大小关系。同理，如果删的是只有右孩子的节点，就让右子树顶上来。

实现上，“让孩子顶上来”就是修改父亲的指针：如果被删节点是父亲的左孩子，就把父亲的 left 指向被删节点的唯一孩子；如果是右孩子，就把 right 指向它。如果被删节点是根，就把新的根设为它的唯一孩子。孩子少了一个“中间层”，但整棵树依然有序。

6.4 前驱与后继：两个孩子的钥匙

最麻烦的情况来了：被删节点有两个孩子。直接让左孩子顶上来，右子树没地方放；让右孩子顶上来，左子树又没地方放。标准解法非常巧妙：不删这个节点本身，而是找一个“替身”——用它的中序前驱或中序后继的值覆盖它，然后把替身从原位置删掉。

先定义两个术语。前驱（predecessor）：比某个节点小、且是所有比它小的节点里最大的那个，也就是中序遍历序列中紧挨在它前面的元素。后继（successor）：比某个节点大、且是所有比它大的节点里最小的那个，也就是中序遍历序列中紧挨在它后面的元素。在一棵 BST 里，找前驱和后继有非常具体的树规则：

• 后继：如果节点有右子树，后继就是右子树里最左的节点（右子树的最小值）；如果没有右子树，就沿父亲链向上找第一个“作为左孩子”的祖先。
• 前驱：如果节点有左子树，前驱就是左子树里最右的节点（左子树的最大值）；如果没有左子树，就沿父亲链向上找第一个“作为右孩子”的祖先。

为什么“右子树的最左节点”是后继？因为右子树里所有节点都比当前节点大，而“最左”意味着一路向左，是右子树里最小的节点；比当前节点大的所有节点里，最小的那个自然紧挨在它后面。前驱同理。下图把节点 50 的前驱 45 和后继 60 标了出来：

看图验证：50 的左子树是 30、20、40、35、45，其中最大的是 45，所以 45 是前驱；50 的右子树是 70、60、80、65，其中最小的是 60，所以 60 是后继。中序遍历序列是 20、30、35、40、45、50、60、65、70、80，50 前面是 45，后面是 60，完全吻合。

6.5 情况三：删除有两个孩子的节点（以后继为例）

现在删除 50（根节点，有两个孩子）。分三步走：

第一步，找到后继：50 有右子树，后继是右子树的最左节点，也就是 60。

第二步，用后继的值覆盖被删节点：把 50 的值改成 60。此时树里出现了两个 60（一个在根的位置，一个在 70 的左子树里），但 BST 的“键唯一”约定被暂时打破——没关系，下一步就修复。

第三步，删除原位置上的后继节点：把原来那个 60（位于 70 的左孩子位置）从树中删除。关键问题来了：原位置上的 60 有几个孩子？答案：它最多只有一个孩子。为什么？因为它是“右子树的最左节点”，而“最左”意味着它没有左孩子——一路向左走到头，左子树必然是空的。它可能有一个右孩子（比如示例里的 65），但绝不可能有左孩子。所以删除后继节点时，只会遇到情况一（叶子）或情况二（只有右孩子），而这两种情况我们已经会处理了！

这就是整场魔术的核心：用后继替换，把“删除一个有两个孩子的节点”这个难题，转化为“删除一个最多只有一个孩子的节点”这个简单问题。用前驱替换同理：前驱是左子树的最右节点，它没有右孩子，删除它最多只需处理一个左孩子。

下面这张图完整走一遍“删除 50”的三步：

三步之后树里只剩下一个 60：根上的 60 是原 50 的“替身”，而 70 的左孩子位置由 65 顶替，中序序列依然严格递增。

删除完成后的中序遍历是 20、30、35、40、45、60、65、70、80——依然是严格递增的。BST 性质完好无损。

有一个很容易被忽略的细节值得强调：后继不一定是被删节点的“孙子”。在示例里，60 是 70 的左孩子，离根 50 只隔一层；但后继也可能离得很远，比如 50 的右子树是一条长长的左链，后继在最深处。无论离得多远，替换的逻辑都一样：先“复制值”，再“删原节点”。值复制之后，被删节点在树结构上其实没有消失（它变成了后继的副本），但键的唯一性和有序性都恢复了，从逻辑上讲删除完成。如果你介意“旧节点还在”这种实现细节，也可以选择真正删除被删节点并把子树接好，但标准教材与工程实现普遍采用“值替换”方案，因为它简单、正确、边界少。

6.6 选前驱还是选后继？都行，但要注意一致性

两个孩子的节点既可以选前驱替换，也可以选后继替换，两者都能保持 BST 性质。工程实现里通常二选一并保持始终一致（比如永远选后继），避免同样的删除序列产生不同的树形，给调试和测试增加难度。还有一个细微差别：选前驱替换会让树偏向“左侧更矮”，选后继会让树偏向“右侧更矮”——这个差异在随机数据下无关紧要，但对某些刻意构造的删除序列，长期偏选一侧可能加速树的退化，这也是红黑树等自平衡树要同时考虑的问题。对入门阶段，记住“二选一、保持一致”即可。

6.7 删除的完整代码（TypeScript）

把三种情况整合成一个递归函数。为了让代码清晰，我们先用两个辅助函数：找最小值、删除最小值。

// 返回以 node 为根的子树中的最小节点
function findMin(node: TreeNode): TreeNode {
  let cur = node;
  while (cur.left !== null) cur = cur.left;
  return cur;
}

// 删除以 node 为根的子树中的最小节点，返回新的子树根
function removeMin(node: TreeNode): TreeNode | null {
  if (node.left === null) return node.right;  // 自己就是最小：右孩子顶上
  node.left = removeMin(node.left);           // 否则递归去左子树删
  return node;
}

findMin 对应“一路向左”，removeMin 则是“删除最小节点”的专用函数，它天然只处理“没有左孩子”的节点——最小节点没有左孩子，所以只需返回它的右孩子（可能为空）作为新的子树根。接下来是主函数：

// 删除键为 key 的节点，返回删除后的树根
function deleteBST(root: TreeNode | null, key: number): TreeNode | null {
  if (root === null) return null;             // 没找到：什么也不删

  if (key < root.val) {
    root.left = deleteBST(root.left, key);    // 去左子树删
  } else if (key > root.val) {
    root.right = deleteBST(root.right, key);  // 去右子树删
  } else {
    // 找到要删的节点，按孩子数量分三种情况
    if (root.left === null) return root.right;       // 无左孩子：右孩子顶上（叶子也适用）
    if (root.right === null) return root.left;       // 无右孩子：左孩子顶上

    // 两个孩子的节点：用后继替换
    const successor = findMin(root.right);           // 后继 = 右子树最小值
    root.val = successor.val;                        // 复制值
    root.right = removeMin(root.right);              // 删除原后继节点
  }
  return root;
}

这段代码非常紧凑，但每一行都对应一个情况，请逐行核对：

第一行 if (root === null) return null 处理“键不存在”——删除一个不存在的键，树原样返回。递归查找阶段，key < root.val 去左、key > root.val 去右，和查找、插入完全一致。找到后，root.left === null 这一分支同时覆盖了情况一（叶子：right 也是 null，返回 null，父亲指针置空）和情况二的一部分（只有右孩子：返回右孩子，让右孩子顶上）；root.right === null 覆盖只有左孩子的情况。最后，左右都有孩子，用 findMin(root.right) 找后继、复制值、removeMin 删掉原后继。注意：这里所有递归的返回值都被赋值给父亲的指针——和插入一样，递归修改树必须把新子树根传回去。

如果你更习惯用前驱，替换中间两行即可：找到左子树最大值、复制值、删除左子树最大值。思路完全对称。

6.8 删除的边界与陷阱

删除的边界情况比插入多，逐个点名。边界一：删除根节点。递归版不需要特殊处理：如果根是叶子，root.left === null 且 root.right === null，返回 null，整棵树变空；如果根只有一个孩子，返回那个孩子成为新根；如果根有两个孩子，走替换流程。边界二：删除不存在的键。递归一路走到底遇到 null，原树返回，没有任何副作用。边界三：后继就是被删节点的右孩子。比如删除一个节点，它的右孩子没有左子树，那么 findMin 直接返回右孩子，removeMin 返回右孩子的右子树，值覆盖后一切正常——注意此时 root.right = removeMin(root.right) 会把这个右孩子“删掉”，但它已经不是原来的值了，逻辑依然正确。边界四：树中只有一个节点时删除它。返回 null，得到空树。

最常见的实现错误有三个。第一个是忘记把递归结果赋给 left/right，导致删除后树结构损坏；第二个是在两个孩子的分支里直接删了后继却忘记先复制值，导致键丢失；第三个是用“直接删除后继节点”代替“删除最小值”——如果后继有右孩子，直接删会丢掉右子树。只要记住“复制值 + 删原节点”这两步，第三个错误就不会犯。

7 复杂度分析：树的高度说了算

7.1 三个操作的共同分母：O(h)

把查找、插入、删除三个算法放在一起看，会发现它们的耗时结构惊人地一致：都从根出发，沿着一条路径走到某个位置（命中节点、空位、被删节点），每一步只做 O(1) 的比较和指针操作，然后（删除时）可能再沿着另一条小路径找前驱或后继。所以三个操作的时间复杂度都可以写成 O(h)，其中 h 是树的高度。删除的“两个孩子的分支”会额外多走一段找后继的路径，但那段路径也在树内，长度不超过 h，所以总复杂度依然是 O(h)，常数更大一些而已。

这个结论的价值在于：BST 的性能完全由形状决定。同样 100 万个节点，树高是 20 还是一百万，查找代价是天壤之别。接下来的问题只有一个：h 到底是多少？

7.2 平均情况：O(log n) 的直觉

先给结论：在随机插入顺序下，一棵 n 节点的 BST 的期望高度是 O(log n)，因此查找、插入、删除的期望时间复杂度都是 O(log n)。这个结论的严格证明需要概率论，但直觉很清晰：每次插入一个新节点，它落在树里的位置近似随机；随机插入过程会让树“大致平衡”，就像往沙堆上随机倒沙子，沙堆会自然形成接近圆锥的形状，而不是一根柱子。数学上可以证明，随机 BST 的期望高度约为 4.311 ln n（约 2.99 log₂n），也就是常数倍的对数。100 万个节点，期望高度大约在 30 到 60 之间，查找一次不到几十次比较，非常快。

“平均情况”在工程上有多可靠？它假设插入顺序是随机的。如果你的数据本身是随机生成的（比如用户 ID、哈希值、随机数），BST 的表现确实接近理论值；但现实数据经常不是随机的——按时间戳插入、按字母序插入、按编号递增插入，都会让树长歪。于是最坏情况登场。

7.3 最坏情况：O(n) 与第 8 篇的预告

如果按严格递增的顺序插入 1、2、3、4、5……每个新节点都比所有已有节点大，一路向右走，最终树会变成一条“向右的单链表”：每个节点只有右孩子，高度 h = n。在这条链上查找最大值，要从根一路走到最深处，比较 n 次；插入、删除同理，全部退化成 O(n)。下面这张图对比了同样 7 个节点的两种极端形状：

左树找任意节点最多 3 次比较；右树找 7 需要 7 次比较。节点越多，差距越悬殊：100 万个节点，平衡树约 20 次，链状树要 100 万次。这就是“BST 退化”：插入顺序不当（或删除操作长期偏斜）会让 BST 失去 log 的优势，变成一条链表。为什么退化的 BST 还能“假装”自己是 BST？因为它确实满足定义——每个节点的左子树都小于它、右子树都大于它，只是左子树或右子树总是空着。定义没有错，树也没有错，错的是我们没控制形状。

这个痛点太重要了，第 8 篇《BST 为什么会退化》会专门分析：什么样的插入顺序会退化、如何量化“歪”的程度、为什么随机化（随机 BST）只能缓解不能根治、以及“旋转”这把形状手术刀如何把歪树扶正。本篇先记住结论：BST 的 O(log n) 是平均情况下的承诺，不是最坏情况下的保证。

7.4 空间复杂度：O(n) 与递归栈

存储本身：一棵 n 节点的 BST 需要 n 个节点，每个节点存值、左右指针，空间 O(n)。链式存储的每个节点还要承担指针的开销——两个指针通常各占 8 字节（64 位系统），所以一个整数键的节点可能占用 24 字节甚至更多，这是 BST 相对紧凑数组的代价。

递归实现还会占用额外的调用栈空间：递归深度等于路径长度，最坏 O(h)。平衡树 O(log n)，链状树 O(n)——100 万个节点的链状树，递归查找会尝试压 100 万层栈，绝大多数运行环境直接栈溢出。所以工程上要么用迭代版（额外空间 O(1)），要么保证树高受控（自平衡树），两条路都行，但必须至少选一条。第 8 篇讨论退化时，会再次碰到“递归栈溢出”这个现实后果。

7.5 复杂度速览

操作	平均	最坏	说明
查找	O(log n)	O(n)	沿单条路径下行
插入	O(log n)	O(n)	查找 + 挂叶子
删除	O(log n)	O(n)	可能附加前驱/后继查找
遍历（中序）	O(n)	O(n)	访问全部节点
空间	O(n)	O(n)	节点存储，另加递归栈 O(h)

这张表是 BST 的“成绩单”：查找、插入、删除三位同学的平均分都很优秀，但一旦树退化，全部挂科。如何让最坏情况也变优秀？答案是 AVL 树和红黑树，第 9–12 篇见。

7.6 log n 到底有多快：让复杂度“有感觉”

“O(log n)”写起来轻飘飘，但很多人对它的力量没有体感。做几个换算：2 的 10 次方是 1024，所以 1000 个节点时 log₂n ≈ 10；2 的 20 次方约 100 万，所以 100 万个节点时 log₂n ≈ 20；2 的 30 次方约 10 亿，所以 10 亿个节点时 log₂n ≈ 30。也就是说，从 1000 个节点增长到 10 亿个节点，BST 查找的最多步数只从 10 涨到 30——节点数多了 100 万倍，代价只多了 3 倍。这就是指数与对数的浪漫：数据规模可以爆炸式增长，而对数代价几乎是“躺平”的。

把这份感觉带到对比里：在 100 万个节点的无序链表里查找，平均要碰 50 万个节点；在 100 万个节点的平衡 BST 里查找，最多 20 次比较。一台每秒做 1 亿次比较的机器，链表查一次大约 0.5 毫秒，BST 不到 1 微秒——相差三个数量级。数据库动辄上亿行记录，为什么还能在毫秒级响应？就是因为索引把“扫全表”变成了“沿树走 30 步”。学数据结构时请把“log n”当作一种信仰，但也要记住：这个信仰只对平衡的树成立。

7.7 递归还是迭代：BST 版的决策流程

本篇的查找、插入、删除都给了递归和迭代两种写法（删除只给了递归主流程，迭代版是很好的练习）。怎么选？我的建议和前几篇一致：默认递归，威胁到栈就换迭代。递归版的正确性最好验证——代码与定义一一对应，插入删除的“返回新子树根”模式让结构修改清晰；但它每走一层就压一帧调用栈，深度 O(h)。在平衡树上 h 只有几十，完全无压力；在链状树上 h 可能等于 n，百万级节点直接栈溢出。迭代版用显式循环，额外空间 O(1)，代码稍长，但对深树免疫。

工程上还有第三条路：保证树本身不高。这也是 AVL 树、红黑树存在的意义之一——树高被锁死在 O(log n) 后，递归栈深度自然安全，你可以放心享受递归的简洁。所以“递归还是迭代”在自平衡树的语境里几乎不成问题；真正需要纠结的，只有裸 BST 且无法控制数据形状的场景。另外提醒一句：树的遍历和查找无法写成尾递归，别指望编译器帮你把递归优化成循环——要么迭代，要么控高，没有第三条魔法。

8 应用：BST 能干什么

8.1 动态有序集合

BST 最基本的身份是动态有序集合：它维护一组互异的键，支持插入、删除、查找，并且任意时刻都能以有序的方式遍历。相比有序数组（插入删除 O(n)）和哈希表（无序），BST 在“既要快又要有序”的场景里几乎是唯一的选择。数据库索引、操作系统的进程调度器、文本编辑器的撤销栈（按时间戳有序）、股票订单簿（按价格有序）……这些系统里的核心结构，要么是 BST，要么是 BST 的平衡亲戚。

8.2 范围查询：把整棵子树剪掉

范围查询（Range Query）要求找出所有落在 [low, high] 之间的键。朴素做法是中序遍历整棵树逐个筛选，O(n)；BST 的正确打开方式是剪枝：递归访问每个节点时，如果当前节点的值小于 low，那么它的左子树全部小于 low，整棵左子树都可以跳过；如果当前节点的值大于 high，右子树全部跳过；只有当前值落在区间内时才收集它，并继续访问左右子树。代码：

// 收集所有在 [low, high] 区间内的键
function rangeQuery(root: TreeNode | null, low: number, high: number, out: number[]): void {
  if (root === null) return;
  if (root.val > low) rangeQuery(root.left, low, high, out);  // 左子树可能有值
  if (root.val >= low && root.val <= high) out.push(root.val);
  if (root.val < high) rangeQuery(root.right, low, high, out); // 右子树可能有值
}

为什么左子树的条件是 root.val > low？因为只有当当前值大于 low 时，左子树里才可能含有 ≥ low 的节点；如果当前值 ≤ low，左子树全部更小，必然都 < low，剪掉。右子树同理。这个剪枝让范围查询的实际代价从 O(n) 降到 O(k + h)——k 是结果数量，h 是树高：只访问“可能与区间相交”的路径和结果节点，其余整棵子树直接跳过。在 100 万个节点里查一个很窄的区间，可能只需几十次比较加几个结果，这是哈希表做不到的（哈希表不支持有序范围）。

8.3 第 k 小：中序遍历的现场直播

“找到第 k 小的键”也是高频需求。最直观的方法：中序遍历，数到第 k 个就停。由于中序遍历就是从小到大，这个做法天然正确：

// 找第 k 小（k 从 1 开始），找不到返回 null
function kthSmallest(root: TreeNode | null, k: number): number | null {
  let count = 0;
  let answer: number | null = null;

  function dfs(node: TreeNode | null): boolean {
    if (node === null) return false;
    if (dfs(node.left)) return true;       // 左子树里已经找到
    count++;
    if (count === k) { answer = node.val; return true; }
    return dfs(node.right);
  }

  dfs(root);
  return answer;
}

这个版本最坏 O(n)（比如 k 很大），但空间 O(h)。如果要支持“反复问第 k 小”并希望每次 O(h)，可以在节点里增加一个 size 字段（子树节点数），插入、删除时沿途维护，然后用“左子树大小”决定去左还是去右，类似二分查找按区间定位。这种“增强 BST（Augmented BST）”是线段树、树状数组的亲戚，第 9–12 篇会提到，这里先记住方向：有序性 + 子树统计 = 快速排名。

8.4 BST 排序：插入再中序遍历

把 n 个元素依次插入 BST，再中序遍历输出，得到的就是有序序列——这个过程叫 BST 排序（Tree Sort）。代码只有两行骨架：

function treeSort(values: number[]): number[] {
  let root: TreeNode | null = null;
  for (const v of values) root = insertBST(root, v);  // 依次插入
  const result: number[] = [];
  inorderTraversal(root, result);                      // 中序输出
  return result;
}

复杂度是多少？插入 n 个节点总代价 O(n·h)，中序遍历 O(n)。如果插入顺序随机，h ≈ O(log n)，总代价 O(n log n)——和快速排序、归并排序一个量级；如果插入顺序接近有序，h ≈ O(n)，总代价退化到 O(n²)。所以 BST 排序的复杂度曲线和快速排序惊人地相似：平均 O(n log n)、最坏 O(n²)、对输入顺序敏感。这不是巧合——快速排序的递归树本质上就是一棵 BST！第 8 篇讨论退化时会看到这个深层联系。BST 排序还有一个隐含特性：它天然去重（重复键约定不插入），所以也常被用来“排序并去重”。

8.5 前驱、后继、floor 与 ceiling

除了“找得到”，BST 还擅长“找接近”：给定一个键（可能不在树里），问比它小的最大键（floor）和比它大的最小键（ceiling）。这组操作在订单匹配、最近邻查询、日程安排（找下一个空闲时间）里很常见。算法同样是沿路径走，只是要记录“最后一个满足条件的候选”：查找 key 时，遇到值 ≤ key 的节点，记录它为 floor 候选并向右走；遇到值 > key 的节点，向左走。走到空位时，记录的候选就是答案。这一组操作把 BST 的“有序性”用到了极致，也是 6.4 节前驱后继概念的推广——前驱后继是“树里一定存在”的 floor/ceiling，而 floor/ceiling 允许键不在树里。

8.6 与二分查找、哈希表的三方对比

很多初学者纠结：查找到底用数组二分、BST 还是哈希表？三者没有绝对优劣，只有场景适配。下面这张表把关键维度摊开：

维度	有序数组 + 二分查找	二叉搜索树	哈希表
查找	O(log n)	O(log n) 平均	O(1) 平均
插入	O(n)（搬移元素）	O(log n) 平均	O(1) 平均
删除	O(n)（搬移元素）	O(log n) 平均	O(1) 平均
有序遍历	天然有序	中序 O(n)	无序
范围查询	二分边界 + 遍历	剪枝，O(k + log n)	不支持
第 k 小	按下标 O(1)	O(k) 或增强后 O(log n)	不支持
额外要求	数据量固定 / 可预分配	键可比较、树需平衡	键可哈希、处理冲突

读表的关键结论有三条。第一，如果只做“点查找”且不在乎顺序，哈希表最快，O(1) 平均是 BST 比不了的；但哈希表牺牲了顺序，范围查询、第 k 小、排序输出全部做不到。第二，如果数据是静态的（建好后几乎不变），有序数组 + 二分查找既简单又省内存，比 BST 更优——BST 的优势只在“动态”场景。第三，如果既要动态又要有序，BST 是自然之选，但必须小心退化，工程上通常直接上 AVL 树或红黑树。数据库索引之所以用 B 树而不用哈希表，正是因为要支持范围扫描；进程表、符号表之所以常选平衡树，也是同一个道理。

再补充一个容易误解的点：哈希表的 O(1) 是“平均”，最坏情况下（冲突严重）退化到 O(n)；BST 的 O(log n) 平均在退化时也会变成 O(n)。两种结构的“最坏情况”都不是免费的，只是退化原因不同——一个败给糟糕的哈希函数，一个败给糟糕的插入顺序。

8.7 验证一棵树是不是 BST：把定义变成代码

定义讲得再清楚，落到代码时还是会有人写错。判断一棵二叉树是不是 BST，最常见的错误版本长这样：递归检查每个节点“大于左孩子、小于右孩子”。我们在 2.2 节已经见过它的反例——局部成立、全局崩坏。正确的验证有两种主流写法，恰好对应 BST 性质的两种等价表述。

写法一：中序有序。利用第 3 节的等价关系“BST ⇔ 中序严格递增”，中序遍历一遍，检查序列是否严格递增。为了避免存储整个序列，可以只记住上一个访问的值，当前值必须大于它：

function isValidBST(root: TreeNode | null): boolean {
  let prev: number | null = null;   // 上一个访问的值

  function dfs(node: TreeNode | null): boolean {
    if (node === null) return true;
    if (!dfs(node.left)) return false;          // 左子树必须有序
    if (prev !== null && node.val <= prev) return false; // 必须严格递增
    prev = node.val;
    return dfs(node.right);                     // 再检查右子树
  }

  return dfs(root);
}

这个写法最省脑：不用设计复杂的参数，只需要相信“中序 = 从小到大”这个等价关系。注意比较用的是 <= 而不是 <——因为约定不允许重复键，一旦出现相等，树就不是合法的 BST。

写法二：区间约束。BST 的定义其实可以翻译成另一种形式：每个节点都有一个合法的取值区间。根节点可以取任意值（区间负无穷到正无穷）；一旦走进左子树，该子树的所有节点都必须小于父节点，于是区间右边界收紧为父节点的值；走进右子树，区间左边界收紧为父节点的值。递归时把“当前合法区间”一路传下去：

function isValidBSTBounds(root: TreeNode | null): boolean {
  function check(node: TreeNode | null, low: number, high: number): boolean {
    if (node === null) return true;
    if (node.val <= low || node.val >= high) return false;  // 超出合法区间
    return check(node.left, low, node.val)      // 左子树区间 (low, node.val)
        && check(node.right, node.val, high);   // 右子树区间 (node.val, high)
  }
  return check(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
}

看 2.2 节那个反例如何被区间法抓住：根 50 的合法区间是 (-∞, +∞)；走进左孩子 30，合法区间变成 (-∞, 50)；30 的右孩子 60 的合法区间是 (30, 50)——60 不在区间内，直接返回 false。区间法的好处是它天然表达“全局”约束：约束不只在父子之间传递，而是沿着整条路径不断收紧，任何远处的越界都逃不掉。两种写法时间复杂度都是 O(n)、空间 O(h)。面试里被问“如何验证 BST”，中序写法最快，区间写法最能展示你对定义的理解，建议两个都会。

8.8 从有序数组构建平衡 BST：中序遍历的“逆运算”

如果手里已经有一份有序数组，想直接得到一棵平衡的 BST，不用一个一个插入——因为插入顺序决定了形状，而“中点优先”的顺序恰好能长出一棵平衡树。更优雅的做法是递归建树：取数组的中间元素作为根，左半边递归建左子树，右半边递归建右子树。每次递归都把区间对半切开，所以树高天然是 O(log n)。代码：

// 从有序数组构造高度平衡的 BST
function sortedArrayToBST(nums: number[]): TreeNode | null {
  function build(l: number, r: number): TreeNode | null {
    if (l > r) return null;
    const mid = Math.floor((l + r) / 2);          // 中点做根
    const node: TreeNode = { val: nums[mid], left: null, right: null };
    node.left = build(l, mid - 1);                // 左半边建左子树
    node.right = build(mid + 1, r);               // 右半边建右子树
    return node;
  }
  return build(0, nums.length - 1);
}

这个算法的复杂度是 O(n)：每个元素恰好被取一次作为某个子树的根。它同时也是中序遍历的“逆运算”——把中序序列“折叠”回一棵树。前面说过，中序序列不能唯一还原 BST；这个算法给出的是其中一棵特别“端正”的：每次取中点，保证左右子树大小差不超过 1，是一棵理想平衡树。这个“分半建树”的思想还会在第 8 篇（退化分析）和第 9 篇（AVL 旋转）里反复出现，请把它和二分查找放在同一个抽屉里：二分、分治、平衡，三者的灵魂都是“对半切”。

8.9 现实世界里的 BST：符号表与数据库索引

最后用两个真实场景把 BST 的价值钉进记忆。第一个是符号表（Symbol Table）：编译器在翻译代码时，需要维护一张“变量名 → 地址/类型”的表。变量会不断声明（插入）、被引用（查找）、在作用域结束时销毁（删除），而且调试器常要按名字顺序列出所有变量——这正是“动态 + 有序”的组合，BST 及其平衡亲戚是符号表的经典实现。第二个是数据库索引：SQL 的 WHERE id = 7 是点查找，WHERE id BETWEEN 5 AND 100 是范围查询，ORDER BY 是排序输出——一张哈希表只能满足第一个，而 B+ 树（BST 的多叉亲戚）三个全包。理解 BST，你就理解了这些系统的第一性原理：树的有序性，是把“查找”“排序”“范围”三件事统一起来的纽带。

9 动手体验：在可视化实验室里玩一遍

光看图和代码，不如亲手玩一遍。本站的搜索算法可视化实验室内置了 BST 的交互演示：你可以往树里插入节点，看着新节点沿着查找路径一步步滑到自己的位置；可以输入一个键查找，观察路径上哪些节点被高亮、哪些子树被“剪掉”；还可以练习删除，亲眼见证叶子直接消失、单孩子节点被孩子顶替、双孩子节点被后继替换的全过程。建议按下面的顺序操作，和本篇的章节一一对应：

第一步，先建一棵树：依次插入 50、30、70、20、40、60、80，对照 5.3 节的“手算多轮插入”，确认树的形状和文中图一致。第二步，查找 40 和 35，对照 4.2 节的访问顺序 50 → 30 → 40，看看高亮路径是不是一模一样；查找 35 时注意它最后停下的“空位”，那就是插入它的位置。第三步，插入 35，观察它成为 40 的左孩子。第四步，依次删除 35（叶子）、30（单孩子）、50（双孩子），每删一步前先在纸上写出你预期的结果，再和动画对照。第五步，玩点“坏”的：按 1 到 15 递增插入，看树如何一步步长成一条链，直观感受第 8 篇的主角——退化。

如果你在沙盒里把树“玩歪”了，不用慌——删除全部节点或刷新页面就能重来。动手实验的价值在于，把“左小右大”从一句抽象定义变成肌肉记忆：看多了路径，你会发现查找就像在有序世界里“走迷宫”，而迷宫的路标就是比较结果。

9.1 常见易错点清单

把本篇最容易翻车的八个点集中列在这里，写代码前过一遍，能省掉大量调试时间：

第一，重复键没有分支。查找、插入、删除的比较逻辑里，“等于”必须被显式处理，否则插入会死循环、删除会漏删。第二，递归返回值没有赋给父亲。root.left = deleteBST(root.left, key) 里的“=不能省，少了它，树结构在递归返回时就断了。第三，**把 BST 性质理解成局部比较**。验证一棵树是不是 BST，必须用中序递增或区间约束，不能只比“节点与两个孩子”。第四，**忘记空树**。所有操作的第一行都该想清楚 root 为 null 时返回什么：查找返回 null，插入返回新节点，删除返回 null。第五，**双孩子删除时直接砍掉后继**。正确顺序是“先复制值，再删原后继”；如果后继有右孩子，删除时要用 removeMin 之类的逻辑把它接住，而不是让右子树凭空消失。第六，**键是可变的**。节点入树后如果修改键，比较关系会失效，BST 变得不可信；工程上把键设计成只读，或用“删除再插入”代替修改。第七，**默认树是平衡的**。裸 BST 的 O(log n) 是平均承诺；在面试里说复杂度时，一定要区分“平均”和“最坏”，并说明最坏发生在有序输入。第八，**中序验证用了 <= 却解释不清**。BST 不允许重复键，所以严格递增要用node.val <= prev` 判否；如果你改了约定（允许重复），验证逻辑也要同步改。

这八条不是孤立的技巧，它们全部来自同一个源头：BST 的一切正确性都建立在“全局有序”这个不变量上。每次写代码，问自己一句：我这一步之后，树还满足“左小右大”吗？如果满足，操作大概率是对的；如果不确定，中序遍历一遍验货。

10 常见变形预告：从 BST 到自平衡家族

本篇讲的是“裸 BST”——它不做任何形状控制，把命运交给插入顺序。裸 BST 平均表现优秀、最坏表现拉胯，这个矛盾催生了一个大家族：自平衡二叉搜索树。它们的基本操作（查找、插入、删除、中序有序）和 BST 完全一致，额外的工作是在插入、删除后检查并修复树的平衡，把高度严格限制在 O(log n)。下面这张图勾勒了 BST 家族的关系：

先看 AVL 树（第 9 篇）：它要求任意节点的左右子树高度差不超过 1，失衡时用“旋转”操作修复。AVL 是最“严格”的平衡树，高度最接近 log n，查找最快，但插入删除后的旋转次数可能更多。再看 红黑树（第 10 篇）：它用红黑染色加五条性质把树“近似平衡”，高度不超过 2log(n+1)，牺牲一点查找速度换来更少的旋转，因此成为工程之王——Java 的 TreeMap、C++ 的 std::map、Linux 内核的调度器都基于红黑树。第 11 篇会聊 Treap、替罪羊树、伸展树这些“性格各异”的变体：Treap 用随机优先级让树自动平衡，替罪羊树用“重建”代替旋转，伸展树把最近访问的节点“翻”到根附近。第 12 篇则走向磁盘世界：B 树 / B+ 树把二叉变成多叉，让每个节点塞进一个磁盘块，是数据库索引的事实标准。

学习顺序上，本篇是所有这些树的地基：AVL 和红黑树只是“BST + 平衡策略”，它们的查找、插入、删除骨架和本篇一模一样，多出来的只是“失衡检测”和“旋转修复”。所以这一篇写得越扎实，后面四篇就越轻松。现在，请在继续之前确认自己真的能默写：BST 定义、中序有序性、查找路径、三种删除情况、复杂度结论——这五样就是整个家族的遗传基因。

10.1 学习路线：从裸 BST 到自平衡树

给想把这套知识彻底吃进肌肉里的你一条四阶段路线。阶段一：裸 BST 通关。合上书，用 TypeScript 独立实现节点类型、查找、插入、删除，并用中序遍历当“验货器”：随机插删几百次，每次操作后中序序列都必须严格递增。阶段二：边界轰炸。针对空树、单节点、根节点、链状树、重复键、不存在的键六个边界反复测试；再把删除的三种情况分别构造出来，先纸笔手算再对照代码。阶段三：退化实验。生成三组输入——随机顺序、递增顺序、递减顺序，分别建树并打印高度，直观看到“导演”对形状的影响；再去读第 8 篇，把观察变成理论。阶段四：上旋转。从第 9 篇开始学 AVL 的四种旋转，实现时先在纸上画清“失衡点、旋转轴、子树归属”，再写代码；红黑树可以先用现成库体会行为，再逐步实现。每完成一个阶段，回到本篇的速查表和自测题重做一遍，你会发现同一道题在不同阶段会有完全不同的理解深度——这就是“温故而知新”在算法学习里的样子。

11 BST 操作复杂度速查表

把本篇最需要背的结论压缩成一张表。注意“平均”默认插入顺序随机、树近似平衡；“最坏”默认树退化成链：

操作	最好情况	平均情况	最坏情况	备注
查找	O(1)（根即目标）	O(log n)	O(n)	沿单条路径
插入	O(1)（空树或根旁）	O(log n)	O(n)	新节点总是叶子
删除叶子	O(h)	O(log n)	O(n)	改父亲一个指针
删除单孩子	O(h)	O(log n)	O(n)	孩子顶上
删除双孩子	O(h)	O(log n)	O(n)	前驱/后继替换
中序遍历	O(n)	O(n)	O(n)	输出有序序列
求最小值/最大值	O(h)	O(log n)	O(n)	一路向左/右
找前驱/后继	O(h)	O(log n)	O(n)	右子树最左 / 左子树最右
空间	O(n)	O(n)	O(n)	递归栈额外 O(h)

三个必背结论：第一，BST 所有“点操作”的复杂度都是 O(h)，h 是树高；第二，随机插入下 h ≈ O(log n)，递增插入下 h = O(n)；第三，中序遍历永远 O(n) 且输出有序，这是 BST 相对哈希表的不可替代优势。把这张表背下来，面试里的“BST 复杂度”题基本不会丢分。

12 自测题

下一篇预告：《树系列第 8 篇：BST 为什么会退化》

本篇反复提到一个词——“退化”：明明是一棵满足定义的 BST，却因为插入顺序不好长成一条链，把 O(log n) 的承诺变成 O(n) 的噩梦。下一篇，我们专门解剖这个问题。你会看到：什么样的插入顺序会让树长歪；如何用“平衡因子”和“高度”量化歪的程度；随机化为什么能救急却不能根治；以及 BST 与快速排序那场惊人的“灵魂互换”——它们的最坏情况居然来自同一种输入模式。更关键的是，下一篇会引出治疗退化的一把手术刀：旋转。理解旋转，你就拿到了 AVL 树和红黑树的门票。建议你在阅读下一篇之前，先亲手做两个小实验：用递增序列建一棵 15 个节点的树，数一数它的高度；再用 5.3 节的“中点优先”顺序建同样的 15 个数，对比两棵树的高度差异。带着这份体感去读第 8 篇，你会更深刻地理解为什么“形状”是 BST 的生命线。树系列最硬核的部分，才刚刚开始。我们第 8 篇见。