二叉搜索树与平衡树
基于通用算法套路 · 核于 2026-07
速查
- BST 性质：对任意节点，左子树所有值 < 根值 < 右子树所有值，且左右子树也各自是 BST（通常约定值唯一，无重复）。
- 中序得升序：BST 的中序遍历天然产生升序序列——这是「一边动态增删一边维护有序」的结构基础，也是验证 BST 的方法。
- 操作复杂度依赖高度 h：查找 / 插入 / 删除都是 O(h)；平衡树 h = O(log n)，退化为链表 h = O(n)。
- 查找：从根开始，target 小于当前值走左、大于走右，相等即找到——本质是「二分查找」沿树下行，最多走 h 步。
- 插入：先查找定位（找到会插到的空位），新建节点挂上去——一定插在某个叶子下，不改变原有结构。
- 删除三情况：①叶子直接删；②单子节点用唯一孩子顶替；③双子节点用中序后继（右子树最小值）或前驱替换后再删后继——最复杂。
- 退化为链表：按有序序列插入（如 1,2,3,...）会让 BST 长成单链表，所有操作退化到 O(n)——这是 BST 必须配平衡机制的硬伤。
- AVL 树（严格平衡）：任意节点左右子树高度差 ≤ 1，通过四种旋转（LL/RR/LR/RL）维持平衡；查找最快（最矮），但增删旋转多。
- 红黑树（弱平衡）：节点带颜色，五条性质保证「没有一条根到叶路径是另一条的两倍长」——高度 O(log n) 但常数大；增删旋转少，是工业标准。
- 为何红黑是工业标准：增删查都稳定 O(log n)，且插入最多 2 次旋转、删除最多 3 次旋转（AVL 删除可能 O(log n) 次旋转），旋转代价小适合写多场景——C++
map、JavaTreeMap、Linux CFS、epoll 全用它。 - 进阶：平衡树实现细节（旋转代码）属于高级叶，本叶只讲性质与对比；API 速查见参考。
一、BST 性质与中序得升序
二叉搜索树（BST） 在二叉树上加了有序约束：对任意节点 x，其左子树所有节点的值都 小于 x.val，右子树所有节点的值都 大于 x.val（值唯一时），且左右子树本身也是 BST。
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
中序遍历：1 3 4 6 7 8 10 13 14 ← 升序！BST 中序得升序是最重要的推论——中序遍历一棵 BST 得到的序列严格递增。由此衍生：
- 验证 BST：中序遍历，检查序列是否严格递增（或边遍历边记前驱值比较）。
- 找第 k 小：中序遍历到第 k 个即可。
- BST → 有序数组 → 平衡 BST：中序取出有序序列，再二分重建，是「把退化 BST 变平衡」的常用技巧。
二、查找：本质是二分
BST 的查找就是沿树下行的二分——从根开始，target 小于当前值走左子树，大于走右子树，最多走树高 h 步。
js
function search(root, target) {
let cur = root;
while (cur) {
if (target === cur.val) return cur; // 找到
cur = target < cur.val ? cur.left : cur.right; // 小走左，大走右
}
return null; // 未找到
}- 复杂度 O(h)：每层比较一次，最多走 h 步（根到叶最长路径）。平衡树 h = O(log n)，退化为链表 h = O(n)。
- 与二分查找的对比：有序数组的二分 O(log n) 依赖数组支持 O(1) 随机访问；BST 的「二分」依赖树形结构，增删不搬移数据，但退化时失效。
三、插入：查找到空位再挂
插入是查找的延伸——先按查找逻辑找到「该插入的空位」，新建节点挂上去。一定插在叶子的下方，不改变原树结构。
js
function insert(root, val) {
if (root === null) return new TreeNode(val); // 空树或找到空位：新建
if (val < root.val) root.left = insert(root.left, val);
else if (val > root.val) root.right = insert(root.right, val);
return root; // val 已存在则忽略（无重复约定）
}- 复杂度 O(h)：同查找，沿一条路径下行到底。
- 迭代版：用一个
parent指针记录父节点，找到空位后挂到parent的对应孩子上。
四、删除：三种情况
删除是 BST 最复杂的操作，分三种情况（假设值唯一）：
情况① 叶子节点 情况② 单子节点 情况③ 双子节点
8 8 8
/ \ / \ / \
3 10 3 10 3 10
/ \ \ \
1 ← 删 6 ← 删 6 14 ← 删
/ \ / \
4 7 4 7- ① 叶子节点：直接删除（父节点对应指针置空）。
- ② 只有一个孩子的节点：用唯一的孩子顶替它的位置（父节点指针指向它的孩子）。
- ③ 有两个孩子的节点：不能直接删（会破坏子树）。用中序后继（右子树的最小值节点，即右子树一路向左到底）替换它的值，然后删除那个后继节点（后继节点最多只有一个右孩子，退化成情况①或②）。
js
function deleteNode(root, key) {
if (!root) return null;
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else { // 找到待删节点
if (!root.left) return root.right; // 情况①②：无左子，用右子顶替（右子可空）
if (!root.right) return root.left; // 情况②：无右子，用左子顶替
// 情况③：双子，找中序后继（右子树最小值）
let succ = root.right;
while (succ.left) succ = succ.left;
root.val = succ.val; // 用后继值替换
root.right = deleteNode(root.right, succ.val); // 删后继（后继最多一个右子）
}
return root;
}- 为何用后继替换：后继是「右子树里最小的」，替换后仍满足「左子树 < 新根 < 右子树」——BST 性质保持。
- 也可用前驱（左子树最大值）替换，效果等价，选哪个看实现偏好。
- 复杂度 O(h)：查找 + 找后继 + 删后继都在一条 O(h) 路径上。
五、退化为链表：BST 的致命缺陷
BST 的所有操作依赖高度 h，但插入顺序会严重影响树的形状。理想 BST 高度 O(log n)，但按有序序列插入会让它退化成单链表，高度变成 O(n)。
依次插入 1,2,3,4,5（有序）：
理想平衡 BST 退化的 BST（单链表）
3 1
/ \ \
2 4 2
/ \ \
1 5 高度 2 3
\
4
\
5 高度 4 = n-1退化为链表后，查找/插入/删除都退化到 O(n)——BST 的优势荡然无存。这就是为什么实际工程中不能直接用朴素 BST，必须引入平衡机制把高度稳定压在 O(log n)。
六、平衡树：AVL 与红黑树
平衡二叉搜索树通过在增删时主动调整树形（旋转），把高度控制在 O(log n)。两种主流实现：
AVL 树（严格平衡）
AVL 树要求任意节点的左右子树高度差 ≤ 1（平衡因子 ∈ {-1,0,1}）。一旦增删导致某节点平衡因子失衡，就用四种旋转恢复：
| 失衡类型 | 形态 | 恢复旋转 |
|---|---|---|
| LL（左左） | 新节点插入左孩子的左子树 | 右旋（一次） |
| RR（右右） | 新节点插入右孩子的右子树 | 左旋（一次） |
| LR（左右） | 新节点插入左孩子的右子树 | 先左旋左子，再右旋根（两次） |
| RL（右左） | 新节点插入右孩子的左子树 | 先右旋右子，再左旋根（两次） |
- 特点：最严格的平衡（高度差 ≤ 1），树最矮，查找最快（比较次数最少）。
- 代价：增删时维持严格平衡，旋转次数多（删除最坏要 O(log n) 次向上回溯旋转），适合查找密集、增删少的场景（如数据库索引的读多写少）。
红黑树（弱平衡）
红黑树用节点颜色（红/黑）加五条性质维持「弱平衡」——保证没有一条根到叶的路径是另一条的两倍长以上，从而高度仍是 O(log n)（常数比 AVL 大）。
红黑树五条性质：
- 每个节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点（NIL 空节点）是黑色。
- 红色节点的孩子必须是黑色（即不能有连续两个红节点）。
- 从任一节点到其所有后代叶子的路径上，黑色节点数目相同（黑高相同）。
这五条性质共同保证：最长路径（红黑相间）最多是最短路径（全黑）的两倍——所以高度 O(log n)，虽然不如 AVL 矮，但增删时需要的旋转次数少。
- 插入最多 2 次旋转（重新染色 + 最多 2 次旋转）。
- 删除最多 3 次旋转（重新染色 + 最多 3 次旋转）——而 AVL 删除可能要 O(log n) 次旋转。
七、AVL vs 红黑：为何红黑是工业标准
| 维度 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡严格度 | 高度差 ≤ 1（严格） | 弱平衡（路径差 ≤ 2 倍） |
| 树高 | 较矮（查找快） | 较高（常数大） |
| 查找 | 更快（比较次数少） | 略慢 |
| 插入旋转 | 最多 1 次（双旋） | 最多 2 次 |
| 删除旋转 | 最坏 O(log n) 次 | 最多 3 次 |
| 适合场景 | 查找密集（读多写少） | 增删频繁（读写均衡） |
为何工业标准选红黑树而非 AVL：
- 增删旋转次数稳定：红黑树删除最多 3 次旋转，AVL 删除可能要从底向上旋转 O(log n) 次——写多场景红黑树明显更优。
- 综合性能均衡：虽然查找略慢于 AVL，但增删快，整体在「增删查均衡」的通用场景（如标准库容器、内核调度）下表现最好。
- 实际工程中的红黑树：C++ STL 的
std::map/std::set、Java 的TreeMap/TreeSet、Linux 内核的 CFS 进程调度器（rbtree）、epoll的事件管理、Nginx 的 timer 管理——都用红黑树。
一句话总结：AVL 查找最快但增删旋转多，适合读多写少；红黑树增删旋转少且综合均衡，是通用场景的工业标准。
交互演示
- 二叉树可视化演示 —— BST 的查找/插入/删除与平衡过程
下一步
理解了 BST 的性质、操作与平衡树后，可以回头看参考里的 API 速查、复杂度表和代码模板，作为面试和编码时的速查手册。