算法与数据结构 · 第 14 课

AVL 平衡树:旋转为什么能保持顺序,又如何保证最坏 (O(\log n))?

2026 年 11 月 2 日|第 3 周 · 第 1 天|讲授约 17 分钟,自测另计

第 2 周讨论哈希表:在随机性与负载条件下获得期望 (O(1)) 查询。今天开始“高级树”,关注另一种保证:即使输入顺序极端不利,也能对比较型字典的查找、插入给出最坏 (O(\log n)) 时间。

一、学习目标与记号(约 2 分钟)

本课需要掌握:二叉搜索树(BST)的顺序不变量;为何普通 BST 会退化;AVL 的高度与平衡因子;单旋、双旋的指针变化;插入的正确性与复杂度证明。

规定只存互异键,重复插入只更新对应值。空子树高度 (h(\varnothing)=-1),叶子高度 (0)。对节点 (v),定义

[ h(v)=1+\max(h(v.left),h(v.right)),\qquad BF(v)=h(v.left)-h(v.right). ]

BST 不变量是:对每一个节点 (v),左子树所有键小于 (v.key),右子树所有键大于 (v.key)。AVL 在此基础上额外要求每个节点都满足 ( BF(v) \le1),不是只检查根节点。

二、动机:有序插入怎样毁掉普通 BST?(约 2 分钟)

假设依次插入键 (10,20,30,40,50)。普通 BST 若不调整结构,会变成一条向右的链:

10
  \
   20
     \
      30
        \
         40
           \
            50

搜索 50 必须逐个访问 5 个节点;推广到 (n) 个有序插入,树高为 (n-1),查询最坏 (\Theta(n))。而哈希表不天然提供范围顺序或有序遍历。AVL 想同时保留BST 的有序性和对抗插入顺序下的高度上界。

三、旋转的本质:改变形状,不改变中序顺序(约 3 分钟)

看下面的左旋。要求 (x) 有右孩子 (y),并且 (A,B,C) 是三棵可能为空的子树:

左旋前:                    左旋后:
       x                          y
      / \                        / \
     A   y                      x   C
        / \                    / \
       B   C                  A   B

旋转前 BST 顺序是 (A < x < B < y < C);旋转后仍是同一顺序,所以全部键的中序遍历不变。右旋是完全对称的逆操作。改变的仅是局部父子指针与子树归属;若节点维护了高度、子树大小等辅助信息,则必须重新计算。

ROTATE_LEFT(x):
    y = x.right                   # 必须非空
    B = y.left
    y.left = x
    x.right = B
    update_height(x)              # 先更新下降后的旧根
    update_height(y)
    return y                      # 父节点/整树根应接住新根

为简化展示,伪代码通过“返回新子树根”处理父指针;若实际实现存有 parent 指针,还需同步维护它们。

为什么先更新 (x) 再更新 (y)?左旋后 (y) 的高度依赖其左孩子 (x) 的新高度。右旋时也先更新下降的旧根,再更新上升的新根。

四、AVL 插入怎样选择旋转?(约 3 分钟)

新键按 BST 规则插入叶位置,再从插入点向上更新高度。某个节点若 ( BF \le1),暂时合法;若达到 (+2) 或 (-2),按照较高的子树方向修复。
flowchart TD
    A["BST 方式插入新叶"] --> B["沿递归返回路径更新 height 与 BF"]
    B --> C{"BF(v) 是否失衡?"}
    C -->|"−1、0、+1"| D["当前节点已平衡,返回"]
    C -->|"+2:左侧过高"| E{"BF(v.left)<0?"}
    C -->|"−2:右侧过高"| F{"BF(v.right)>0?"}
    E -->|否| G["LL:右旋 v"]
    E -->|是| H["LR:先左旋左孩子,再右旋 v"]
    F -->|否| I["RR:左旋 v"]
    F -->|是| J["RL:先右旋右孩子,再左旋 v"]

这里 LL/LR/RR/RL 描述从失衡节点看高度增长的方向;不是只根据最后插入的键大小猜旋转。对 AVL 插入而言,第一次遇到失衡节点时,较高孩子的平衡因子不会是 0;上图的等号方向对删除也能作为基本再平衡框架。

