二叉树旋转重构定理

核心定理

$O(n)$ 次旋转可以将一棵二叉树转换为任何其他具有相同遍历顺序的二叉树

定理证明

证明思路：双向构造法

步骤1：任意树 → 规范右链（Canonical Chain）

def to_canonical_chain(tree):
    """将任意二叉树转换为右链结构"""
    rotations = 0
    while tree 不是右链:
        # 找到中序遍历中最后可能的右旋转位置
        node = find_last_rotatable_node(tree)
        if node 存在左子树:
            tree = right_rotate(node)  # 执行右旋转
            rotations += 1
    return tree, rotations

关键观察：

每次右旋转使中序遍历最后一个节点的深度增加 1
最终链中最后一个节点深度 = $n - 1$
因此最多需要 $n - 1$ 次旋转

步骤2：规范右链 → 目标树

def chain_to_target(chain, target_tree):
    """从规范链反向旋转到目标树"""
    rotations = 0
    current = chain
    # 通过反向旋转序列到达目标结构
    while current 的结构 != target_tree:
        # 选择适当的旋转操作
        if 需要左旋转:
            current = left_rotate(current)
        else:
            current = right_rotate(current)
        rotations += 1
    return current, rotations

旋转操作详解

基本旋转类型

右旋转（Right Rotation）

初始状态:
    y
   / \
  x   C
 / \
A   B

右旋转后:
  x
 / \
A   y
   / \
  B   C

数学性质：保持中序遍历顺序 A → x → B → y → C 不变

左旋转（Left Rotation）

初始状态:
  x
 / \
A   y
   / \
  B   C

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

旋转操作的性质

性质	说明
保持遍历顺序	旋转前后中序遍历结果相同
局部操作	只影响旋转节点及其直接子树
时间复杂度	每次旋转 $O(1)$
可逆性	左旋转与右旋转互为逆操作

复杂度分析

旋转次数上界

阶段	最大旋转次数	说明
任意树 → 规范链	$\leq n-1$	每个节点最多被"提升"一次
规范链 → 目标树	$\leq n-1$	反向操作对称
总计	$\leq 2(n-1)$	$O(n)$

数学推导

设树有 $n$ 个节点：

规范链中最后一个节点的深度： $n-1$
从任意树到规范链：最多需要 $n-1$ 次旋转（每次增加深度1）
反向操作同理：最多 $n-1$ 次旋转
总旋转次数： $\leq 2(n-1) = O(n)$

具体示例演示

示例：重构二叉树

初始树（中序遍历：A, B, C, D, E）

    C
   / \
  B   E
 /   /
A   D

目标树（相同中序遍历）

  B
 / \
A   D
   / \
  C   E

重构步骤

阶段1：转换为规范链

步骤1: 在C处右旋转
    B
   / \
  A   C
       \
        E
       /
      D

步骤2: 在E处右旋转  
    B
   / \
  A   C
       \
        D
         \
          E

阶段2：从链到目标树

步骤3: 在D处左旋转
    B
   / \
  A   D
     / \
    C   E

总旋转次数：3次（ $< 2(5-1) = 8$ ）

AVL 树：高度平衡

AVL 树的基本性质

AVL 属性（高度平衡属性）

一个节点是高度平衡的，如果它的左子树和右子树的高度差最多为 1。

偏斜度（Skew）定义

节点的偏斜度 = 右子树高度 - 左子树高度

平衡条件：偏斜度 ∈ {-1, 0, 1}

def is_avl_balanced(node):
    """检查节点是否满足 AVL 平衡条件"""
    if node is None:
        return True
    
    left_height = get_height(node.left)
    right_height = get_height(node.right)
    skew = right_height - left_height
    
    return abs(skew) <= 1  # 偏斜度在 [-1, 0, 1] 范围内

高度平衡的理论保证

核心定理

具有高度平衡节点的二叉树的高度 $h = O(\log n)$

等价表述： $n = 2^{\Omega(h)}$ （节点数随高度指数增长）

证明思路：最小节点数分析

定义 $F(h)$ 为高度 $h$ 的 AVL 树的最少节点数：

边界条件

$F(0) = 1\quad \text{(只有根节点)}$
$F(1) = 2 \quad \text{(根节点 + 1个子节点)}$

递归关系

由于要求平衡，高度为 $h$ 的树必须包含：

