AVL树（Adelson-Velsky and Landis Tree）是一种自平衡的二叉搜索树。它确保任何节点的两个子树的高度之差最多为1，因此保证了查找、插入和删除操作的时间复杂度都是 O(log n)。实现 AVL 树的核心方法主要包括插入、删除以及旋转操作（单旋转和双旋转）。
以下是一个简单的 AVL 树实现的核心方法：
节点类
首先，我们需要定义一个节点类：
```java class AVLNode<T> { T key; int height; AVLNode<T> left, right; public AVLNode(T key) { this.key = key; this.height = 1; // 新节点的初始高度为1 } } ```
AVL 树类
接下来是 AVL 树类：
```java public class AVLTree<T extends Comparable<T>> { private AVLNode<T> root; // 获取节点的高度 private int height(AVLNode<T> node) { return node == null ? 0 : node.height; } // 获取节点的平衡因子 private int getBalance(AVLNode<T> node) { if (node == null) return 0; return height(node.left) - height(node.right); } // 右旋 private AVLNode<T> rightRotate(AVLNode<T> y) { AVLNode<T> x = y.left; AVLNode<T> T2 = x.right; // 旋转操作 x.right = y; y.left = T2; // 更新高度 y.height = Math.max(height(y.left), height(y.right)) + 1; x.height = Math.max(height(x.left), height(x.right)) + 1; return x; // 返回新的根节点 } // 左旋 private AVLNode<T> leftRotate(AVLNode<T> x) { AVLNode<T> y = x.right; AVLNode<T> T2 = y.left; // 旋转操作 y.left = x; x.right = T2; // 更新高度 x.height = Math.max(height(x.left), height(x.right)) + 1; y.height = Math.max(height(y.left), height(y.right)) + 1; return y; // 返回新的根节点 } // 插入节点 public void insert(T key) { root = insert(root, key); } private AVLNode<T> insert(AVLNode<T> node, T key) { // 1. 普通的BST插入 if (node == null) return new AVLNode<>(key); if (key.compareTo(node.key) < 0) node.left = insert(node.left, key); else if (key.compareTo(node.key) > 0) node.right = insert(node.right, key); else // 不能插入重复的键 return node; // 2. 更新节点的高度 node.height = 1 + Math.max(height(node.left), height(node.right)); // 3. 获取节点的平衡因子，检查是否平衡 int balance = getBalance(node); // 如果节点失衡，则有4种情况 // 左左情况 if (balance > 1 && key.compareTo(node.left.key) < 0) return rightRotate(node); // 右右情况 if (balance < -1 && key.compareTo(node.right.key) > 0) return leftRotate(node); // 左右情况 if (balance > 1 && key.compareTo(node.left.key) > 0) { node.left = leftRotate(node.left); return rightRotate(node); } // 右左情况 if (balance < -1 && key.compareTo(node.right.key) < 0) { node.right = rightRotate(node.right); return leftRotate(node); } // 4. 返回节点指针 return node; } // 删除节点 public void delete(T key) { root = delete(root, key); } private AVLNode<T> delete(AVLNode<T> root, T key) { // 1. 普通的BST删除 if (root == null) return root; if (key.compareTo(root.key) < 0) root.left = delete(root.left, key); else if (key.compareTo(root.key) > 0) root.right = delete(root.right, key); else { // 节点只有一个子节点或没有子节点 if ((root.left == null) || (root.right == null)) { AVLNode<T> temp = root.left != null ? root.left : root.right; // 没有子节点的情况 if (temp == null) { temp = root; root = null; } else // 有一个子节点的情况 root = temp; temp = null; } else { // 有两个子节点的情况，找到中序后继 AVLNode<T> temp = minValueNode(root.right); root.key = temp.key; root.right = delete(root.right, temp.key); } } // 如果树中只有一个节点，则返回 if (root == null) return root; // 2. 更新节点的高度 root.height = Math.max(height(root.left), height(root.right)) + 1; // 3. 获取节点的平衡因子，检查是否平衡 int balance = getBalance(root); // 左左情况 if (balance > 1 && getBalance(root.left) >= 0) return rightRotate(root); // 左右情况 if (balance > 1 && getBalance(root.left) < 0) { root.left = leftRotate(root.left); return rightRotate(root); } // 右右情况 if (balance < -1 && getBalance(root.right) <= 0) return leftRotate(root); // 右左情况 if (balance < -1 && getBalance(root.right) > 0) { root.right = rightRotate(root.right); return leftRotate(root); } return root; } // 查找最小值节点 private AVLNode<T> minValueNode(AVLNode<T> node) { AVLNode<T> current = node; while (current.left != null) current = current.left; return current; } // 前序遍历 public void preOrder() { preOrder(root); } private void preOrder(AVLNode<T> node) { if (node != null) { System.out.print(node.key + " "); preOrder(node.left); preOrder(node.right); } } public static void main(String[] args) { AVLTree<Integer> tree = new AVLTree<>(); // 插入节点 tree.insert(10); tree.insert(20); tree.insert(30); tree.insert(40); tree.insert(50); tree.insert(25); // 前序遍历 System.out.println("前序遍历AVL树:"); tree.preOrder(); } } ```
代码解释
- **AVLNode 类**: 定义了树的节点，包括键值、左子节点、右子节点和高度。
- **AVLTree 类**:
- `height` 方法：获取节点的高度。
- `getBalance` 方法：计算节点的平衡因子。
- `rightRotate` 和 `leftRotate` 方法：执行右旋和左旋操作，确保树平衡。
- `insert` 方法：插入节点并保持平衡。
- `delete` 方法：删除节点并保持平衡。
- `minValueNode` 方法：查找最小值节点，用于节点删除时。
- `preOrder` 方法：前序遍历，用于测试和验证。
以上代码展示了如何实现 AVL 树的插入和删除操作，以及如何通过旋转保持树的平衡。在实际应用中，根据需要可以扩展和优化这些基本操作。
