10　平衡树

普通二叉搜索树的搜索、插入和删除复杂度取决于树高 h。

如果树比较均匀，h 接近 log n，操作就很快；如果数据按照有序顺序插入，二叉搜索树可能退化成链表，树高变成 n。

平衡树的目标，就是在插入和删除之后主动调整结构，避免树越来越高。

平衡树不是让每个节点左右子树完全一样高，而是把树高控制在对数级别附近。

本文重点实现 AVL 树，并介绍另一种常见的平衡树：红黑树。

1. 为什么需要平衡树？

普通二叉搜索树的形状取决于插入顺序：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

按照比较均匀的顺序插入：

        8
       / \
      3   12
     / \  / \
    1  5 10 15

按照升序插入：

1
 \
  2
   \
    3
     \
      4
       \
        5

两棵树都满足二叉搜索树的顺序规则，但性能完全不同：

因此，普通二叉搜索树只解决了“如何保持有序”，没有解决“如何保持矮”。

2. 什么叫平衡？

最常用的局部指标是平衡因子：

平衡因子 = 左子树高度 - 右子树高度

以 AVL 树为例，每个节点都必须满足：

平衡因子 ∈ {-1, 0, 1}

如果某个节点的平衡因子变成 2 或 -2，说明这一处失衡，需要旋转。

这里定义叶节点高度为 1，空树高度为 0。Python 节点可以保存自己的高度：

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1


def node_height(node):
    if node is None:
        return 0
    return node.height


def update_height(node):
    node.height = 1 + max(
        node_height(node.left),
        node_height(node.right),
    )


def balance_factor(node):
    if node is None:
        return 0

    return node_height(node.left) - node_height(node.right)

每次子树发生变化，都必须从下往上更新高度，否则后续的平衡判断会使用错误信息。

3. 旋转：重新组织节点关系

旋转不会改变中序遍历顺序，只会改变节点的层级关系。

3.1 右旋

右旋常用于解决左侧过重的情况：

旋转前：       y              旋转后：      x
              / \                         / \
             x   C                       A   y
            / \                             / \
           A   B                           B   C

Python 实现：

def rotate_right(y):
    x = y.left
    middle = x.right

    x.right = y
    y.left = middle

    update_height(y)
    update_height(x)

    return x

3.2 左旋

左旋是右旋的镜像，常用于解决右侧过重的情况：

旋转前：       x              旋转后：      y
              / \                         / \
             A   y                       x   C
                / \                     / \
               B   C                   A   B

def rotate_left(x):
    y = x.right
    middle = y.left

    y.left = x
    x.right = middle

    update_height(x)
    update_height(y)

    return y

旋转后必须按“先下层、后上层”的顺序更新高度。上面的代码先更新被下移的节点，再更新新的子树根。

4. AVL 树的四种失衡情况

插入一个节点后，失衡通常可以归纳为四类：

4.1 LL：右旋一次

插入顺序 30、20、10：

插入后：       30
              /
             20
            /
           10

右旋后：       20
              /  \
             10  30

4.2 RR：左旋一次

插入顺序 10、20、30：

插入后：       10
                \
                 20
                   \
                    30

左旋后：       20
              /  \
             10  30

4.3 LR：两次旋转

左子树的右侧过重时：

1. 先对左孩子左旋；
2. 再对当前节点右旋。

4.4 RL：两次旋转

右子树的左侧过重时：

1. 先对右孩子右旋；
2. 再对当前节点左旋。

两次旋转并不是额外的技巧，而是把“折线形”结构先转成“直线形”，再使用一次单旋转。

5. AVL 插入

AVL 插入和普通二叉搜索树插入的前半部分相同：

1. 按大小关系向左或向右递归；
2. 插入新节点；
3. 从递归返回时更新高度；
4. 检查平衡因子；
5. 必要时旋转。

def rebalance(root):
    if root is None:
        return None

    update_height(root)
    balance = balance_factor(root)

    # 左侧过重
    if balance > 1:
        if balance_factor(root.left) < 0:
            root.left = rotate_left(root.left)
        return rotate_right(root)

    # 右侧过重
    if balance < -1:
        if balance_factor(root.right) > 0:
            root.right = rotate_right(root.right)
        return rotate_left(root)

    return root


def avl_insert(root, value):
    if root is None:
        return AVLNode(value)

    if value < root.value:
        root.left = avl_insert(root.left, value)
    elif value > root.value:
        root.right = avl_insert(root.right, value)
    else:
        # 本实现忽略重复值
        return root

    return rebalance(root)

为了观察结果，写一个中序遍历和高度检查：

def inorder(root):
    result = []

    def visit(node):
        if node is None:
            return

        visit(node.left)
        result.append(node.value)
        visit(node.right)

    visit(root)
    return result


root = None
for value in [30, 20, 10, 25, 28, 27]:
    root = avl_insert(root, value)

print(inorder(root))  # [10, 20, 25, 27, 28, 30]
print(root.height)

无论插入顺序如何，AVL 树都会在返回路径上修复失衡。由于树高被控制在 O(log n)，插入复杂度也是 O(log n)。

6. AVL 删除

删除比插入更复杂，因为删除一个节点后，可能让从该节点到根的多层祖先同时变矮。

删除的基本步骤仍然分为两部分：

1. 按普通二叉搜索树规则删除；
2. 从删除位置向上更新高度并重新平衡。

def find_min(node):
    current = node

    while current.left is not None:
        current = current.left

    return current


