数据结构与算法 / 系统课时
平衡树的基本思想
平衡树的基本思想
普通二叉搜索树可能因插入顺序不理想而退化成链表。平衡树通过检测局部高度差并执行旋转,把树高控制在对数级附近,从而稳定查找、插入和删除性能。
学习目标
- 理解树高、平衡因子与操作性能之间的关系
- 能解释左旋和右旋为何不会破坏搜索树顺序
- 能运行一次右旋示例并验证旋转前后的结构
为什么需要平衡
搜索树操作的复杂度是 。当节点分布较均匀时,树高接近 ;若依次插入有序数据,树会向一侧倾斜,树高可能增长到 ,查找也随之退化为线性时间。
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性能与实现边界
单次旋转只修改固定数量的引用,时间复杂度为 。但若像示例一样反复递归计算高度,完整插入过程可能产生额外开销。工程实现通常缓存节点高度,并在插入或删除回溯时更新,使 AVL 操作保持 。
平衡不表示左右节点数完全相等,也不能只检查根节点。每棵子树都必须满足对应规则。实际项目中应优先使用语言标准库或成熟容器,而不是自行实现复杂平衡逻辑。
按自己的节奏,确认真正理解。