3.3 平衡之术：AVL 树与红黑树

3.3 平衡之术：AVL 树与红黑树

本节摘要：平衡树在 BST 之上增加一条"任何节点左右子树高度差至多一"（AVL）或一套着色规则（红黑树）的形状纪律，用旋转在插入删除后修复失衡，把 O(log n) 从"看输入脸色"变成"最坏保证"。本节实现 AVL 插入与四种旋转，复现顺序输入下的救树实验，并对比 AVL 与红黑树的取舍。

给树请一位自动整形师

上一节的退化实验留下一个悬案：BST 的形状由输入决定，而现实输入常常有序。平衡树的思路是在结构内部常驻一位整形师——每次插入或删除后立刻检查每个祖先的平衡因子（左子树高减右子树高），一旦越界就地旋转修复，不给树长歪的机会。

旋转是整门功法的核心招式，本质只有两个基本动作：右旋把左孩子提上来当父、自己降级做右孩子；左旋镜像。旋转前后中序序列完全不变——这是旋转的合法性来源：它改变形状，绝不破坏 BST 不变量。

四种失衡与对应旋转

失衡按"插入点相对失衡祖先的方位"命名：LL（左孩子的左子树长高）右旋一次；RR 左旋一次；LR 与 RL 是折线，双旋掰直。代码里平衡因子与旋转写成独立函数，插入递归回溯时逐层体检：

# AVL 树：插入 + 四种旋转自动修复
class Node:
    def __init__(self, key):
        self.key, self.left, self.right, self.h = key, None, None, 0

def H(n): return n.h if n else -1                 # 空树高 -1
def update(n): n.h = 1 + max(H(n.left), H(n.right))
def bf(n): return H(n.left) - H(n.right)          # 平衡因子

def rot_right(z):                                 # 右旋：左孩子 y 升上来
    y = z.left
    z.left, y.right = y.right, z
    update(z); update(y)
    return y

def rot_left(z):                                  # 左旋：右孩子 y 升上来
    y = z.right
    z.right, y.left = y.left, z
    update(z); update(y)
    return y

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node
    update(node)
    b = bf(node)
    if b > 1 and key < node.left.key:             # LL
        return rot_right(node)
    if b < -1 and key > node.right.key:           # RR
        return rot_left(node)
    if b > 1 and key > node.left.key:             # LR：先左旋左孩子
        node.left = rot_left(node.left)
        return rot_right(node)
    if b < -1 and key < node.right.key:           # RL：先右旋右孩子
        node.right = rot_right(node.right)
        return rot_left(node)
    return node

def height(node):
    return -1 if node is None else node.h

def preorder(node, out):
    if node:
        out.append(node.key)
        preorder(node.left, out)
        preorder(node.right, out)
    return out

root = None
for k in (1, 2, 3, 4, 5, 6, 7):                   # 有序输入：BST 的天敌
    root = insert(root, k)
print("AVL 顺序插入 1 到 7：高度 =", height(root), "，前序 =", preorder(root, []))
# 输出：AVL 顺序插入 1 到 7：高度 = 2 ，前序 = [4, 2, 1, 3, 6, 5, 7]
# 对比上一节：同一输入下普通 BST 高度 6；AVL 靠一路左旋保持矮壮

def search(root, key):
    node, steps = root, 0
    while node:
        steps += 1
        if node.key == key:
            return steps
        node = node.left if key < node.key else node.right
    return steps
print("AVL 查 7 比较次数 =", search(root, 7), "；上一节链状 BST 为 7 次")
# 输出：AVL 查 7 比较次数 = 3 ；上一节链状 BST 为 7 次
​

每个节点插入后至多一次旋转（单旋或双旋）即可恢复 AVL 纪律，旋转本身 O(1)，插入整体仍是 O(log n)。把旋转记进事件簿，能看到整形师的出手规律：

# AVL 旋转事件簿：顺序插入 1 到 7，记录每次失衡与修复招式
class N:
    def __init__(s, k): s.key, s.l, s.r, s.h = k, None, None, 0
def H(n): return n.h if n else -1
def upd(n): n.h = 1 + max(H(n.l), H(n.r))
def bf(n): return H(n.l) - H(n.r)
def rot_r(z):
    y = z.l; z.l, y.r = y.r, z; upd(z); upd(y); return y
