### Python中实现AVL树（平衡二叉查找树） AVL树是一种自平衡的二叉查找树，其每个节点的左右子树的高度差最多为1。这种特性使得AVL树在插入、删除和查找操作中的时间复杂度均为O(log n)[^1]。 #### AVL树的关键概念 - **平衡因子**：节点的平衡因子定义为其左子树高度减去右子树高度。在AVL树中，所有节点的平衡因子必须位于{-1, 0, 1}范围内。 - **旋转操作**：当插入或删除节点导致树失去平衡时，需要通过旋转操作恢复平衡。旋转包括单旋转（左旋或右旋）和双旋转（先左后右或先右后左）[^1]。 #### AVL树的Python实现 以下是一个基本的AVL树实现，涵盖了节点插入和树的自平衡逻辑： ```python class TreeNode: def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 # 初始化高度为1 class AVLTree: def insert(self, root, key): """ 插入新节点并更新平衡 """ if not root: return TreeNode(key) elif key < root.key: root.left = self.insert(root.left, key) else: root.right = self.insert(root.right, key) root.height = 1 + max(self.get_height(root.left), self.get_height(root.right)) balance = self.get_balance(root) # 左左情况 - 右旋 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 left_rotate(self, z): """ 左旋操作 """ y = z.right T2 = y.left y.left = z z.right = T2 z.height = 1 + max(self.get_height(z.left), self.get_height(z.right)) y.height = 1 + max(self.get_height(y.left), self.get_height(y.right)) return y def right_rotate(self, z): """ 右旋操作 """ y = z.left T3 = y.right y.right = z z.left = T3 z.height = 1 + max(self.get_height(z.left), self.get_height(z.right)) y.height = 1 + max(self.get_height(y.left), self.get_height(y.right)) return y def get_height(self, root): """ 获取节点高度 """ if not root: return 0 return root.height def get_balance(self, root): """ 计算平衡因子 """ if not root: return 0 return self.get_height(root.left) - self.get_height(root.right) def pre_order(self, root): """ 前序遍历 """ if not root: return print(f"{root.key}", end=" ") self.pre_order(root.left) self.pre_order(root.right) ``` #### 示例用法 ```python avl_tree = AVLTree() root = None # 插入节点 keys = [10, 20, 30, 40, 50, 25] for key in keys: root = avl_tree.insert(root, key) # 打印前序遍历结果 print("Preorder traversal of the constructed AVL tree is:") avl_tree.pre_order(root) ``` 输出结果将展示一个平衡的AVL树结构。 #### 平衡调整的详细说明 在插入或删除节点后，可能需要进行以下四种旋转之一来恢复树的平衡： 1. **右旋**：适用于左子树过重的情况。 2. **左旋**：适用于右子树过重的情况。 3. **先左旋后右旋**：适用于左子树的右子树过重的情况。 4. **先右旋后左旋**：适用于右子树的左子树过重的情况。 这些旋转操作确保了树的高度始终保持在O(log n)范围内。