AVL树是由苏联数学家Georgy Adelson-Velsky和Evgenii Landis于1962年发明的自平衡二叉搜索树。它在插入和删除操作后通过旋转保持树的平衡，确保任意节点的左右子树高度差不超过1，从而将查找、插入和删除的时间复杂度严格控制在O(log n)。与红黑树相比，AVL树的查询效率更高，适合读多写少的场景。
一、AVL树的核心概念
1.1 平衡因子
AVL树中每个节点维护一个平衡因子（Balance Factor），定义为左子树高度减去右子树高度：
平衡因子 = height(左子树) - height(右子树)
AVL树的平衡条件要求所有节点的平衡因子只能是 -1、0 或 1。当平衡因子的绝对值超过1时，树失去平衡，需要通过旋转操作恢复。
1.2 节点高度
节点的高度定义为从该节点到最远叶子节点的路径上的边数。叶子节点的高度为0，空节点的高度为-1。通过维护高度信息，AVL树可以在O(1)时间内判断是否需要旋转。
二、四种旋转操作
当插入或删除导致失衡时，根据失衡节点与其子节点的位置关系，共有四种旋转方式：
2.1 左旋（RR型失衡）
当失衡节点的右子树的右子树过高时发生。以失衡节点为支点，向左旋转，让右子节点成为新的根节点。
T R
/ \ / \
L R => T RR
/ \ / \
RL RR L RL
2.2 右旋（LL型失衡）
当失衡节点的左子树的左子树过高时发生。以失衡节点为支点，向右旋转，让左子节点成为新的根节点。
T L
/ \ / \
L R => LL T
/ \ / \
LL LR LR R
2.3 先左旋后右旋（LR型失衡）
当失衡节点的左子树的右子树过高时发生。先对左子节点左旋，再对失衡节点右旋。
T T LR
/ \ / \ / \
L R => LR R => L T
/ \ / \ / \ / \
LL LR L LRR LL LRL LRR R
/ \ / \
LRL LRR LL LRL
2.4 先右旋后左旋（RL型失衡）
当失衡节点的右子树的左子树过高时发生。先对右子节点右旋，再对失衡节点左旋。
三、完整Java实现
以下是一个完整的、可直接运行的AVL树Java实现，包含插入、删除、查找和四种旋转操作。
import java.util.ArrayList;
import java.util.List;
/**
* AVL树实现
* 自平衡二叉搜索树，保证任意节点左右子树高度差不超过1
*/
public class AVLTree<T extends Comparable<T>> {
/**
* 树节点定义
*/
private static class Node<T> {
T data; // 节点数据
Node<T> left; // 左子节点
Node<T> right; // 右子节点
int height; // 节点高度
int size; // 以该节点为根的子树节点数
Node(T data) {
this.data = data;
this.height = 0; // 新节点是叶子，高度为0
this.size = 1;
}
}
private Node<T> root; // 根节点
private int count; // 节点总数
public AVLTree() {
this.root = null;
this.count = 0;
}
// ==================== 基础工具方法 ====================
/**
* 获取节点高度，空节点返回-1
*/
private int height(Node<T> node) {
return node == null ? -1 : node.height;
}
/**
* 获取节点子树大小，空节点返回0
*/
private int size(Node<T> node) {
return node == null ? 0 : node.size;
}
/**
* 计算平衡因子
*/
private int balanceFactor(Node<T> node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
/**
* 更新节点高度和大小
*/
private void updateNode(Node<T> node) {
if (node != null) {
node.height = 1 + Math.max(height(node.left), height(node.right));
node.size = 1 + size(node.left) + size(node.right);
}
}
// ==================== 旋转操作 ====================
/**
* 右旋操作（LL型失衡）
* 将失衡节点向左下旋转，左子节点上升为新根
*/
private Node<T> rotateRight(Node<T> y) {
Node<T> x = y.left;
Node<T> t2 = x.right;
// 执行旋转
x.right = y;
y.left = t2;
// 先更新y的高度，再更新x的高度（因为x是y的父节点）
updateNode(y);
updateNode(x);
return x; // 新的子树根节点
}
/**
* 左旋操作（RR型失衡）
* 将失衡节点向右下旋转，右子节点上升为新根
*/
private Node<T> rotateLeft(Node<T> x) {
Node<T> y = x.right;
Node<T> t2 = y.left;
// 执行旋转
y.left = x;
x.right = t2;
// 先更新x的高度，再更新y的高度
updateNode(x);
updateNode(y);
return y; // 新的子树根节点
}
/**
* 重新平衡节点
* 根据平衡因子判断失衡类型并执行相应旋转
*/
private Node<T> rebalance(Node<T> node) {
updateNode(node);
int bf = balanceFactor(node);
// 左子树过高（LL或LR）
if (bf > 1) {
if (balanceFactor(node.left) < 0) {
// LR型：先对左子节点左旋，变为LL型
node.left = rotateLeft(node.left);
}
// LL型：右旋
return rotateRight(node);
}
// 右子树过高（RR或RL）
if (bf < -1) {
if (balanceFactor(node.right) > 0) {
// RL型：先对右子节点右旋，变为RR型
node.right = rotateRight(node.right);
}
// RR型：左旋
return rotateLeft(node);
}
return node; // 无需旋转，已平衡
}
// ==================== 插入操作 ====================
/**
* 向AVL树中插入元素
* 插入后沿路径向上重新平衡
*/
public void insert(T data) {
if (data == null) {
throw new IllegalArgumentException("不能插入null值");
}
root = insert(root, data);
count++;
}
private Node<T> insert(Node<T> node, T data) {
// 标准BST插入
if (node == null) {
return new Node<>(data);
}
int cmp = data.compareTo(node.data);
if (cmp < 0) {
node.left = insert(node.left, data);
} else if (cmp > 0) {
node.right = insert(node.right, data);
} else {
// 重复元素：这里选择不插入（可根据需求改为计数或覆盖）
count--; // 补偿外部count++
return node;
}
// 插入后重新平衡
return rebalance(node);
}
// ==================== 删除操作 ====================
/**
* 从AVL树中删除元素
* 删除后沿路径向上重新平衡
*/
public boolean delete(T data) {
if (data == null || root == null) {
return false;
}
int oldCount = count;
root = delete(root, data);
return count < oldCount;
}
private Node<T> delete(Node<T> node, T data) {
if (node == null) {
return null;
}
int cmp = data.compareTo(node.data);
if (cmp < 0) {
node.left = delete(node.left, data);
} else if (cmp > 0) {
node.right = delete(node.right, data);
} else {
// 找到要删除的节点
count--;
// 叶子节点或只有一个子节点
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
}
// 有两个子节点：找到后继（右子树最小值）
Node<T> successor = findMin(node.right);
node.data = successor.data;
node.right = delete(node.right, successor.data);
count++; // delete successor时会减1，这里补偿
}
// 删除后重新平衡
return rebalance(node);
}
/**
* 查找子树中的最小节点
*/
private Node<T> findMin(Node<T> node) {
while (node.left != null) {
node = node.left;
}
return node;
}
// ==================== 查找操作 ====================
/**
* 查找元素是否存在
*/
public boolean contains(T data) {
return find(root, data) != null;
}
private Node<T> find(Node<T> node, T data) {
while (node != null) {
int cmp = data.compareTo(node.data);
if (cmp == 0) {
return node;
} else if (cmp < 0) {
node = node.left;
} else {
node = node.right;
}
}
return null;
}
// ==================== 其他查询方法 ====================
/**
* 获取树的高度
*/
public int height() {
return height(root);
}
/**
* 获取节点总数
*/
public int size() {
return count;
}
/**
* 中序遍历（升序输出）
*/
public List<T> inOrder() {
List<T> result = new ArrayList<>();
inOrder(root, result);
return result;
}
private void inOrder(Node<T> node, List<T> result) {
if (node != null) {
inOrder(node.left, result);
result.add(node.data);
inOrder(node.right, result);
}
}
/**
* 按层打印树结构（用于可视化调试）
*/
public void printTree() {
if (root == null) {
System.out.println("空树");
return;
}
printTree(root, "", true);
}
private void printTree(Node<T> node, String prefix, boolean isTail) {
if (node == null) return;
System.out.println(prefix + (isTail ? "└── " : "├── ") +
node.data + " [h=" + node.height + ", bf=" + balanceFactor(node) + "]");
List<Node<T>> children = new ArrayList<>();
if (node.left != null) children.add(node.left);
if (node.right != null) children.add(node.right);
for (int i = 0; i < children.size(); i++) {
boolean isLast = (i == children.size() - 1);
printTree(children.get(i), prefix + (isTail ? " " : "│ "), isLast);
}
}
// ==================== 主程序：演示与测试 ====================
public static void main(String[] args) {
AVLTree<Integer> tree = new AVLTree<>();
System.out.println("=== AVL树插入演示 ===");
int[] insertValues = {30, 20, 40, 10, 25, 35, 50, 5, 15, 27};
for (int val : insertValues) {
System.out.println("\n插入: " + val);
tree.insert(val);
tree.printTree();
System.out.println("树高度: " + tree.height() +
", 节点数: " + tree.size() +
", 平衡因子范围: [-1, 1]");
}
System.out.println("\n=== 中序遍历结果 ===");
System.out.println(tree.inOrder());
System.out.println("\n=== AVL树删除演示 ===");
System.out.println("删除 20（有两个子节点的内部节点）");
tree.delete(20);
tree.printTree();
System.out.println("\n删除 5（叶子节点）");
tree.delete(5);
tree.printTree();
System.out.println("\n=== 查找测试 ===");
System.out.println("包含 25? " + tree.contains(25));
System.out.println("包含 100? " + tree.contains(100));
// 大规模性能测试
System.out.println("\n=== 大规模性能测试（10万元素） ===");
AVLTree<Integer> bigTree = new AVLTree<>();
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
bigTree.insert((int)(Math.random() * 1000000));
}
long insertTime = System.currentTimeMillis() - start;
System.out.println("插入10万个随机元素耗时: " + insertTime + "ms");
System.out.println("树高度: " + bigTree.height() + " (理论最优: ~17)");
System.out.println("节点数: " + bigTree.size());
start = System.currentTimeMillis();
int found = 0;
for (int i = 0; i < 100000; i++) {
if (bigTree.contains((int)(Math.random() * 1000000))) {
found++;
}
}
long searchTime = System.currentTimeMillis() - start;
System.out.println("10万次查找耗时: " + searchTime + "ms, 命中次数: " + found);
}
}
四、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 查找 | O(log n) | O(1) | 树高严格控制在O(log n) |
| 插入 | O(log n) | O(log n) | 递归栈深度为树高 |
| 删除 | O(log n) | O(log n) | 最坏情况需要一次旋转 |
| 旋转 | O(1) | O(1) | 仅修改少量指针 |
AVL树的高度上限约为 1.44 * log₂(n + 2) - 0.328，这意味着包含10万个节点的AVL树高度不超过24，查找操作最多只需24次比较。
五、AVL树与红黑树的对比
| 特性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡条件 | 左右子树高度差 ≤ 1 | 从根到叶子的最长路径 ≤ 2倍最短路径 |
| 查找效率 | 更优（树高更小） | 略低（树高最多2倍于AVL） |
| 插入旋转次数 | 最多2次 | 最多2次 |
| 删除旋转次数 | 最多O(log n)次 | 最多3次 |
| 适用场景 | 读多写少（查询频繁） | 读写均衡（Java TreeMap/TreeSet） |
| 实现复杂度 | 稍高 | 稍低 |
六、应用场景
AVL树在以下场景中表现优异：
- 数据库索引：当查询远多于更新时，AVL树的低高度带来更快的检索速度
- 内存中的有序集合：需要频繁进行范围查询和顺序访问的场景
- 编译器符号表：标识符查找远多于插入删除的场景
- 实时系统：严格的时间复杂度保证对确定性要求高的场景
七、总结
AVL树通过维护节点高度和四种旋转操作，确保了二叉搜索树的严格平衡。理解LL、RR、LR、RL四种失衡类型及其对应的旋转策略，是掌握自平衡树的关键。虽然Java标准库选择了红黑树作为TreeMap和TreeSet的底层实现，但AVL树在查询密集型应用中仍具有不可替代的优势。
