第6章（上）：平衡的意义——从歪斜到旋转

元数据卡

• 前置知识：BST（第5章） | 预计时间：40 分钟 | 核心难度：进阶
• 完成标志：能手画 AVL 的四种旋转，能解释平衡因子

---

你的进度

上一章你学会了 BST——左小右大，查找快如闪电。但老陈师傅把那根贴满标签（1 2 3 4 5）的枯枝往地上一扔："你按顺序插，它就变成一根棍子。"

数据有序，树就退化成链表。

---

破局 · 溯源

1. BST 退化——有序插入 = 链表

按顺序插入 [1, 2, 3, 4, 5]——每次都往右走，树变成一条链：1 -> 2 -> 3 -> 4 -> 5。查找 5 需要走 5 步。n=10000 时走到 10000 步——O(n)。平衡树只要约 14 步（log₂10000）。

// BST退化：有序插入1000个数，查找深度
// 运行: javac Degrade.java && java Degrade
public class Degrade {
    static class N{int v;N l,r;N(int x){v=x;}}
    static N ins(N r,int v){
        if(r==null)return new N(v);
        if(v<r.v)r.l=ins(r.l,v);else r.r=ins(r.r,v);
        return r;
    }
    static int dep(N r,int v,int d){
        if(r==null)return -1;
        if(r.v==v)return d;
        return v<r.v?dep(r.l,v,d+1):dep(r.r,v,d+1);
    }
    public static void main(String[]a){
        N r=null;
        for(int i=1;i<=1000;i++)r=ins(r,i);
        System.out.println("深度: "+dep(r,1000,0)+" (理想: ~10)");
    }
}
// 输出: 深度: 999 (理想: ~10)

2. 旋转——把歪树拧回来

旋转保持 BST 的中序顺序。

右旋：树向右歪，抓住中间节点提上来当根。左旋：对称操作。

   y         x          x           y
  / \       / \        / \         / \
 x  T3  => T1  y      T1  y  =>  x  T3
/ \           / \        / \    / \
T1 T2        T2 T3      T2 T3  T1 T2
  右旋                   左旋

// 旋转操作——中序遍历不变
// 运行: javac Rotate.java && java Rotate
public class Rotate {
    static class N{int v;N l,r;N(int x){v=x;}}
    static N rRot(N y){N x=y.l,t=x.r;x.r=y;y.l=t;return x;}
    static N lRot(N x){N y=x.r,t=y.l;y.l=x;x.r=t;return y;}
    static void pr(N n){
        if(n==null)return;pr(n.l);System.out.print(n.v+" ");pr(n.r);
    }
    public static void main(String[]a){
        N r=new N(10);r.l=new N(5);r.l.l=new N(3);
        pr(r);System.out.print("-> ");pr(rRot(r));
    }
}
// 输出: 3 5 10 -> 3 5 10（顺序不变）

3. AVL 树与平衡因子

光有旋转不够——你得知道什么时候该转。

AVL 树（1962）用一条简单规则解决了这个问题：

任何节点的左右子树高度差不超过 1。

高度差 = 平衡因子 = 左高 - 右高，允许 {-1, 0, 1}。超出范围就需要旋转。

4. 四种失衡模式

模式	条件	修复
LL	左偏高，插入点在左孩子的左侧	右旋
RR	右偏高，插入点在右孩子的右侧	左旋
LR	左偏高，插入点在左孩子的右侧	左旋左孩子 → 右旋
RL	右偏高，插入点在右孩子的左侧	右旋右孩子 → 左旋

// AVL完整插入——自动平衡
// 运行: javac AVLTree.java && java AVLTree
public class AVLTree {
    N root;
    class N{int v,ht=1;N l,r;N(int x){v=x;}}
    int h(N n){return n==null?0:n.ht;}
    int bf(N n){return n==null?0:h(n.l)-h(n.r);}
    N rRot(N y){
        N x=y.l,t=x.r;x.r=y;y.l=t;
        y.ht=1+Math.max(h(y.l),h(y.r));
        x.ht=1+Math.max(h(x.l),h(x.r));return x;
    }
    N lRot(N x){
        N y=x.r,t=y.l;y.l=x;x.r=t;
        x.ht=1+Math.max(h(x.l),h(x.r));
        y.ht=1+Math.max(h(y.l),h(y.r));return y;
    }
    N ins(N n,int v){
        if(n==null)return new N(v);
        if(v<n.v)n.l=ins(n.l,v);
        else if(v>n.v)n.r=ins(n.r,v);
        else return n;
        n.ht=1+Math.max(h(n.l),h(n.r));
        int bal=bf(n);
        if(bal>1&&v<n.l.v)return rRot(n);       // LL
        if(bal<-1&&v>n.r.v)return lRot(n);      // RR
        if(bal>1&&v>n.l.v){n.l=lRot(n.l);return rRot(n);} // LR
        if(bal<-1&&v<n.r.v){n.r=rRot(n.r);return lRot(n);} // RL
        return n;
    }
    public static void main(String[]a){
        AVLTree t=new AVLTree();
        for(int v=1;v<=10;v++)t.root=t.ins(t.root,v);
        System.out.println("AVL树高: "+t.h(t.root)+" (BST链表:10)");
    }
}
// 输出: AVL树高: 4 (BST链表:10)

同样的有序输入 [1..10]，AVL 高度 4，普通 BST 高度 10。旋转真的在起作用。

---

常见陷阱

旋转后更新高度顺序错了。 右旋后 y 变成 x 的孩子——必须先更新 y 再更新 x。反了算出来是旧高度。

---

通关挑战

1. 手画 AVL 插入 [30, 20, 10] 的每一步——何时触发旋转？
2. 口述 LL/RR/LR/RL 的判断标准（往哪歪就往反方向拧）
3. 解释旋转为什么不破坏 BST 的中序顺序

验收标准

• [ ] 能手画四种旋转
• [ ] 能写出 平衡因子 = 左高 - 右高
• [ ] 能解释旋转前后中序遍历不变

---

旅人笔记

BST 遇到有序数据退化成链表。AVL 用"高度差不超过 1" + 四种旋转，让树保持 O(log n)。旋转不是重建，只是把结构拧回正确姿态。

---

下一步

AVL 有一个问题——它太严格了。每次插入都可能触发旋转。下一节介绍更"宽松"的红黑树，它牺牲一点查找效率，换来更少的旋转次数。Java 的 TreeMap 和 C++ 的 std::map 都选它。

→ 红黑树 → 第7章：堆与优先队列