加载中…
应用场景：严格平衡的有序集合 · 数据库索引
交互式动画演示，可调整参数并单步执行。
全屏打开普通 BST 在有序数据插入时会退化为链表，查找从 O(log n) 退化到 O(n)。
平衡 BST 通过限制左右子树高度差，保证树高始终为 O(log n)。
| 平衡方案 | 平衡条件 | 代表 |
|---|---|---|
| 严格平衡 | 左右子树高度差 ≤ 1 | AVL 树 |
| 近似平衡 | 最长路径 ≤ 2×最短路径 | 红黑树 |
| 多路平衡 | 节点可有多个 key | B 树 / B+ 树 |
AVL 查询更快（树更矮），红黑树插入删除更快（旋转更少）。
AVL 树是一棵 BST，且满足：每个节点的左右子树高度差（平衡因子）的绝对值 ≤ 1。
平衡因子 BF(node) = height(left) - height(right)
合法值：-1, 0, 1
graph TD A[10 h=2] --> B[5 h=1] A --> C[15 h=1] B --> D[3 h=0] B --> E[7 h=0] C --> F[12 h=0] C --> G[20 h=0]
每个节点的 BF 都是 -1、0 或 1，合法 AVL。
当插入/删除导致 BF 变为 ±2 时，需要旋转恢复平衡：
| 失衡类型 | 条件 | 旋转方式 |
|---|---|---|
| LL | BF=2 且左子 BF≥0 | 右旋 |
| RR | BF=-2 且右子 BF≤0 | 左旋 |
| LR | BF=2 且左子 BF<0 | 先左旋再右旋 |
| RL | BF=-2 且右子 BF>0 | 先右旋再左旋 |
private Node rotateRight(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
updateHeight(y);
updateHeight(x);
return x; // 新根
}private Node rotateLeft(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
updateHeight(x);
updateHeight(y);
return y; // 新根
}// LR：先对左子左旋，再对当前节点右旋
node.left = rotateLeft(node.left);
return rotateRight(node);
// RL：先对右子右旋，再对当前节点左旋
node.right = rotateRight(node.right);
return rotateLeft(node);class AVLTree {
class Node {
int val, height;
Node left, right;
Node(int v) { val = v; height = 1; }
}
private Node root;
private int height(Node n) { return n == null ? 0 : n.height; }
private int balanceFactor(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }
private void updateHeight(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }
public void insert(int val) { root = insert(root, val); }
private Node insert(Node node, int val) {
if (node == null) return new Node(val);
if (val < node.val) node.left = insert(node.left, val);
else if (val > node.val) node.right = insert(node.right, val);
else return node; // 不允许重复
updateHeight(node);
return balance(node);
}
private Node balance(Node node) {
int bf = balanceFactor(node);
// LL
if (bf > 1 && balanceFactor(node.left) >= 0) return rotateRight(node);
// LR
if (bf > 1 && balanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
// RR
if (bf < -1 && balanceFactor(node.right) <= 0) return rotateLeft(node);
// RL
if (bf < -1 && balanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
}| 维度 | AVL | 红黑树 |
|---|---|---|
| 平衡严格度 | 严格（高度差≤1） | 宽松（最长≤2×最短） |
| 树高 | 更矮 | 稍高 |
| 查找速度 | 更快 | 略慢 |
| 插入/删除 | 旋转多（可能多次） | 旋转少（最多 3 次） |
| 适用场景 | 读多写少（数据库索引） | 写多读多均衡（Map/Set） |
Java
TreeMap/TreeSet用红黑树；数据库索引用 B+ 树。
面试中很少要求手写 AVL，但需要：
public boolean isBalanced(TreeNode root) {
return checkHeight(root) != -1;
}
private int checkHeight(TreeNode node) {
if (node == null) return 0;
int left = checkHeight(node.left);
if (left == -1) return -1;
int right = checkHeight(node.right);
if (right == -1) return -1;
if (Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
}