引言 (Introduction)
在本系列前三篇中，我们从二叉树的基础遍历一路深入到最大路径和、Morris 遍历等高阶技巧。然而，一个关键问题始终悬而未决：当输入数据有序或接近有序时，普通的二叉搜索树（BST）会退化成一条链表，使得查找、插入、删除的时间复杂度从理想的 $O(\log N)$ 跌落至 $O(N)$。
AVL 树（Adelson-Velsky & Landis，1962 年提出）是历史上第一个自平衡的二叉搜索树。它通过在每个节点上维护一个平衡因子（Balance Factor），并在插入/删除后自动触发旋转操作，确保树的高度始终保持在 $O(\log N)$ 的水平。
本文是本系列第四篇，在第二篇 BST 理论的基础上，正式进入自平衡二叉树的世界。
1. 平衡的定义与数据结构
一棵 AVL 树满足以下条件：
- 它是一棵二叉搜索树（BST）；
- 每个节点的左右子树高度差（平衡因子）的绝对值不超过 $1$。
令 bf(node) = height(node.left) - height(node.right)，则必须满足 $bf \in \{-1, 0, 1\}$。
我们首先扩展标准 TreeNode，增加 height 字段来追踪每个节点的高度：
from typing import Optional
class AVLNode:
"""AVL 树节点定义"""
def __init__(self, val: int = 0):
self.val = val
self.left: Optional['AVLNode'] = None
self.right: Optional['AVLNode'] = None
self.height: int = 1 # 叶子节点高度为 1
class AVLTree:
"""AVL 树封装"""
def __init__(self):
self.root: Optional[AVLNode] = None
# ---------- 工具函数 ----------
def _get_height(self, node: Optional[AVLNode]) -> int:
"""获取节点高度，空节点高度为 0"""
return node.height if node else 0
def _get_balance(self, node: Optional[AVLNode]) -> int:
"""计算平衡因子 = 左子树高度 - 右子树高度"""
if not node:
return 0
return self._get_height(node.left) - self._get_height(node.right)
def _update_height(self, node: AVLNode) -> None:
"""在旋转或插入后刷新节点高度"""
node.height = 1 + max(self._get_height(node.left),
self._get_height(node.right))
复杂度分析：所有工具函数时间复杂度均为 $O(1)$。
2. 旋转操作：四种失衡场景
当某节点的平衡因子超出 $[-1, 1]$ 范围时，需要通过旋转（Rotation）恢复平衡。共有四种失衡场景。
2.1 LL 型失衡 —— 右旋 (Right Rotation)
场景：在左子树的左侧插入导致 bf(node) > 1 且 bf(node.left) >= 0。
z (bf=2) y
/ / \
y --> x z
/
x
def _rotate_right(self, z: AVLNode) -> AVLNode:
"""LL 型：对 z 执行右旋"""
y = z.left
assert y is not None
# 1. y 的右子树接管给 z 的左边
z.left = y.right
# 2. z 成为 y 的右孩子
y.right = z
# 3. 自底向上刷新高度（先 z 后 y）
self._update_height(z)
self._update_height(y)
return y # 新根
2.2 RR 型失衡 —— 左旋 (Left Rotation)
场景：在右子树的右侧插入导致 bf(node) < -1 且 bf(node.right) <= 0。
z (bf=-2) y
\ / \
y --> z x
\
x
def _rotate_left(self, z: AVLNode) -> AVLNode:
"""RR 型：对 z 执行左旋"""
y = z.right
assert y is not None
# 1. y 的左子树接管给 z 的右边
z.right = y.left
# 2. z 成为 y 的左孩子
y.left = z
# 3. 自底向上刷新高度
self._update_height(z)
self._update_height(y)
return y
2.3 LR 型失衡 —— 先左旋后右旋
场景：在左子树的右侧插入导致 bf(node) > 1 且 bf(node.left) < 0。
z (bf=2) z x
/ / / \
y --> x --> y z
\ /
x y
# LR = 对左孩子左旋 + 对当前节点右旋
z.left = self._rotate_left(z.left)
return self._rotate_right(z)
2.4 RL 型失衡 —— 先右旋后左旋
场景：在右子树的左侧插入导致 bf(node) < -1 且 bf(node.right) > 0。
z (bf=-2) z x
\ \ / \
y --> x --> z y
/ \
x y
# RL = 对右孩子右旋 + 对当前节点左旋
z.right = self._rotate_right(z.right)
return self._rotate_left(z)
2.5 统一的再平衡入口
def _rebalance(self, node: AVLNode) -> AVLNode:
"""根据平衡因子自动选择旋转策略"""
balance = self._get_balance(node)
# LL: 左子树比右子树高，且新节点插在左子树的左边
if balance > 1 and self._get_balance(node.left) >= 0:
return self._rotate_right(node)
# RR: 右子树比左子树高，且新节点插在右子树的右边
if balance < -1 and self._get_balance(node.right) <= 0:
return self._rotate_left(node)
# LR: 左子树比右子树高，且新节点插在左子树的右边
if balance > 1 and self._get_balance(node.left) < 0:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
# RL: 右子树比左子树高，且新节点插在右子树的左边
if balance < -1 and self._get_balance(node.right) > 0:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
3. 插入操作与复杂度
插入分为两步：标准 BST 插入 + 回溯再平衡。
def insert(self, val: int) -> None:
"""插入值 val 并维护 AVL 属性"""
self.root = self._insert(self.root, val)
def _insert(self, node: Optional[AVLNode], val: int) -> AVLNode:
if not node:
return AVLNode(val)
# 1. 标准 BST 插入
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
else:
return node # 重复值不插入
# 2. 自底向上：更新高度 → 检测并修复平衡
self._update_height(node)
return self._rebalance(node)
复杂度分析：
- 时间复杂度：$O(\log N)$。BST 插入沿树高下行 $O(\log N)$，回溯修复每条边只做常数次旋转（至多一次即可恢复整棵树），总计 $O(\log N)$。
- 空间复杂度：$O(\log N)$（递归栈深度即为树高）。
- 高度上界：可以证明，对于 $N$ 个节点的 AVL 树，树高 $h \le 1.44 \log_2(N+1) - 0.328$。推导思路：设 $N_h$ 为高度为 $h$ 的 AVL 树的最少节点数，有递推式 $N_h = N_{h-1} + N_{h-2} + 1$，与斐波那契数列同源，因此 $h = O(\log N)$。
4. LeetCode 实战应用
4.1 #110 平衡二叉树 (Balanced Binary Tree)
题目描述：给定一棵二叉树，判断它是否是高度平衡的二叉树。
此问题与 AVL 平衡因子的概念直接对应。采用自底向上策略，同时返回高度和是否平衡两个信息，避免重复计算：
def is_balanced(root: Optional[AVLNode]) -> bool:
"""LeetCode 110: 判断二叉树是否平衡"""
def check(node: Optional[AVLNode]) -> int:
if not node:
return 0 # 空树高度为 0，且平衡
left_h = check(node.left)
if left_h == -1:
return -1 # 左子树已不平衡，短路
right_h = check(node.right)
if right_h == -1:
return -1 # 右子树已不平衡，短路
if abs(left_h - right_h) > 1:
return -1 # 当前节点不平衡
return 1 + max(left_h, right_h)
return check(root) != -1
复杂度：时间 $O(N)$，空间 $O(H)$。
4.2 #1382 将二叉搜索树变平衡 (Balance a BST)
题目描述：给定一棵 BST，返回任意一棵等价的平衡 BST。
利用 AVL 的思路分两步：先对原 BST 做中序遍历得到有序数组，再递归取中间元素建平衡 BST。这正是 AVL 试图维持的理想结构。
from typing import List
def balance_bst(root: Optional[AVLNode]) -> Optional[AVLNode]:
"""LeetCode 1382: 将 BST 转化为平衡 BST"""
# Step 1: 中序遍历得到有序数组
vals: List[int] = []
def inorder(node: Optional[AVLNode]) -> None:
if not node:
return
inorder(node.left)
vals.append(node.val)
inorder(node.right)
inorder(root)
# Step 2: 二分递归构建平衡 BST
def build(l: int, r: int) -> Optional[AVLNode]:
if l > r:
return None
mid = (l + r) // 2
node = AVLNode(vals[mid])
node.left = build(l, mid - 1)
node.right = build(mid + 1, r)
return node
return build(0, len(vals) - 1)
复杂度：时间 $O(N)$，空间 $O(N)$（存储有序数组）。
4.3 #108 将有序数组转换为二叉搜索树 (Convert Sorted Array to BST)
题目描述：给定升序数组，构造一棵高度平衡的 BST。
这是 #1382 的 Step 2 本身，也是 AVL 树「通过二分选取根节点来保证平衡」思想的直接体现。
def sorted_array_to_bst(nums: List[int]) -> Optional[AVLNode]:
"""LeetCode 108: 有序数组 -> 平衡 BST"""
def build(l: int, r: int) -> Optional[AVLNode]:
if l > r:
return None
mid = (l + r) // 2
node = AVLNode(nums[mid])
node.left = build(l, mid - 1)
node.right = build(mid + 1, r)
return node
return build(0, len(nums) - 1)
结论 (Conclusion)
AVL 树通过旋转这一核心操作，在每次插入后以常数代价修复平衡，为 BST 提供了严格的高度保证（$|bf| \le 1$）。相比普通 BST 在最坏情况下退化为 $O(N)$ 的脆弱性，AVL 树稳定地保持了 $O(\log N)$ 的所有操作复杂度。理解四种旋转场景是掌握 AVL 树的钥匙——而旋转本身，也是下一篇红黑树的核心操作。下一篇我们将探讨在工程实践中应用更广泛的红黑树。