数据结构与算法 / 系统课时

平衡树的基本思想

平衡树的基本思想

普通二叉搜索树可能因插入顺序不理想而退化成链表。平衡树通过检测局部高度差并执行旋转,把树高控制在对数级附近,从而稳定查找、插入和删除性能。

学习目标

  • 理解树高、平衡因子与操作性能之间的关系
  • 能解释左旋和右旋为何不会破坏搜索树顺序
  • 能运行一次右旋示例并验证旋转前后的结构

为什么需要平衡

搜索树操作的复杂度是 O(h)O(h)。当节点分布较均匀时,树高接近 log⁡n\log n;若依次插入有序数据,树会向一侧倾斜,树高可能增长到 nn,查找也随之退化为线性时间。

AVL 树要求每个节点左右子树高度差的绝对值不超过 1。红黑树采用颜色和路径规则维持较弱平衡。两者规则不同,但目标一致:避免树长期过高。

旋转保持什么

旋转只调整少量节点之间的父子关系,不改变节点的中序顺序。以右旋为例,失衡节点的左子节点上移,原失衡节点下移到其右侧,中间子树重新连接到合适位置。

平衡树右旋前后结构

完整可运行示例

下面演示一次 LL 型失衡的右旋。示例使用递归计算高度,便于理解;完整 AVL 实现通常会在每个节点中缓存高度,使更新和旋转保持常数级局部开销。

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

def height(node):
    if node is None:
        return 0
    return max(height(node.left), height(node.right)) + 1

def balance_factor(node):
    return height(node.left) - height(node.right)

def right_rotate(root):
    # root.left 将成为旋转后的新根
    new_root = root.left
    middle_subtree = new_root.right

    new_root.right = root
    root.left = middle_subtree
    return new_root

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def is_balanced(node):
    if node is None:
        return True
    return (
        abs(balance_factor(node)) <= 1
        and is_balanced(node.left)
        and is_balanced(node.right)
    )

root = Node(30, Node(20, Node(10)))
print("旋转前根节点:", root.value)
print("旋转前平衡因子:", balance_factor(root))
print("旋转前中序:", inorder(root))

root = right_rotate(root)
print("旋转后根节点:", root.value)
print("旋转后中序:", inorder(root))
print("旋转后是否平衡:", is_balanced(root))

预期输出:

text
旋转前根节点: 30
旋转前平衡因子: 2
旋转前中序: [10, 20, 30]
旋转后根节点: 20
旋转后中序: [10, 20, 30]
旋转后是否平衡: True

性能与实现边界

单次旋转只修改固定数量的引用,时间复杂度为 O(1)O(1)。但若像示例一样反复递归计算高度,完整插入过程可能产生额外开销。工程实现通常缓存节点高度,并在插入或删除回溯时更新,使 AVL 操作保持 O(log⁡n)O(\log n)。

平衡不表示左右节点数完全相等,也不能只检查根节点。每棵子树都必须满足对应规则。实际项目中应优先使用语言标准库或成熟容器,而不是自行实现复杂平衡逻辑。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

平衡树的基本思想

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通