AVL_INSERT(v, key, value):
    if v == null:
        return Node(key, value, height=0)
    if key < v.key:
        v.left = AVL_INSERT(v.left, key, value)
    else if key > v.key:
        v.right = AVL_INSERT(v.right, key, value)
    else:
        v.value = value; return v

    update_height(v)
    if BF(v) > 1:
        if BF(v.left) < 0:
            v.left = ROTATE_LEFT(v.left)
        return ROTATE_RIGHT(v)
    if BF(v) < -1:
        if BF(v.right) > 0:
            v.right = ROTATE_RIGHT(v.right)
        return ROTATE_LEFT(v)
    return v

正确性不变量分成两层:递归前后节点集合与 BST 顺序正确;每次递归返回的子树都已按局部规则恢复 AVL 平衡,且高度字段准确。旋转保持中序顺序;对插入导致的第一个失衡祖先,合适的单旋或双旋恢复平衡后,这个子树的高度回到插入前的高度,因而更高祖先不会因为这次插入继续失衡。这也是 AVL 插入最多使用两次基本旋转的原因;伪代码虽然回溯检查祖先,但不会再次需要旋转。

五、手工 Trace:一次 LR 还不够(约 2 分钟)

从空树依次插入 ([40,20,30,10,25,22]):

插入后 首个失衡节点 修复 当前根
40 无 无 40
20 无 无 40
30 40 LR:先左旋 20,再右旋 40 30
10 无 无 30
25 无 无 30
22 30 LR:先左旋 20,再右旋 30 25

最后一次插入 22 后、修复前的树:

        30
       /  \
     20    40
    /  \
  10    25
        /
       22

此时 (BF(30)=2),而 (BF(20)=-1),属于 LR。先左旋 20,再右旋 30:

        25
       /  \
     20    30
    / \      \
   10 22      40

键的中序顺序始终是 (10,20,22,25,30,40)。请注意:旋转不是对键做排序,而是用局部指针调整保持既有顺序并降低高度。

六、为什么能证明高度 (O(\log n))?(约 3 分钟)

不能只说“每个节点左右高度差最多 1,所以大概平衡”;我们要证明节点数与高度的关系。

定义 (N(h)) 为高度恰好为 (h) 的 AVL 树所需最少节点数。边界为

[ N(-1)=0,\qquad N(0)=1. ]

当 (h\ge1),为了用最少节点达到高度 (h),一侧孩子高度必须为 (h-1),另一侧允许最低为 (h-2);更低则违反 AVL 条件。因此

[ \boxed{N(h)=1+N(h-1)+N(h-2).} ]

前几项:(N(0)=1,N(1)=2,N(2)=4,N(3)=7,N(4)=12)。它与 Fibonacci 数列相连:若 (F_0=0,F_1=1),则 (N(h)=F_{h+3}-1)。

由于 Fibonacci 数以 (\varphi=(1+\sqrt5)/2>1) 的指数速度增长,有常数 (c>0) 使充分大 (h) 时

[ n\ge N(h)\ge c\varphi^h \quad\Longrightarrow\quad \boxed{h\le\log_\varphi(n/c)=O(\log n).} ]

搜索只走一条根到叶路径,最坏 (O(\log n))。插入沿同一条路径回溯,每个节点维护高度耗 (O(1)),且至多做两次 (O(1)) 旋转,因此最坏也是 (O(\log n))。树本体占 (O(n)) 空间,递归 INSERT 的额外栈空间 (O(\log n))。

七、前提、边界与反例(约 1 分钟)

AVL 的保证是确定性的最坏界,不依赖随机键分布;但它也不能让查找变成最坏 (O(1))。旋转前必须确认相应孩子非空;返回的新子树根必须正确接到父节点,必要时更新 parent 指针。重复键若只更新值,不增加节点,不必改变高度。

删除和插入不同。 删除后子树高度可能继续下降,即使某个失衡节点修复了,祖先仍可能失衡,因此 AVL 删除可能需要沿祖先链多次重新平衡;下一节再进入更一般的“树上维护附加信息”时,会重复使用本节的旋转局部性思想。

