Python算法——平衡二叉树（AVL）

Python中的平衡二叉搜索树（AVL树）算法详解

平衡二叉搜索树（AVL树）是一种自平衡的二叉搜索树，它通过在插入或删除节点时进行旋转操作来保持树的平衡性。在AVL树中，任何节点的两个子树的高度差（平衡因子）最多为1。这种平衡性质确保了AVL树的高度始终是对数级别，使得查找、插入和删除等操作的时间复杂度保持在O(log n)。在本文中，我们将深入讨论AVL树的原理，并提供Python代码实现。

AVL树的节点定义

首先，我们定义AVL树的节点类：

class AVLNode:def __init__(self, key):self.key = keyself.height = 1self.left = Noneself.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 rootif 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.rightelif 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 0return node.heightdef get_balance(node):if node is None:return 0return get_height(node.left) - get_height(node.right)def rotate_left(z):y = z.rightT2 = y.left# 执行左旋y.left = zz.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 ydef rotate_right(y):x = y.leftT2 = x.right# 执行右旋x.right = yy.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树解决实际问题。