hello-algo 中的 AVL 树：平衡因子、四种旋转与自底向上的再平衡实现

本文基于《Hello 算法》（hello-algo）树结构章节中的 AVL 树文档展开，系统讲解 AVL 树为何能避免二叉搜索树退化为链表、节点高度与平衡因子的精确定义、右旋/左旋/双旋转四种失衡情形的判定条件，以及插入、删除时“自底向上旋转”的完整递归流程。读完后你将理解 AVL 树保持 $O(\log n)$ 操作复杂度的底层机制，并能对照仓库中 Python 实现、C++ 实现 与 Rust 实现 逐行读懂一遍可运行的参考代码。

为什么需要 AVL 树：二叉搜索树的退化问题

在“二叉搜索树”章节中我们提到，在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从 $O(\log n)$ 劣化为 $O(n)$。

上图给出了一个典型例子：经过两次删除节点操作后，一棵原本结构良好的二叉搜索树便退化成了一条“右斜链表”。同样地，在一棵完美二叉树中连续插入两个较小值的节点后，树也会严重向左倾斜，查找操作随之劣化。

1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在论文 “An algorithm for the organization of information” 中提出了 AVL 树。论文中详细描述了一系列操作，确保在持续添加和删除节点后，AVL 树不会退化，从而使得各种操作的时间复杂度保持在 $O(\log n)$ 级别。换句话说，在需要频繁进行增删查改操作的场景中，AVL 树能始终保持高效的数据操作性能，具有很好的应用价值。

AVL 树常见术语

AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质，因此是一种平衡二叉搜索树（balanced binary search tree）。

节点高度：为什么每个节点都要存 height 字段

AVL 树的相关操作需要频繁获取节点高度。如果每次都需要递归遍历子树去“现算”，单次操作开销会上升到 $O(n)$，破坏平衡维护的性价比。因此 hello-algo 的实现选择在节点类中直接为每个节点添加 height 变量，并在每次结构变化后增量更新。

以 Python 实现为例，节点类为：

class TreeNode:
    """AVL 树节点类"""
    def __init__(self, val: int):
        self.val: int = val                 # 节点值
        self.height: int = 0                # 节点高度
        self.left: TreeNode | None = None   # 左子节点引用
        self.right: TreeNode | None = None  # 右子节点引用

仓库中所有语言的 AVL 实现都遵循同一结构，例如 C++ 版 的 struct TreeNode 包含 val、height、left、right 四个成员；Rust 版 则使用 Rc<RefCell<TreeNode>> 来表达可变共享的子节点引用。Python 版复用的公共节点定义见 tree_node.py，其中 TreeNode.__init__ 同样带有 self.height: int = 0 字段。

“节点高度”是指从该节点到它的最远叶节点的距离，即所经过的“边”的数量。需要特别注意的是，叶节点的高度为 $0$，而空节点的高度为 $-1$。仓库为这两个约定各提供了工具函数：

def height(self, node: TreeNode | None) -> int:
    """获取节点高度"""
    # 空节点高度为 -1 ，叶节点高度为 0
    if node is not None:
        return node.height
    return -1

def update_height(self, node: TreeNode | None):
    """更新节点高度"""
    # 节点高度等于最高子树高度 + 1
    node.height = max([self.height(node.left), self.height(node.right)]) + 1

空节点高度取 $-1$ 这一约定是刻意设计的：它使得 update_height 的公式对叶节点也统一成立——叶节点的两个子节点都是空节点，max(-1, -1) + 1 = 0，恰好等于叶节点高度 $0$，无需特判。

节点平衡因子

节点的平衡因子（balance factor）定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为 $0$。获取节点平衡因子的功能同样被封装成函数：

def balance_factor(self, node: TreeNode | None) -> int:
    """获取平衡因子"""
    # 空节点平衡因子为 0
    if node is None:
        return 0
    # 节点平衡因子 = 左子树高度 - 右子树高度
    return self.height(node.left) - self.height(node.right)

设平衡因子为 $f$，则一棵 AVL 树的任意节点的平衡因子皆满足 $-1 \le f \le 1$。后文所有旋转逻辑都建立在这一不等式之上。

AVL 树旋转：四种失衡情形与选择策略

AVL 树的特点在于“旋转”操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持“二叉搜索树”的性质，也能使树重新变为“平衡二叉树”。

我们将平衡因子绝对值 $> 1$ 的节点称为“失衡节点”。根据节点失衡情况的不同，旋转操作分为四种：右旋、左旋、先右旋后左旋、先左旋后右旋。下面逐一介绍这些旋转操作。

右旋：以左子节点为原点“压下来”

从底至顶看，二叉树中首个失衡节点记为 node，其左子节点记为 child，执行“右旋”操作。完成右旋后，子树恢复平衡，并且仍然保持二叉搜索树的性质。当 child 有右子节点（记为 grand_child）时，右旋需要添加一步：将 grand_child 作为 node 的左子节点。