1 个根节点
1 个高度为 $h-1$ 的子树
1 个高度至少为 $h-2$ 的子树（为了平衡）

因此：

$F(h) = 1 + F(h-1) + F(h-2)$

下界推导

$F(h) = 1 + F(h-1) + F(h-2) \geq F(h-1) + F(h-2) \geq 2F(h-2)$

递推得到：
$F(h) \geq 2F(h-2) \geq 2^2F(h-4) \geq \cdots \geq 2^{h/2}F(0) = 2^{h/2}$

因此：
$n \geq F(h) \geq 2^{h/2} \implies h \leq 2\log_2 n = O(\log n)$

AVL 树的动态维护

插入/删除后的影响

当在高度平衡树中添加或删除叶子节点时：

影响范围：只有该叶子节点的祖先节点的子树高度会改变
高度变化：每个受影响节点的高度变化最多为 ±1
偏斜度变化：偏斜度的幅度仍然 ≤ 2

重新平衡策略

自底向上修复

def avl_fixup(node):
    """从叶子节点向上修复 AVL 平衡"""
    while node is not None:
        # 检查当前节点是否失衡
        if not is_avl_balanced(node):
            # 重新平衡这个节点
            node = rebalance(node)
        
        # 更新当前节点的高度
        update_height(node)
        
        # 继续向上检查父节点
        node = node.parent

重新平衡最低失衡祖先

算法策略：从叶子节点开始向上，重新平衡第一个遇到的不平衡祖先节点

不失一般性：假设偏斜度为 2（右子树太重）

偏斜度为 -2 的情况对称处理

重新平衡操作分类

根据偏斜度情况的旋转策略

情况1：偏斜度 = 2（右子树太重）

def rebalance_right_heavy(node):
    """重新平衡右子树太重的节点"""
    right_child = node.right
    right_skew = get_skew(right_child)
    
    if right_skew >= 0:    # 右右情况 (Right-Right)
        return left_rotate(node)
    else:                  # 右左情况 (Right-Left)
    #先旋转右子节点，后面再左旋转本节点
        node.right = right_rotate(right_child)
        return left_rotate(node)

情况2：偏斜度 = -2（左子树太重）

def rebalance_left_heavy(node):
    """重新平衡左子树太重的节点"""
    left_child = node.left
    left_skew = get_skew(left_child)
    
    if left_skew <= 0:     # 左左情况 (Left-Left)
        return right_rotate(node)
    else:                  # 左右情况 (Left-Right)
        node.left = left_rotate(left_child)
        return right_rotate(node)

性能分析

时间复杂度保证

操作	时间复杂度	说明
查找	$O(\log n)$	树高度为 $O(\log n)$
插入	$O(\log n)$	查找位置 + 向上重新平衡
删除	$O(\log n)$	查找位置 + 向上重新平衡
旋转操作	$O(1)$	每次操作只影响常数个节点

空间复杂度

存储开销：每个节点需要存储高度信息（ $O(1)$ 额外空间）
递归栈： $O(\log n)$ （平衡树的高度）

实际示例

插入操作示例

这边给出原pdf中的部分

在这里插入图片描述

AVL 树全局重新平衡与高度计算

全局重新平衡定理

定理陈述

向高度平衡树 $T$ 添加或删除叶子节点得到 $T'$ ，则最多通过 $O(\log n)$ 次旋转可将 $T'$ 转换为高度平衡树 $T''$

证明思路

影响范围分析

def affected_ancestors(leaf):
    """只有叶子节点的祖先节点会受到影响"""
    ancestors = []
    current = leaf.parent
    while current is not None:
        ancestors.append(current)
        current = current.parent
    return ancestors  # 最多 h = O(log n) 个节点

关键观察：

只有受影响叶子节点的祖先节点的子树高度可能改变
祖先节点数量： $h = O(\log n)$ （因为树是平衡的）

插入操作分析

def handle_insertion(imbalanced_node):
    """处理插入导致的失衡"""
    # 插入增加了节点高度，属于案例2或3
    if imbalanced_node.skew == 2:  # 右子树太重
        if imbalanced_node.right.skew >= 0:
            return left_rotate(imbalanced_node)  # 案例1&2
        else:
            return right_left_rotate(imbalanced_node)  # 案例3

插入特性：

旋转操作降低子树高度
通常一次旋转即可恢复平衡