def rot_l(z):
    y = z.r; z.r, y.l = y.l, z; upd(z); upd(y); return y
LOG = []
def insert(n, k):
    if n is None: return N(k)
    if k < n.key: n.l = insert(n.l, k)
    else: n.r = insert(n.r, k)
    upd(n)
    b = bf(n)
    if b > 1 and bf(n.l) >= 0: LOG.append(f"插{k}：节点{n.key} LL 失衡 → 右旋"); return rot_r(n)
    if b < -1 and bf(n.r) <= 0: LOG.append(f"插{k}：节点{n.key} RR 失衡 → 左旋"); return rot_l(n)
    if b > 1: LOG.append(f"插{k}：节点{n.key} LR 失衡 → 双旋"); n.l = rot_l(n.l); return rot_r(n)
    if b < -1: LOG.append(f"插{k}：节点{n.key} RL 失衡 → 双旋"); n.r = rot_r(n.r); return rot_l(n)
    return n

root = None
for k in range(1, 8):
    root = insert(root, k)
for line in LOG:
    print(line)
print("最终高度 =", root.h)
# 输出：
# 插3：节点1 RR 失衡 → 左旋
# 插5：节点3 RR 失衡 → 左旋
# 插6：节点2 RR 失衡 → 左旋
# 插7：节点5 RR 失衡 → 左旋
# 最终高度 = 2
# 七次插入出手四次，全是 RR 单旋——有序输入专喂同一种失衡
​

事件簿印证了两件事：有序输入让失衡清一色发生在右路（RR），单旋即可；而每次失衡都出现在离新节点最近的祖先上，修复它之后更上层自动恢复——这正是插入回溯时"遇到第一个失衡点修完就收手"的依据。

红黑树：放宽纪律，少转几圈

AVL 的纪律极严（高度差至多一），换来极矮的树与最快的查找；代价是插入删除时旋转较频繁。红黑树改用一套着色纪律：每个节点红或黑；根与叶空位为黑；红节点的孩子必须全黑（不许红红相邻）；从任一节点到其所有叶空位的黑节点数相同（黑高一致）。这套规则保证最长路径不超过最短路径两倍——树高被压在 2log₂(n+1) 以内，不追求完美平衡，只承诺"大致平衡"。

放宽的回报是维护便宜：插入至多两次旋转、删除至多三次，其余靠重新着色完成（着色是 O(1) 的记账，不用动指针）。这也是工业界的选择倾向：

⚠️ 常见坑：旋转后忘记更新高度。上面代码里 rot_right 与 rot_left 内部先 update 降级节点、再 update 升级节点，顺序不能反——升上来的节点高度依赖降级节点的新高度。漏掉这一步，平衡因子全是错的，树会在后续操作中悄悄歪掉。

走火入魔：两则平衡树迷信

**迷信一：上了平衡树就万事大吉。**平衡树保的是单操作 O(log n)，不保常数。数据规模几千、访问模式固定时，一个精心 sized 的数组加二分（5.4 节）常常更快；缓存友好性上连续内存完胜节点散居的树。工程选型先量规模，再谈结构。

**迷信二：把红黑树当完美平衡树推理。**红黑树高差允许到近两倍，推理时别拿"完全平衡"当前提去算比较次数上界，正确上界是两倍 log 量级。面试里这道边界题专收想当然的人。

💡 关键直觉：AVL 与红黑树的分歧是"查找次数多还是修改次数多"。读多写少选 AVL 的严格；写频繁或要求稳定延迟选红黑树的宽松。没有最好，只有合用。

本节要点回顾

• 平衡树的使命：把 O(log n) 从期望变成最坏保证，代价是插入删除后的检查与旋转；
• 旋转是唯一基本动作（左旋、右旋互为镜像），改变形状但保持中序不变，因而不破坏 BST 不变量；
• 四种失衡：LL 右旋、RR 左旋、LR 与 RL 双旋掰直折线；AVL 每次插入至多一次旋转修复；
• 顺序输入实验：同一批键，AVL 高度 2 对普通 BST 高度 6，查找 3 次对 7 次，可复算；
• 红黑树放宽纪律：黑高一致保证树高不超过两倍 log，换来更少的旋转，是主流语言有序容器的选择。

BST 一族讲完"有序地找"。下一节换一副心肠：只要求"父胜于子"的半序结构——堆，以及它撑起的优先队列。