Olverae Assets

1 一句话定义

AVL 树就是一棵会"自动保持平衡"的二叉搜索树——每次插入/删除后，如果某节点左右子树高度差超过 1，就旋转把它转回来。

普通 BST 像随手堆的书，可能堆成歪歪的一长条（退化成链，查找 O(n)）。AVL 像有个强迫症管理员：每放一本书就检查有没有偏重，一偏就立刻旋转扶正，永远不让树长歪。代价是插入时多做几次旋转，换来查找永远 O(log n)。

平衡因子 BF = 左子树高 − 右子树高。AVL 要求每个节点 BF ∈ {−1, 0, +1}。一旦插入后某节点 BF 变成 ±2，就触发旋转修复。

2 模型 · 四种旋转，每种看一遍

插入会破坏平衡，旋转把它修回来。共 4 种失衡形态：LL / RR / LR / RL。点上面切换、点 ▶ 单步：左边树上每个节点显示 BF，红色 = 失衡（|BF|=2），旋转后节点弹簧式归位、BF 全部回到 0。

AVL 在代码里怎么写？——BST 插入 + 失衡就旋转

AVL 的插入 = 普通 BST 插入，外加"回溯时更新高度 + 检查 BF + 该旋转就旋转"。四种情况靠 失衡节点的 BF 符号 和 新值插到哪边 来区分。

node *insert(node *t, int v) {
    if (t == NULL) return newNode(v);
    if (v < t->value) t->left  = insert(t->left, v);
    else             t->right = insert(t->right, v);
    updateHeight(t);
    int bf = height(t->left) - height(t->right);   // 平衡因子
    // |bf| == 2 → 旋转修复（共 4 种）
    if (bf >  1 && v < t->left->value)  return rightRotate(t);   // LL → 右旋
    if (bf < -1 && v > t->right->value) return leftRotate(t);    // RR → 左旋
    if (bf >  1 && v > t->left->value)  { t->left = leftRotate(t->left);  return rightRotate(t); } // LR
    if (bf < -1 && v < t->right->value) { t->right = rightRotate(t->right); return leftRotate(t); }  // RL
    return t;
}

命名陷阱：左左(LL)用右旋、右右(RR)用左旋——名字和旋转方向是"反"的！LR / RL 是双旋（先转孩子、再转自己，共 2 次）。下面四个演示一一对应这四行 if。

AVL 旋转演示器

当前操作代码（当前行高亮）

各节点平衡因子 BF

提示

选一种失衡类型，点 ▶ 播放，看插入如何把树压歪、再被旋转扶正。

3 核心要点 · 4 句人话看懂 AVL

AVL = BST + "歪了就转正"。

① AVL = BST + 平衡约束

一句话：它首先是一棵 BST（左小右大、中序升序都成立），额外保证每个节点左右子树高度差 ≤ 1。

因为永远平衡，高度恒为 O(log n)，查找/插入/删除都稳定 O(log n)——再也不会退化成链。

是 BST：左 < 根 < 右 + 平衡：|左高 − 右高| ≤ 1

② 平衡因子 BF = 左高 − 右高

一句话：每个节点算一个 BF = 左子树高 − 右子树高。平衡时 BF ∈ {−1, 0, +1}；变成 ±2 就是失衡，要旋转。

空子树高度记 −1（和求树高一致）。BF = +2 表示"左边太重"，−2 表示"右边太重"。

BF = +2 → 左边太重 BF = −2 → 右边太重否则平衡，不用动

③ 失衡就旋转：4 种情况

一句话：看"失衡节点 + 重的那条路"判类型——LL→右旋、RR→左旋、LR→先左后右、RL→先右后左。

单旋（LL/RR）一次搞定；双旋（LR/RL）要两次（先转孩子、再转自己）。名字记的是"哪边重"，方向往往是反的。

LL → rightRotate RR → leftRotate LR → left(子) + right(自) RL → right(子) + left(自)

④ 旋转保持 BST 性质

一句话：旋转只是换爹、重新挂子树，不改变中序顺序——转完还是合法 BST，只是更矮更平衡。

右旋 30：左孩子 20 升为根，30 变成 20 的右孩子，20 原来的右子树挂到 30 的左边。中序遍历前后不变。

30 20 / 右旋 / \ 20 ───→ 10 30 / 10

4 错误实验室 · 点一下亲眼看 bug

AVL 最常翻车在"旋转判断"。点击卡片看症状。

① 旋转方向判反

左左(LL)型却用了左旋 → 越转越歪

② 忘更新高度

旋转后没重算 height → BF 全错，漏检失衡

③ 双旋当单旋

LR/RL 只转一次 → 转完仍然失衡

// 点击上方任一卡片，查看错误与后果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

先在脑子里转一遍，再点选项。

去做例题：AVL 树 · 自平衡插入

去做例题

读完这节，你应该明白：

AVL 就是给 BST 加了一套"自动扶正"机制，专治上一节那个"退化成链"的毛病。它的工作方式是：每个节点算一个平衡因子 BF = 左高 − 右高，插入后一旦某节点 |BF| = 2 就旋转修复（口诀：LL→右旋、RR→左旋、LR/RL 双旋）；而旋转只是重挂父子、不改变中序顺序，所以转完仍是合法 BST、只是更矮更平衡。代价是插入时多转几下，换来查找/插入/删除永远 O(log n)，再也不会退化 ↓

AVL Trees (self-balancing, rotations)

AVL 树