def avl_delete(root, target):
    if root is None:
        return None

    if target < root.value:
        root.left = avl_delete(root.left, target)
    elif target > root.value:
        root.right = avl_delete(root.right, target)
    else:
        if root.left is None:
            return root.right

        if root.right is None:
            return root.left

        successor = find_min(root.right)
        root.value = successor.value
        root.right = avl_delete(root.right, successor.value)

    return rebalance(root)

测试删除：

root = None
for value in [30, 20, 10, 25, 28, 27, 40, 50]:
    root = avl_insert(root, value)

root = avl_delete(root, 25)
root = avl_delete(root, 40)

print(inorder(root))
print(root.height)

删除节点只有一个子树时，函数直接返回子树根节点。递归返回到上层后，上层节点还会继续执行 rebalance。

7. 检查 AVL 树是否真的平衡

实现数据结构时，最好写一个验证函数，帮助发现高度更新或旋转链接中的错误：

def validate_avl(root):
    def check(node):
        if node is None:
            return True, 0

        left_ok, left_height = check(node.left)
        right_ok, right_height = check(node.right)

        current_height = 1 + max(left_height, right_height)
        balanced = abs(left_height - right_height) <= 1
        height_correct = node.height == current_height

        return (
            left_ok and right_ok and balanced and height_correct,
            current_height,
        )

    return check(root)[0]


print(validate_avl(root))

验证函数同时检查两件事：

• 左右子树高度差是否不超过 1；
• 节点保存的 height 是否等于真实高度。

实际项目中，测试旋转边界比只测试随机数据更重要。

8. 红黑树的基本思想

红黑树也是一种自平衡二叉搜索树。它不要求每个节点的左右高度差都非常小，而是给节点增加颜色，并遵守一组规则：

1. 每个节点是红色或黑色；
2. 根节点通常是黑色；
3. 空叶子被视为黑色；
4. 红色节点不能有红色子节点；
5. 从任意节点到其后代空叶子的路径，经过的黑色节点数量相同。

这些规则共同限制了最长路径不会比最短路径长得过多，因此树高仍然是 O(log n)。

红黑树插入和删除通常通过：

• 重新着色；
• 左旋；
• 右旋；

来恢复规则。

红黑树的代码比 AVL 更复杂，但它的平衡条件更宽松。在频繁插入和删除的场景中，红黑树通常能减少一些旋转。

9. AVL 树和红黑树的比较

两者的渐进复杂度都是：

10. Python 中如何选择？

Python 内置的 dict 和 set 使用哈希表思想，适合根据键做精确查找，平均复杂度接近 O(1)。

Python 的 list 配合 bisect 可以在有序列表中进行二分搜索：

from bisect import bisect_left, insort

numbers = [1, 3, 5, 8]

position = bisect_left(numbers, 5)
print(position)  # 2

insort(numbers, 6)
print(numbers)  # [1, 3, 5, 6, 8]

不过 insort 插入时仍然需要移动列表元素，插入复杂度是 O(n)。如果需要大量有序插入、删除和范围查询，可以使用专门的有序容器或自己实现平衡树。

选择时可以这样考虑：

• 只需要精确查找：优先使用 dict 或 set；
• 数据静态、主要搜索：排序列表加二分搜索；
• 需要动态维护有序数据：AVL、红黑树或其他有序树；
• 数据量很大、存储在磁盘上：数据库常使用 B 树或 B+ 树；
• 需要教学和理解旋转：先实现 AVL 树最合适。

11. 为什么数据库常用 B 树？

AVL 和红黑树都是二叉树，每个节点最多有两个孩子。磁盘和数据库索引通常会使用多路平衡树，例如 B 树或 B+ 树：

• 一个节点可以保存多个关键字；
• 一个节点可以拥有多个子节点；
• 树的高度更低；
• 每次磁盘读取可以获得更多关键字；
• 所有叶节点保持在相近的层级。

这说明“平衡”不仅适用于二叉树，也适用于更一般的多路搜索树。

12. 常见错误

忘记更新高度

旋转后如果高度没有重新计算，下一次平衡判断就会出错。应先更新下移节点，再更新新的子树根。

旋转后没有返回新的根

旋转可能改变子树根，必须把返回值重新连接：

def rebalance_example(root):
    root.left = rotate_left(root.left)
    return rotate_right(root)

把平衡理解成左右节点数量完全相同

AVL 只要求每个节点左右子树高度差不超过 1，不要求节点数量完全相等。

只处理插入，不处理删除

删除会让祖先节点变矮，可能造成新的失衡。AVL 删除需要沿返回路径持续更新和检查。

混淆树高定义

有的教材把叶节点高度记为 0，有的实现把叶节点高度记为 1。只要在整套代码中保持一致，复杂度结论不会改变。

认为 Python 的 dict 是平衡树

dict 是哈希表，不提供按键大小排列的树结构。需要有序操作时，不能把字典当作平衡搜索树使用。

13. 小结

• 普通二叉搜索树可能退化成链表；
• 平衡树通过旋转、重新着色等方法控制树高；
• AVL 树要求每个节点的平衡因子只能是 -1、0 或 1；
• AVL 的插入和删除都需要在递归返回时更新高度并重新平衡；
• 红黑树用颜色规则换取较宽松的平衡条件；
• AVL 和红黑树的搜索、插入、删除都是 O(log n)；
• Python 的 dict 和 set 适合精确查找，但不是平衡树；
• 读多写少可以偏向 AVL，更新频繁可以考虑红黑树；
• 数据库索引通常使用 B 树或 B+ 树等多路平衡树。