删除操作分析

def handle_deletion(imbalanced_node):
    """处理删除导致的失衡"""
    # 删除可能引起连锁反应
    current = imbalanced_node
    while current is not None and not is_balanced(current):
        current = rebalance(current)  # 重新平衡当前节点
        current = current.parent  # 继续检查父节点

删除特性：

可能需要在整个祖先链上重新平衡
但最多 $O(\log n)$ 个节点需要检查

高度计算优化策略

朴素方法的问题

def naive_height(node):
    """朴素的高度计算方法 - Ω(n) 时间"""
    if node is None:
        return -1
    left_height = naive_height(node.left)   # 递归计算
    right_height = naive_height(node.right) # 递归计算
    return 1 + max(left_height, right_height)

问题：每次都需要递归计算，时间复杂度 $\Omega(n)$

解决方案：节点增强（Augmentation）

在每个节点类中都设置一个height存储高度

增强设计

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
        self.height = 0  # 新增：存储子树高度

常数时间高度计算

def get_height(node):
    """O(1) 时间获取节点高度"""
    if node is None:
        return -1
    return node.height  # 直接返回存储的高度

def compute_height_from_children(node):
    """根据子节点高度计算当前节点高度"""
    left_height = get_height(node.left)
    right_height = get_height(node.right)
    return 1 + max(left_height, right_height)

高度维护机制

旋转操作中的高度更新

def left_rotate(x):
    """左旋转并更新高度"""
    y = x.right
    x.right = y.left
    y.left = x
    
    # 更新受影响节点的高度
    x.height = compute_height_from_children(x)
    y.height = compute_height_from_children(y)
    
    return y

关键点：只有旋转直接涉及的节点需要更新高度，祖先节点高度不变。

插入/删除操作的高度维护

def update_ancestor_heights(node):
    """更新从节点到根路径上所有节点的高度"""
    current = node
    while current is not None:
        old_height = current.height
        new_height = compute_height_from_children(current)
        
        if old_height == new_height:
            break  # 高度未改变，可以提前终止
        
        current.height = new_height
        current = current.parent  # 继续向上更新

完整的AVL插入操作

def avl_insert(root, key):
    """完整的AVL树插入操作"""
    # 1. 标准BST插入
    new_node = bst_insert(root, key)
    
    # 2. 更新祖先高度
    update_ancestor_heights(new_node)
    
    # 3. 从新节点向上检查平衡
    current = new_node
    while current is not None:
        if not is_balanced(current):
            # 重新平衡并更新高度
            current = rebalance(current)
            update_ancestor_heights(current)
        
        current = current.parent
    
    return find_root(new_node)

时间复杂度分析

各操作的时间复杂度

操作	时间复杂度	说明
高度查询	$O(1)$	直接访问存储的高度
单次旋转	$O(1)$	更新常数个节点的高度
高度更新链	$O(\log n)$	最多更新 $\log n$ 个祖先
重新平衡	$O(\log n)$	最多处理 $\log n$ 个失衡节点
完整插入	$O(\log n)$	查找 + 更新 + 重新平衡
完整删除	$O(\log n)$	查找 + 更新 + 重新平衡

空间复杂度分析

每个节点： $O(1)$ 额外空间存储高度
总空间： $O(n)$ ，与标准BST相同

实际实现考虑

高度维护的优化技巧

def smart_height_update(node):
    """智能高度更新：只有必要时才更新"""
    while node is not None:
        old_height = node.height
        new_height = 1 + max(get_height(node.left), get_height(node.right))
        
        if old_height == new_height:
            return  # 高度未改变，提前退出
        
        node.height = new_height
        node = node.parent

批量操作优化

对于连续的插入/删除操作，可以考虑：

延迟重新平衡：累积多个操作后一次性重新平衡
批量高度更新：优化更新路径的计算

总结

理论贡献

全局平衡保证： $O(\log n)$ 次旋转即可恢复全局平衡
高效维护机制：通过节点增强实现 $O(1)$ 高度查询
最优时间复杂度：所有动态操作保持 $O(\log n)$

实践意义

AVL树的这种设计模式展示了：

增强数据结构的强大威力
局部更新避免全局重新计算
理论界限在实际中的可达成性

正是这种精妙的高度维护机制，使得AVL树能够在动态操作中高效维持严格平衡！