八、小结与下一课(约 1 分钟)

关键逻辑链是:

[ \text{BST 顺序不变量} \longrightarrow \text{旋转保持中序顺序} \longrightarrow \text{每个节点 }|BF|\le1 \longrightarrow N(h)\text{ 的 Fibonacci 递推} \longrightarrow h=O(\log n). ]

下一课(2026-11-03,第 15 课): 秩统计树(Order-Statistic Tree)。在平衡树节点上维护子树大小,用 (O(\log n)) 时间回答“第 (k) 小”和“某键的排名”,并证明旋转时为什么只需局部更新 size。

九、四级自测(总分 100;首次只给中立提示)

前三题可客观判分,最后一题要求完整推导。课堂正文不公布答案或解析。

Lv1|机制辨析:旋转与平衡约束|15 分|预计 2 分钟|单选

关于二叉搜索树旋转与 AVL 平衡条件,以下哪一项严格正确?

A. 只要根节点满足左右子树高度差不超过 1,整棵树就是 AVL 树。

B. 正确的左旋或右旋保持中序键序不变;局部结构改变后必须自底向上更新受影响节点的高度。

C. 即使节点没有右孩子,也能对它直接执行标准左旋。

D. AVL 每次插入新键以后,都至少需要执行一次旋转。

中立提示:分别检查 AVL 的约束覆盖哪些节点、旋转对键顺序的影响,以及旋转所需的孩子节点。

Lv2|六次 AVL 插入的完整 Trace|20 分|预计 4 分钟|数值

从空 AVL 树开始,依次插入互异键 [20,40,30,50,10,5]。在每次插入后立即按 AVL 规则修复失衡。把一次单左旋或单右旋各计为 1 次基本旋转;一次 LR/RL 双旋计为 2 次。整个插入过程中,基本旋转总次数是多少?

中立提示:先检查前三次插入是否形成 RL,再观察后续插入是否在左子树引发新的失衡。

Lv3|不变量、反例与复杂度边界|25 分|预计 4 分钟|多选

以下关于 AVL 树的说法哪些成立?(多选,选出全部正确项)

A. 在旋转指针和子树连接正确的前提下,单次左旋或右旋不会改变整棵树的中序遍历结果。

B. 某棵 BST 的根节点平衡因子为 0,就能推出这棵 BST 的所有节点均满足 AVL 条件。

C. AVL 插入可在自底向上遇到的第一个失衡祖先处修复并停止进一步旋转;AVL 删除却可能使失衡继续向上传播。

D. AVL 树最坏高度仍可能是 n-1,因此最坏查找时间是 Θ(n)。

中立提示:从“每个节点”与“只有根节点”的区别出发;再比较插入修复与删除后子树高度的变化。

Lv4|设计、旋转正确性与高度下界|40 分|预计 10 分钟|开放推导

设计一个仅存互异键的 AVL 字典,空树高度定义为 -1,叶子高度为 0,BF(v)=height(v.left)-height(v.right)。(a)(12分)写出 INSERT 的递归伪代码,涵盖 BST 插入、更新高度和 LL/LR/RR/RL 修复,说明首次失衡修复为何足以处理插入;(b)(10分)用左旋前后子树 A、B、C 的键序关系严格证明旋转保持 BST 不变量,并说明高度更新顺序;(c)(12分)定义 N(h) 为高度 h 的 AVL 树最少节点数,给出边界与递推式,证明树高为 O(log n),据此推出查找和插入的最坏时间;(d)(6分)说明重复键、空子树和删除操作的边界,以及空间复杂度。

中立提示:旋转只改局部父子指针;最少节点的 AVL 树会让两棵孩子子树的高度相差恰好 1。对删除,不要直接沿用“插入只需一处修复”的结论。

十、作答与反馈

请回复 Lv1:选项;Lv2:旋转次数及关键结构;Lv3:全部正确选项;Lv4:(a)–(d) 分步证明。我会按 15/20/25/40 分逐题批改:80–100 分继续原定课号,60–79 分补一题针对练习,低于 60 分优先复习旋转的键序不变量与 Fibonacci 高度递推。补练不改变按自然日计算的课号。