“向右旋转”是一种形象化的说法，实际上需要通过修改节点指针来实现。Python 参考实现如下：

def right_rotate(self, node: TreeNode | None) -> TreeNode | None:
    """右旋操作"""
    child = node.left
    grand_child = child.right
    # 以 child 为原点，将 node 向右旋转
    child.right = node
    node.left = grand_child
    # 更新节点高度
    self.update_height(node)
    self.update_height(child)
    # 返回旋转后子树的根节点
    return child

从源码结构看，指针修改只有三行核心语句：先保存 grand_child = child.right（这是唯一会被“顶走”的子树），再让 child 上移成为新根（child.right = node），最后把 grand_child 挂到 node 的左侧（node.left = grand_child）。旋转后必须自底向上更新 node 与 child 的高度——node 的子树变小了，child 的子树变大了，两者都可能变化。C++ 版 rightRotate 与 Rust 版 right_rotate 的指针操作与此逐句对应，只是 Rust 通过 borrow()/borrow_mut() 管理可变性。

左旋：右旋的镜像

如果考虑失衡二叉树的“镜像”，则需要执行“左旋”操作。同理，当节点 child 有左子节点（记为 grand_child）时，需要在左旋中添加一步：将 grand_child 作为 node 的右子节点。

可以观察到，右旋和左旋操作在逻辑上是镜像对称的，它们分别解决的两种失衡情况也是对称的。基于对称性，只需将右旋实现代码中所有的 left 替换为 right，将所有的 right 替换为 left，即可得到左旋实现：

def left_rotate(self, node: TreeNode | None) -> TreeNode | None:
    """左旋操作"""
    child = node.right
    grand_child = child.left
    # 以 child 为原点，将 node 向左旋转
    child.left = node
    node.right = grand_child
    # 更新节点高度
    self.update_height(node)
    self.update_height(child)
    # 返回旋转后子树的根节点
    return child

双旋转：先左旋后右旋 / 先右旋后左旋

存在一类失衡，仅用单旋无法修复：失衡节点的一侧子树本身是“反向倾斜”的。此时需要两次旋转——先对 child 执行一次单旋把它“转正”，再对 node 执行单旋。

• 先左旋后右旋：失衡节点的左子节点 child 自身向右倾斜（child 的平衡因子为负），先对 child 左旋、再对 node 右旋；
• 先右旋后左旋：镜像情形，失衡节点的右子节点 child 自身向左倾斜，先对 child 右旋、再对 node 左旋。

下图给出了全部四种失衡情况与旋转操作的一一对应关系：

旋转的选择：一张判定表

我们通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号，来确定失衡节点属于上图中哪种情况：

失衡节点的平衡因子	子节点的平衡因子	应采用的旋转方法
$> 1$ （左偏树）	$\geq 0$	右旋
$> 1$ （左偏树）	$< 0$	先左旋后右旋
$< -1$ （右偏树）	$\leq 0$	左旋
$< -1$ （右偏树）	$> 0$	先右旋后左旋

为了便于使用，仓库将旋转操作封装成一个 rotate 函数。有了这个函数，我们就能对各种失衡情况进行旋转，使失衡节点重新恢复平衡：

def rotate(self, node: TreeNode | None) -> TreeNode | None:
    """执行旋转操作，使该子树重新恢复平衡"""
    # 获取节点 node 的平衡因子
    balance_factor = self.balance_factor(node)
    # 左偏树
    if balance_factor > 1:
        if self.balance_factor(node.left) >= 0:
            # 右旋
            return self.right_rotate(node)
        else:
            # 先左旋后右旋
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)
    # 右偏树
    elif balance_factor < -1:
        if self.balance_factor(node.right) <= 0:
            # 左旋
            return self.left_rotate(node)
        else:
            # 先右旋后左旋
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)
    # 平衡树，无须旋转，直接返回
    return node

注意双旋转分支中 node.left = self.left_rotate(node.left) 这样的写法：第一次旋转改变的是子树根，必须把返回值重新赋回父节点的对应指针，第二次旋转才能作用在正确的树上。C++ 版 rotate 与 Rust 版 rotate 中的判定分支与这张表完全一致，是“从源码结构看”验证旋转选择条件的最佳材料。

AVL 树常用操作

插入节点：递归插入 + 自底向上再平衡

AVL 树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于，在 AVL 树中插入节点后，从该节点到根节点的路径上可能会出现一系列失衡节点。因此，我们需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡：

def insert(self, val):
    """插入节点"""
    self._root = self.insert_helper(self._root, val)

