专题进阶 · 树与范围查询推荐总顺序 · 第 50 / 148 课

从高度差定位失衡,区分单旋与双旋,并在回溯时更新高度。

先学会这些,再进入本课 二叉搜索树 后序遍历
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

AVL 树AVL Tree

维护子树高度差不超过 1,旋转恢复平衡,查询更新 O(log n)。

建议 55 分钟 · 含手算、代码与三层练习

本课要建立的能力

从高度差定位失衡,区分单旋与双旋,并在回溯时更新高度。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

普通 BST 连续插入 3、2、1 会变成链。怎样保持搜索顺序,同时把高度恢复到对数级?

02一步步得到方法

局部高度约束带来全局保证

AVL 要求每个节点左右子树高度差的绝对值≤1。本课空树高度 0,叶子 1,平衡因子 balance=h(left)−h(right)。插入先像 BST 一样落到叶子,再沿返回路径更新高度并修复。

高度为 h 的 AVL 至少包含 N(h)=1+N(h−1)+N(h−2) 个节点,按 Fibonacci 速度增长。反过来固定 n 时 h=O(log n),这才是对数查询的依据。

旋转移动连接,不改变中序

左侧太高且左孩子也左高时,对根右旋。设根 z、左孩子 y、y 的右子树 B;将 y 提为根,z 成为 y 的右孩子,B 接到 z 的左侧。键仍满足 A<y<B<z<C。

若左侧太高但新节点落在左孩子的右侧,先对左孩子左旋,把折线变直,再对根右旋。右侧情况镜像得到 RR、RL;四种情形是插入路径的两个方向组合。

高度更新顺序不能反

旋转后原根先变成孩子,因此先更新原根高度,再更新新根高度。调用者必须接住旋转返回的新子树根,否则结构虽然在局部变了,父节点仍指向旧根。删除也需沿路径修复,且可能持续影响多个祖先;本课代码聚焦完整插入。

03把一个小例子完全算清楚

依次插入 3、2、1。

步骤计算与状态为什么这样做
插入 3、2根 3 高度 2,balance=1仍合法
插入 1根 3 的 balance=2左左失衡
右旋 3新根 2,左右孩子 1、3中序仍 [1,2,3]
更新高度1、3 高度 1;2 高度 2恢复平衡

窄屏可左右滑动表格,阅读完整计算与理由。

右旋不是交换两个值,而是重新连接整棵局部子树。

04为什么这个方法成立

  1. BST 插入保持键序,只可能改变插入路径上的高度。
  2. 旋转保留局部中序,因此保留搜索性质。
  3. 单旋或双旋修复当前失衡;回溯逐层检查后,每个节点均满足高度差约束。

05把推导翻译成代码

Python · 可独立运行的教学实现

class Node:
    def __init__(self, key):
        self.key, self.left, self.right, self.height = key, None, None, 1
def height(t):
    return t.height if t else 0
def update(t):
    t.height = 1 + max(height(t.left), height(t.right))
def rotate_right(z):
    y, middle = z.left, z.left.right
    y.right, z.left = z, middle
    update(z); update(y)
    return y
def rotate_left(z):
    y, middle = z.right, z.right.left
    y.left, z.right = z, middle
    update(z); update(y)
    return y
def insert(t, key):
    if t is None:
        return Node(key)
    if key < t.key:
        t.left = insert(t.left, key)
    elif key > t.key:
        t.right = insert(t.right, key)
    else:
        return t
    update(t)
    balance = height(t.left) - height(t.right)
    if balance > 1:
        if key > t.left.key:
            t.left = rotate_left(t.left)
        return rotate_right(t)
    if balance < -1:
        if key < t.right.key:
            t.right = rotate_right(t.right)
        return rotate_left(t)
    return t

逐个理解关键决定

update(z); update(y)
先更新降下去的旧根,再更新升上来的新根。
t.left = rotate_left(t.left)
LR 先修孩子方向,再进行根右旋。
return rotate_right(t)
旋转后的新根必须向上一层返回。

06时间、空间与实现范围

每个祖先做常数次检查和旋转,插入 O(log n),查询 O(log n)。

节点额外保存高度,树存储 O(n),递归插入栈 O(log n)。

07改变条件,检查哪里会出错

只把根的平衡因子检查一遍

内部子树也必须平衡;沿插入路径从下到上修复。

四种旋转条件直接用于删除

删除时子树形态判断不同,不能用被删 key 的比较套入插入分支。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

插入 3、1、2 应做什么?

需要一点提示

左孩子右侧变高。

查看解析与答案

LR:先左旋节点 1,再右旋节点 3,得到根 2、孩子 1 和 3。

练习 2 · 边界与辨析

旋转后中序为什么不变?

需要一点提示

写出 A,y,B,z,C 的次序。

查看解析与答案

两种结构中序都为 A,y,B,z,C,B 只改变父节点,不改变键值区间。

练习 3 · 变式与迁移

为什么不每次重新递归计算整棵子树高度?

需要一点提示

重复扫描代价。

查看解析与答案

会增加重复工作;缓存高度并在局部更新,让每个回溯节点的检查保持 O(1)。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。