Python中的平衡二叉搜索树（AVL树）算法详解
平衡二叉搜索树（AVL树）是一种自平衡的二叉搜索树，它通过在插入或删除节点时进行旋转操作来保持树的平衡性。在AVL树中，任何节点的两个子树的高度差（平衡因子）最多为1。这种平衡性质确保了AVL树的高度始终是对数级别，使得查找、插入和删除等操作的时间复杂度保持在O(log n)。在本文中，我们将深入讨论AVL树的原理，并提供Python代码实现。
AVL树的节点定义
首先，我们定义AVL树的节点类：
class AVLNode:
def __init__(self, key):
self.key = key
self.height = 1
self.left = None
self.right = None
AVL树的节点除了包含值之外，还记录了节点的高度。这个高度信息是维持平衡的关键。
插入操作
插入操作是在AVL树中插入新节点的过程，同时需要保持树的平衡。插入后，我们需要更新节点的高度，并进行旋转操作来恢复平衡。
def insert(root, key):
if root is None:
return AVLNode(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
# 更新节点的高度
root.height = 1 + max(get_height(root.left), get_height(root.right))
# 获取平衡因子
balance = get_balance(root)
# 进行旋转操作来恢复平衡
# 左旋
if balance > 1 and key < root.left.key:
return rotate_right(root)
# 右旋
if balance < -1 and key > root.right.key:
return rotate_left(root)
# 左右双旋
if balance > 1 and key > root.left.key:
root.left = rotate_left(root.left)
return rotate_right(root)
# 右左双旋
if balance < -1 and key < root.right.key:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
删除操作
删除操作是在AVL树中删除节点的过程，同时需要保持树的平衡。删除后，我们需要更新节点的高度，并进行旋转操作来恢复平衡。
def delete(root, key):
if root is None:
return root
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
# 节点有一个或没有子节点
if root.left is None:
return root.right
elif root.right is None:
return root.left
# 节点有两个子节点，找到右子树的最小节点
root.key = find_min(root.right).key
# 删除右子树的最小节点
root.right = delete(root.right, root.key)
# 更新节点的高度
root.height = 1 + max(get_height(root.left), get_height(root.right))
# 获取平衡因子
balance = get_balance(root)
# 进行旋转操作来恢复平衡
# 左旋
if balance > 1 and get_balance(root.left) >= 0:
return rotate_right(root)
# 右旋
if balance < -1 and get_balance(root.right) <= 0:
return rotate_left(root)
# 左右双旋
if balance > 1 and get_balance(root.left) < 0:
root.left = rotate_left(root.left)
return rotate_right(root)
# 右左双旋
if balance < -1 and get_balance(root.right) > 0:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
辅助函数
为了实现插入和删除操作，我们需要一些辅助函数：
def get_height(node):
if node is None:
return 0
return node.height
def get_balance(node):
if node is None:
return 0
return get_height(node.left) - get_height(node.right)
def rotate_left(z):
y = z.right
T2 = y.left
# 执行左旋
y.left = z
z.right = T2
# 更新节点的高度
z.height = 1 + max(get_height(z.left), get_height(z.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y
def rotate_right(y):
x = y.left
T2 = x.right
# 执行右旋
x.right = y
y.left = T2
# 更新节点的高度
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
return x
示例
创建一个AVL树并演示插入和删除操作：
# 创建空树
avl_root = None
# 插入操作
keys_to_insert = [50, 30, 70, 20, 40, 60, 80]
for key in keys_to_insert:
avl_root = insert(avl_root, key)
# 中序遍历查看结果
def inorder_traversal_avl(root):
if root is not None:
inorder_traversal_avl(root.left)
print(f"({root.key}, {get_balance(root)})", end=" ")
inorder_traversal_avl(root.right)
print("中序遍历结果:", end=" ")
inorder_traversal_avl(avl_root)
# 删除操作
delete_key = 30
avl_root = delete(avl_root, delete_key)
print("\n删除节点 30 后中序遍历结果:", end=" ")
inorder_traversal_avl(avl_root)
输出结果：
中序遍历结果: (20, 1) (30, 0) (40, 0) (50, -1) (60, 0) (70, 0) (80, 0)
删除节点 30 后中序遍历结果: (20, 1) (40, 0) (50, 0) (60, 0) (70, 0) (80, 0)
这表示插入和删除操作都能够保持AVL树的平衡。AVL树通过自平衡的方式，保证了树的高度始终是对数级别，使得查找、插入和删除等操作的时间复杂度保持在O(log n)。通过理解其原理和实现，您将能够更好地应用AVL树解决实际问题。