def insert_helper(self, node: TreeNode | None, val: int) -> TreeNode:
    """递归插入节点（辅助方法）"""
    if node is None:
        return TreeNode(val)
    # 1. 查找插入位置并插入节点
    if val < node.val:
        node.left = self.insert_helper(node.left, val)
    elif val > node.val:
        node.right = self.insert_helper(node.right, val)
    else:
        # 重复节点不插入，直接返回
        return node
    # 更新节点高度
    self.update_height(node)
    # 2. 执行旋转操作，使该子树重新恢复平衡
    return self.rotate(node)

这里的递归结构值得留意：insert_helper 的返回值不是固定为 node，而是 self.rotate(node) 的结果——旋转可能更换子树的根节点，所以每一层都必须把返回值传回上一层的指针上。正是这种“递归展开做插入、递归回溯做再平衡”的结构，天然实现了自底向上的高度更新与旋转：只有当子树返回并更新完高度后，父节点才有机会检测到自己的失衡并旋转。另外注意，重复值直接返回、不插入，这也是二叉搜索树性质的常规处理。

删除节点：三种度数的处理 + 回溯再平衡

类似地，在二叉搜索树的删除节点方法的基础上，需要从底至顶执行旋转操作，使所有失衡节点恢复平衡：

def remove(self, val: int):
    """删除节点"""
    self._root = self.remove_helper(self._root, val)

def remove_helper(self, node: TreeNode | None, val: int) -> TreeNode | None:
    """递归删除节点（辅助方法）"""
    if node is None:
        return None
    # 1. 查找节点并删除
    if val < node.val:
        node.left = self.remove_helper(node.left, val)
    elif val > node.val:
        node.right = self.remove_helper(node.right, val)
    else:
        if node.left is None or node.right is None:
            child = node.left or node.right
            # 子节点数量 = 0 ，直接删除 node 并返回
            if child is None:
                return None
            # 子节点数量 = 1 ，直接删除 node
            else:
                node = child
        else:
            # 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            temp = node.right
            while temp.left is not None:
                temp = temp.left
            node.right = self.remove_helper(node.right, temp.val)
            node.val = temp.val
    # 更新节点高度
    self.update_height(node)
    # 2. 执行旋转操作，使该子树重新恢复平衡
    return self.rotate(node)

删除逻辑覆盖了二叉搜索树删除的三种情形：度数 0 直接返回 None；度数 1 用 node = child 让子节点顶替；度数 2 则找到右子树中最小节点（中序后继 temp），递归删除它并把 temp.val 填入当前节点。与插入一样，每层递归返回前都执行 update_height 与 rotate，保证删除引发的连锁失衡沿路径逐级修复。仓库主程序专门用三次删除分别验证了度 0、度 1、度 2 的情况，见 avl_tree.py 的 Driver Code：

test_remove(avl_tree, 8)  # 删除度为 0 的节点
test_remove(avl_tree, 5)  # 删除度为 1 的节点
test_remove(avl_tree, 4)  # 删除度为 2 的节点

查找节点

AVL 树的节点查找操作与二叉搜索树一致：从根出发，按“小于走左、大于走右”循环下降，越过叶节点后跳出。由于 AVL 树高度恒为 $O(\log n)$ 量级，查找同样稳定在 $O(\log n)$。

运行示例：观察一次完整构建过程

各语言的实现都内置了可执行演示。以 Python 版为例，主程序依次插入 [1, 2, 3, 4, 5, 8, 7, 9, 10, 6]，再插入一个重复值 7，随后执行上述三次删除，每步都打印当前树形（见 avl_tree.py）。在仓库中查看该文件的运行方式：将 codes/python/chapter_tree/avl_tree.py 作为脚本直接运行即可（文件头通过 sys.path 引入了上级 modules 中的 TreeNode 与 print_tree），无需额外安装依赖。其他语言版本中，C++/C 版本可通过各章目录下的 CMakeLists.txt 构建，Java、C# 等语言版本与 Python 版一一对应，便于跨语言比对同一算法的指针操作细节。

AVL 树典型应用与选型参考

• 组织和存储大型数据，适用于高频查找、低频增删的场景。
• 用于构建数据库中的索引系统。
• 红黑树也是一种常见的平衡二叉搜索树。相较于 AVL 树，红黑树的平衡条件更宽松，插入与删除节点所需的旋转操作更少，节点增删操作的平均效率更高。

结合本文的实现可以看到两者的取舍本质：AVL 树通过“每个节点平衡因子 $\in [-1, 1]$”的严格约束换取更矮的树与更快的查找，代价是每次增删都要沿路径做高度更新与可能的旋转；而本仓库选择讲解 AVL 树，正是因为它把“失衡判定—旋转选择—递归回溯再平衡”这套平衡二叉搜索树的核心机制展现得最为直观，读懂它之后再接触红黑树等宽松约束的方案会顺畅许多。