二叉搜索树 BST：查找、插入与删除
在普通二叉树里，左右孩子的位置本身并不一定携带数值上的顺序信息。也就是说，虽然我们能遍历整棵树，但如果想高效查找某个值，普通二叉树未必比线性扫描好多少。二叉搜索树之所以重要，就是因为它在“树的层级结构”和“关键字有序性”之间建立了一条非常漂亮的联系。
它的核心思想非常简单：
对于每个节点，左子树中的所有关键字都小于该节点，右子树中的所有关键字都大于该节点。
正是这条规则，让 BST 同时拥有了两种非常有价值的特性：
- 它仍然是一棵树，适合分层组织和局部更新；
- 它又带有全局有序性，使得查找、插入、删除都能沿着比较路径逐步缩小问题。
所以 BST 可以看成是数据结构里第一次非常明确地把“有序”嵌入树结构的尝试。后面的 AVL、红黑树、B 树、B+ 树，本质上都在继续围绕这个方向做优化。
一、什么是二叉搜索树
二叉搜索树，通常简称 BST，它满足以下性质：
- 若左子树非空，则左子树上所有节点值都小于根节点值；
- 若右子树非空，则右子树上所有节点值都大于根节点值；
- 左右子树本身也分别是二叉搜索树。
这里有两个关键词非常重要。
1. 有序性是局部递归定义的
不是说整棵树“看起来差不多有序”就行，而是每个节点都必须满足左右子树的大小关系。
2. 子树本身仍是 BST
这使得查找、插入、删除都可以递归地进行。
二、为什么 BST 查找会更高效
因为每次比较都能决定下一步只往一个方向走。
例如查找值 x 时：
- 如果
x == root.val，直接找到； - 如果
x < root.val，只需要去左子树找； - 如果
x > root.val，只需要去右子树找。
这意味着你不必像普通二叉树那样把左右子树都遍历一遍，而是可以利用有序性不断缩小搜索范围。
如果树比较平衡，那么每往下一层，问题规模都在显著收缩，于是查找复杂度就能接近 O(log n)。
三、为什么中序遍历 BST 会得到有序序列
这是 BST 最经典、最值得记住的性质之一。
中序遍历顺序是：
1 | 左 -> 根 -> 右 |
而 BST 又保证：
- 左子树全部小于根；
- 右子树全部大于根。
于是中序遍历结果自然就是从小到大的有序序列。
这一点很重要，因为它说明 BST 不只是“查找方便”，它还把树结构和排序结果联系了起来。
四、BST 的查找过程怎么理解
BST 查找的本质其实很像“在树上做比较驱动的路径选择”。
和数组中的二分查找不同，BST 不是靠下标取中点，而是靠当前节点作为比较枢纽：
- 小了就往左；
- 大了就往右；
- 相等就结束。
所以查找路径通常只会经过从根到某个节点的一条链，而不会遍历整个结构。
这也是 BST 相比普通二叉树最根本的优势。
五、BST 的插入为什么也很自然
插入一个新值时，逻辑和查找几乎一样：
- 从根开始比较；
- 小于当前节点就往左走；
- 大于当前节点就往右走；
- 一直走到空位置，把新节点挂上去。
之所以可行，是因为：
- 查找路径本身就确定了新值应该落在哪个局部范围；
- 只要放在最终空位上，就不会破坏 BST 的有序性质。
所以 BST 插入最大的优点是：
- 不需要像顺序表那样整体搬移元素；
- 只需要沿着一条路径往下，最后修改一个局部链接。
六、BST 删除为什么更复杂
删除是 BST 里最值得重点理解的一步，因为它不像查找和插入那样只靠一路往下就能自然结束。删除某个节点时，你不仅要把它去掉，还必须保证整棵树删完后仍然满足 BST 性质。
通常分三种情况。
1. 删除叶子节点
这是最简单的情况，直接删除即可，不会影响其他结构。
2. 删除只有一个孩子的节点
让它的孩子直接顶替它的位置即可。
3. 删除有两个孩子的节点
这是最关键的一种情况。通常做法是：
- 找到该节点的中序前驱，或者中序后继；
- 用它的值替换当前节点；
- 再去删除那个前驱或后继节点。
为什么这样做可行？因为中序前驱是左子树中最大的值，中序后继是右子树中最小的值，它们都是最适合接替当前节点的候选者，不会破坏整体有序性。
七、BST 的性能为什么和树高密切相关
这一点非常重要。
BST 的查找、插入、删除，几乎都只沿着一条从根到叶的路径进行，所以它们的时间复杂度通常和树高 h 成正比，也就是 O(h)。
于是问题就转化成：
- 如果树高较小，操作就快；
- 如果树高很大，操作就慢。
在理想情况下，BST 比较平衡，树高接近 log n，操作复杂度也就接近 O(log n)。
八、BST 为什么会退化
这是普通 BST 最大的问题。
如果插入序列本身非常不均匀，例如按递增顺序依次插入：
1 | 1, 2, 3, 4, 5 |
那么树就会退化成一条链：
- 每个节点都只有右孩子；
- 树高接近
n； - 查找、插入、删除都会退化成
O(n)。
这说明 BST 虽然有序，但它并没有自动保证“形状平衡”。
也正因为这个缺陷，后面才会有 AVL 树、红黑树等平衡搜索树出现。
九、BST 和二分查找是什么关系
它们都利用了“有序性”来缩小搜索范围，但方式不同。
1. 二分查找
- 基于有序数组；
- 随机访问快；
- 查找高效；
- 但插入删除代价高。
2. BST
- 基于有序树结构；
- 查找同样能缩小范围；
- 插入删除更灵活；
- 但如果不平衡，性能可能退化。
可以说，BST 是一种在“有序性”和“动态更新”之间做平衡的结构尝试。
十、BST 在真实开发里有什么启发
即便你不直接手写一个 BST，它背后的思想仍然非常重要：
- 有序结构能支持高效查找；
- 局部调整比整体搬移更灵活；
- 树高决定性能上界；
- 结构有序不代表结构平衡。
这些认识会直接帮助你理解后面更工程化的结构，例如：
TreeMap- 红黑树
- B+ 树索引
- 有序集合和范围查询结构
十一、学习 BST 时最容易踩的坑
1. 只记定义，不理解递归约束
BST 的性质不是只对根节点成立，而是对每棵子树都必须成立。
2. 删除操作三种情况没分清
特别是有两个孩子的节点，很多人一开始最容易乱。
3. 误以为 BST 一定是 O(log n)
其实只有在树比较平衡时才接近这个复杂度。
4. 把 BST 和堆混淆
BST 强调左右子树全局有序，堆只强调局部堆序，二者不是一回事。
5. 忽略中序遍历的重要性
中序遍历输出有序序列，是 BST 最值得牢牢记住的特性之一。
总结
BST 的重要性，不只是因为它是一棵会比较大小的树，而是因为它第一次系统地把“有序查找”和“树形组织”结合在了一起。真正值得先建立起来的，是这些核心认识：
- BST 通过左小右大的递归规则，把顺序性嵌入到树结构中；
- 查找、插入、删除都能沿着比较路径逐步缩小问题；
- 删除之所以复杂，是因为删完后仍要维持整棵树的搜索性质；
- BST 的核心性能取决于树高，而树高又取决于结构是否平衡；
- 中序遍历会得到有序序列，这是 BST 与遍历最重要的联系；
- 真正学会 BST，不是只会写几个操作，而是理解“有序”与“平衡”其实是两回事。
把这一篇理解透之后，后面再去学 AVL 树和红黑树时，你会非常自然地看到：它们并不是推翻 BST，而是在保留 BST 搜索性质的基础上，进一步解决“退化”和“树高失控”的问题。
参考资源：