上一篇
什么是平衡二叉树？
平衡二叉树（AVL树）是一种自平衡的二叉搜索树，由Adelson-Velskii和Landis在1962年发明。在AVL树中，任何节点的两个子树的高度最多相差1，这使得树能够保持平衡状态，确保查找、插入和删除操作的时间复杂度稳定在O(log n)。
为什么需要平衡二叉树？
普通二叉搜索树在极端情况下（如按顺序插入数据）会退化成链表，导致操作时间复杂度变为O(n)。AVL树通过旋转操作自动调整树的结构，始终保持平衡，解决了这个问题。
AVL树的核心概念
1. 平衡因子
平衡因子 = 左子树高度 - 右子树高度。在AVL树中，每个节点的平衡因子只能是-1、0或1。
2. 旋转操作
当插入或删除节点导致平衡因子超出允许范围时，AVL树通过旋转操作恢复平衡：
左旋
当右子树过高时使用
→
右旋
当左子树过高时使用
←
左右旋
先左旋再右旋
↷
右左旋
先右旋再左旋
↶
AVL树的Python实现
节点类定义
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
AVL树类实现
class AVLTree:
def __init__(self):
self.root = None
def height(self, node):
if not node:
return 0
return node.height
def balance_factor(self, node):
if not node:
return 0
return self.height(node.left) - self.height(node.right)
def update_height(self, node):
if node:
node.height = 1 + max(self.height(node.left), self.height(node.right))
# 右旋操作
def right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
self.update_height(z)
self.update_height(y)
return y
# 左旋操作
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
self.update_height(z)
self.update_height(y)
return y
# 插入节点
def insert(self, root, key):
# 1. 标准BST插入
if not root:
return AVLNode(key)
elif key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
# 2. 更新高度
self.update_height(root)
# 3. 获取平衡因子
balance = self.balance_factor(root)
# 4. 平衡树（4种情况）
# 左左情况 - 右旋
if balance > 1 and key < root.left.key:
return self.right_rotate(root)
# 右右情况 - 左旋
if balance < -1 and key > root.right.key:
return self.left_rotate(root)
# 左右情况 - 先左旋后右旋
if balance > 1 and key > root.left.key:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# 右左情况 - 先右旋后左旋
if balance < -1 and key < root.right.key:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
# 中序遍历
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.key, end=" ")
self.inorder(root.right)
重要提示：
在实现AVL树时，需要特别注意在每次插入或删除节点后更新节点高度并检查平衡因子。旋转操作后也要及时更新相关节点的高度。
使用示例
# 创建AVL树并插入数据
avl = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
root = avl.insert(root, key)
# 中序遍历
print("中序遍历结果:")
avl.inorder(root) # 输出: 10 20 25 30 40 50
AVL树与其他数据结构的比较
| 数据结构 | 插入/删除时间复杂度 | 查找时间复杂度 | 是否自平衡 |
|---|---|---|---|
| 普通二叉搜索树 | O(n) (最坏情况) | O(n) (最坏情况) | 否 |
| AVL树 | O(log n) | O(log n) | 是 |
| 红黑树 | O(log n) | O(log n) | 是 |
| 哈希表 | O(1) | O(1) | 不适用 |
平衡二叉树的应用场景
1. 数据库索引
许多数据库系统使用AVL树或类似的自平衡树来实现索引结构，确保高效的数据检索。
2. 内存中的有序数据结构
当需要维护一个动态变化的有序数据集时，AVL树能提供高效的插入、删除和查找操作。
3. 文件系统
某些文件系统使用平衡树来管理目录结构，以支持快速的文件查找操作。
发表评论