**目标**：通过实现 AVL 树和伸展树 --- #### **核心任务** 1. **实现 AVL 树的关键方法** - **方法列表**： - `insert(T value)`：插入值并维护 AVL 树的平衡。 - `remove(T value)`：删除值并维护平衡。 - `contains(T value)`：检查值是否存在。 - `restructure(IPosition<T> x)`：三节点重构（通过旋转操作修复平衡）。 - **提示**： - 使用继承的辅助方法（如 `expandExternal`）。 - 通过 `AVLPosition` 的高度属性高效更新树的高度（避免 O(n) 复杂度）。 - 每次操作后需双向更新父子节点关系。 2. **实现伸展树（Splay Tree）的关键方法** - **方法列表**： - `splay(IPosition<T> p)`：将指定节点展开到根节点（支持 zig、zig-zig、zig-zag 操作）。 - `insert(T value)`：插入值并触发展开。 - `remove(T value)`：删除值并触发展开。 - `contains(T value)`：检查值是否存在并触发展开。 - **提示**： - 需处理不同展开场景（如根节点、深层节点、左右子树差异）。 3. **测试策略** - 编写测试类（如 `Test1.java`, `Test2.java`），覆盖以下场景： - **AVL 树**：所有旋转类型（左旋、右旋、双旋）及高度更新逻辑。 - **伸展树**：所有展开类型（zig、zig-zig、zig-zag）及不同位置的操作。

### AVL树的实现 #### 插入 (Insert) AVL 树是一种自平衡二叉搜索树，在插入新节点后可能需要重新调整以保持平衡。每次插入可能导致单旋转或双旋转来恢复平衡。 ```python class TreeNode: def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 def insert(root, key): if not root: return TreeNode(key) if key < root.key: root.left = insert(root.left, key) else: root.right = insert(root.right, key) root.height = 1 + max(get_height(root.left), get_height(root.right)) balance_factor = get_balance(root) # 左左情况 if balance_factor > 1 and key < root.left.key: return rotate_right(root) # 单右旋 [^1] # 右右情况 if balance_factor < -1 and key > root.right.key: return rotate_left(root) # 单左旋 [^1] # 左右情况 if balance_factor > 1 and key > root.left.key: root.left = rotate_left(root.left) # 先左旋再右旋 [^1] return rotate_right(root) # 右左情况 if balance_factor < -1 and key < root.right.key: root.right = rotate_right(root.right) # 先右旋再左旋 return rotate_left(root) return root 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)) # 更新高度 [^1] y.height = 1 + max(get_height(y.left), get_height(y.right)) # 更新高度 [^1] return y def rotate_right(z): y = z.left T3 = y.right y.right = z z.left = T3 z.height = 1 + max(get_height(z.left), get_height(z.right)) # 更新高度 [^1] y.height = 1 + max(get_height(y.left), get_height(y.right)) # 更新高度 return y def get_height(node): if not node: return 0 return node.height def get_balance(node): if not node: return 0 return get_height(node.left) - get_height(node.right) def contains(root, key): while root is not None: if key == root.key: return True elif key < root.key: root = root.left else: root = root.right return False # O(h) 时间复杂度 [^2] def remove(root, key): if not root: return root if key < root.key: root.left = remove(root.left, key) elif key > root.key: root.right = remove(root.right, key) else: if root.left is None or root.right is None: temp = root.left if root.left else root.right if temp is None: return None else: root = temp else: min_larger_node = find_min(root.right) root.key = min_larger_node.key root.right = remove(root.right, min_larger_node.key) if root is None: return root root.height = 1 + max(get_height(root.left), get_height(root.right)) balance_factor = get_balance(root) if balance_factor > 1 and get_balance(root.left) >= 0: return rotate_right(root) if balance_factor < -1 and get_balance(root.right) <= 0: return rotate_left(root) if balance_factor > 1 and get_balance(root.left) < 0: root.left = rotate_left(root.left) return rotate_right(root) if balance_factor < -1 and get_balance(root.right) > 0: root.right = rotate_right(root.right) return rotate_left(root) return root def find_min(node): current = node while current.left is not None: current = current.left return current ``` --- ### 伸展树的实现 #### Splay 方法 Splay 是一种将目标节点移动到根的操作，涉及多种旋转组合。 ```python def splay(root, key): if root is None or root.key == key: return root if key < root.key: if root.left is None: return root if key < root.left.key: # Zig-Zig Case root.left.left = splay(root.left.left, key) root = rotate_right(root) elif key > root.left.key: # Zig-Zag Case root.left.right = splay(root.left.right, key) if root.left.right: root.left = rotate_left(root.left) return rotate_right(root) if root.left else root else: if root.right is None: return root if key > root.right.key: # Zag-Zag Case root.right.right = splay(root.right.right, key) root = rotate_left(root) elif key < root.right.key: # Zag-Zig Case root.right.left = splay(root.right.left, key) if root.right.left: root.right = rotate_right(root.right) return rotate_left(root) if root.right else root ``` #### Insert 和 Remove 的扩展 在伸展树中，`insert` 和 `remove` 都依赖于 `splay` 操作： ```python def insert_splay_tree(root, key): new_root = splay(root, key) if new_root and new_root.key == key: return new_root # Key already exists new_node = TreeNode(key) if not new_root: return new_node if key < new_root.key: new_node.right = new_root new_node.left = new_root.left new_root.left = None else: new_node.left = new_root new_node.right = new_root.right new_root.right = None return new_node def remove_splay_tree(root, key): if not root: return root root = splay(root, key) if root.key != key: return root left_subtree = root.left right_subtree = root.right del root if not right_subtree: return left_subtree minimal_in_right = splay(right_subtree, key - 1) minimal_in_right.left = left_subtree return minimal_in_right ``` --- ### 测试策略 为了全面验证上述方法的功能性和正确性，可以设计以下测试场景： 1. **基本功能测试**: 对每种操作分别进行单元测试，确保其行为符合预期。 2. **边界条件测试**: 如空树、重复键值、极端大小数据集等。 3. **性能测试**: 使用大量随机输入模拟真实环境下的表现，观察时间复杂度是否接近理论预测 \(O(\log n)\)[^1] 或摊销 \(O(\log n)\)[^2]。 4. **旋转覆盖测试**: 构造特定序列触发所有四种旋转类型（LL、RR、LR、RL），并确认最终状态满足平衡性质。 5. **一致性测试**: 执行多次连续操作后检查整棵树仍然维持 BST 属性及其对应子类额外约束（如 AVL 平衡因子限制或 ST 合法形态）。 --- 相关问题