引言
AVL树是由苏联数学家Adelson-Velsky和Landis于1962年发明的自平衡二叉搜索树。它通过维护每个节点的平衡因子（左子树高度减右子树高度），确保任意节点的平衡因子绝对值不超过1，从而将查找、插入、删除操作的时间复杂度严格控制在O(log n)。本文将用Java从零实现完整的AVL树，深入讲解四种旋转操作（LL、RR、LR、RL）的触发条件与执行过程。
平衡因子与失衡判定
AVL树的核心不变量是：每个节点的平衡因子 ∈ {-1, 0, 1}。
- 平衡因子 = 左子树高度 – 右子树高度
- 若平衡因子 > 1：左子树过高，需要右旋或左右双旋
- 若平衡因子 < -1：右子树过高，需要左旋或右左双旋
核心数据结构
public class AVLTree<T extends Comparable<T>> {
static class Node<T> {
T key;
Node<T> left, right;
int height;
Node(T key) {
this.key = key;
this.height = 1; // 新节点高度为1（叶子节点）
}
}
private Node<T> root;
private int size;
// 获取节点高度（空节点高度为0）
private int height(Node<T> node) {
return node == null ? 0 : node.height;
}
// 获取平衡因子
private int balanceFactor(Node<T> node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
// 更新节点高度
private void updateHeight(Node<T> node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
// 获取树的大小
public int size() { return size; }
// 判断是否为空
public boolean isEmpty() { return size == 0; }
}
四种旋转操作
1. 左旋（Left Rotation）—— RR型失衡
当节点A的右子树过高（balanceFactor < -1），且其右孩子B的平衡因子 ≤ 0 时，执行左旋：
A B
\ / \
B => A C
\
C
private Node<T> rotateLeft(Node<T> a) {
Node<T> b = a.right;
Node<T> bl = b.left; // B的左子树将成为A的右子树
// 执行旋转
b.left = a;
a.right = bl;
// 先更新A的高度，再更新B的高度（因为A是B的子节点）
updateHeight(a);
updateHeight(b);
return b; // 新的根节点
}
2. 右旋（Right Rotation）—— LL型失衡
当节点A的左子树过高（balanceFactor > 1），且其左孩子B的平衡因子 ≥ 0 时，执行右旋：
A B
/ / \
B => C A
/
C
private Node<T> rotateRight(Node<T> a) {
Node<T> b = a.left;
Node<T> br = b.right; // B的右子树将成为A的左子树
// 执行旋转
b.right = a;
a.left = br;
updateHeight(a);
updateHeight(b);
return b;
}
3. 左右双旋（Left-Right Rotation）—— LR型失衡
当节点A的左子树过高（balanceFactor > 1），但其左孩子B的平衡因子 < 0 时（B的右子树更高），先对B左旋，再对A右旋：
A A C
/ / / \
B => C => B A
\ /
C B
private Node<T> rotateLeftRight(Node<T> a) {
a.left = rotateLeft(a.left);
return rotateRight(a);
}
4. 右左双旋（Right-Left Rotation）—— RL型失衡
当节点A的右子树过高（balanceFactor < -1），但其右孩子B的平衡因子 > 0 时（B的左子树更高），先对B右旋，再对A左旋：
A A C
\ \ / \
B => C => A B
/ \
C B
private Node<T> rotateRightLeft(Node<T> a) {
a.right = rotateRight(a.right);
return rotateLeft(a);
}
插入操作与自平衡
public void insert(T key) {
root = insert(root, key);
}
private Node<T> insert(Node<T> node, T key) {
// 1. 标准BST插入
if (node == null) {
size++;
return new Node<>(key);
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = insert(node.left, key);
} else if (cmp > 0) {
node.right = insert(node.right, key);
} else {
return node; // 重复键不插入
}
// 2. 更新高度
updateHeight(node);
// 3. 获取平衡因子并修复
int bf = balanceFactor(node);
// LL型：左左失衡
if (bf > 1 && key.compareTo(node.left.key) < 0) {
return rotateRight(node);
}
// RR型：右右失衡
if (bf < -1 && key.compareTo(node.right.key) > 0) {
return rotateLeft(node);
}
// LR型：左右失衡
if (bf > 1 && key.compareTo(node.left.key) > 0) {
return rotateLeftRight(node);
}
// RL型：右左失衡
if (bf < -1 && key.compareTo(node.right.key) < 0) {
return rotateRightLeft(node);
}
return node;
}
删除操作与自平衡
public void delete(T key) {
root = delete(root, key);
}
private Node<T> delete(Node<T> node, T key) {
if (node == null) return null;
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = delete(node.left, key);
} else if (cmp > 0) {
node.right = delete(node.right, key);
} else {
// 找到要删除的节点
size--;
if (node.left == null) return node.right;
if (node.right == null) return node.left;
// 有两棵子树：找后继节点（右子树最小值）
Node<T> successor = findMin(node.right);
node.key = successor.key;
node.right = delete(node.right, successor.key);
}
// 更新高度
updateHeight(node);
// 重新平衡
int bf = balanceFactor(node);
// LL
if (bf > 1 && balanceFactor(node.left) >= 0) {
return rotateRight(node);
}
// LR
if (bf > 1 && balanceFactor(node.left) < 0) {
return rotateLeftRight(node);
}
// RR
if (bf < -1 && balanceFactor(node.right) <= 0) {
return rotateLeft(node);
}
// RL
if (bf < -1 && balanceFactor(node.right) > 0) {
return rotateRightLeft(node);
}
return node;
}
private Node<T> findMin(Node<T> node) {
while (node.left != null) node = node.left;
return node;
}
查找与前序遍历
public boolean contains(T key) {
return search(root, key) != null;
}
private Node<T> search(Node<T> node, T key) {
while (node != null) {
int cmp = key.compareTo(node.key);
if (cmp == 0) return node;
node = cmp < 0 ? node.left : node.right;
}
return null;
}
// 中序遍历输出有序序列
public void inorder() {
inorder(root);
System.out.println();
}
private void inorder(Node<T> node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.key + " ");
inorder(node.right);
}
完整测试与验证
public static void main(String[] args) {
AVLTree<Integer> tree = new AVLTree<>();
int[] values = {30, 20, 10, 25, 27, 5, 15};
System.out.println("插入序列: " + java.util.Arrays.toString(values));
for (int v : values) {
tree.insert(v);
System.out.println("插入 " + v + " 后中序遍历:");
tree.inorder();
}
System.out.println("\n树大小: " + tree.size());
System.out.println("包含15? " + tree.contains(15));
System.out.println("包含100? " + tree.contains(100));
tree.delete(20);
System.out.println("\n删除20后中序遍历:");
tree.inorder();
System.out.println("树大小: " + tree.size());
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 查找 | O(log n) | O(1) |
| 插入 | O(log n) | O(log n) 递归栈 |
| 删除 | O(log n) | O(log n) 递归栈 |
AVL树的高度始终为 O(log n)，因为每次插入/删除后的旋转操作将树的高度限制在对数级别。
与红黑树的对比
| 特性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡严格度 | 更严格（高度差≤1） | 较宽松（黑高平衡） |
| 查找速度 | 更快（树更矮） | 稍慢 |
| 插入/删除旋转次数 | 最多2次 | 最多3次（含变色） |
| 适用场景 | 查询密集型 | 修改密集型 |
小结
本文从零实现了完整的AVL树，涵盖：
– 平衡因子计算与高度更新机制
– LL/RR/LR/RL四种旋转的触发条件与代码实现
– 插入与删除操作的自平衡修复流程
– 与红黑树的特性对比分析
AVL树作为最早发明的自平衡二叉搜索树，其严谨的数学性质和优雅的旋转修复机制，至今仍是数据结构教学中的经典范例。掌握AVL树的实现，是理解高级索引结构（如数据库B+树）的重要基础。
