引言
二叉搜索树（BST）在理想情况下可以提供O(log n)的查找、插入和删除效率。然而，当数据有序或接近有序时，BST会退化为链表，操作效率降至O(n)。平衡树通过引入自平衡机制，确保树的高度始终维持在O(log n)级别。本文将深入讲解两种经典平衡树——AVL树和红黑树的平衡原理，并提供完整的Java实现。
核心算法概述
1. AVL树的平衡因子
AVL树要求每个节点的左右子树高度差（平衡因子）的绝对值不超过1。当插入或删除导致平衡因子超出[-1, 1]范围时，通过旋转操作恢复平衡。
2. 红黑树的五大约束
红黑树通过颜色标记（红/黑）和五条约束来维持近似平衡：
1. 每个节点要么是红色，要么是黑色
2. 根节点是黑色
3. 所有叶子（NIL）是黑色
4. 红色节点的子节点必须是黑色
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
Java完整实现
import java.util.*;
/**
* AVL树实现：基于平衡因子的严格平衡二叉搜索树
* 保证任意节点的左右子树高度差不超过1
*/
class AVLTree<T extends Comparable<T>> {
class Node {
T key;
Node left, right;
int height;
int size; // 子树节点数，支持顺序统计
Node(T key) {
this.key = key;
this.height = 1;
this.size = 1;
}
}
private Node root;
private int size;
public AVLTree() {
this.root = null;
this.size = 0;
}
/**
* 获取节点高度
*/
private int height(Node node) {
return node == null ? 0 : node.height;
}
/**
* 获取节点子树大小
*/
private int getSize(Node node) {
return node == null ? 0 : node.size;
}
/**
* 计算平衡因子：左子树高度 - 右子树高度
*/
private int balanceFactor(Node node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
/**
* 更新节点高度和子树大小
*/
private void updateNode(Node node) {
if (node != null) {
node.height = 1 + Math.max(height(node.left), height(node.right));
node.size = 1 + getSize(node.left) + getSize(node.right);
}
}
/**
* 右旋操作（RR旋转）
* 适用于左子树过高的情况（平衡因子 > 1）
*
* y x
* / \ / \
* x C ==> A y
* / \ / \
* A B B C
*/
private Node rotateRight(Node y) {
Node x = y.left;
Node B = x.right;
// 执行旋转
x.right = y;
y.left = B;
// 更新高度（注意顺序：先更新y，再更新x）
updateNode(y);
updateNode(x);
return x; // x成为新的子树根
}
/**
* 左旋操作（LL旋转）
* 适用于右子树过高的情况（平衡因子 < -1）
*
* x y
* / \ / \
* A y ==> x C
* / \ / \
* B C A B
*/
private Node rotateLeft(Node x) {
Node y = x.right;
Node B = y.left;
// 执行旋转
y.left = x;
x.right = B;
// 更新高度
updateNode(x);
updateNode(y);
return y; // y成为新的子树根
}
/**
* 重新平衡节点
* 根据平衡因子选择适当的旋转策略
*/
private Node rebalance(Node node) {
updateNode(node);
int bf = balanceFactor(node);
// 左子树过高
if (bf > 1) {
if (balanceFactor(node.left) < 0) {
// 左-右情况（LR）：先对左子节点左旋，再对当前节点右旋
node.left = rotateLeft(node.left);
}
// 左-左情况（LL）：直接右旋
return rotateRight(node);
}
// 右子树过高
if (bf < -1) {
if (balanceFactor(node.right) > 0) {
// 右-左情况（RL）：先对右子节点右旋，再对当前节点左旋
node.right = rotateRight(node.right);
}
// 右-右情况（RR）：直接左旋
return rotateLeft(node);
}
return node; // 已经平衡
}
/**
* 插入操作
*/
public void insert(T key) {
root = insert(root, key);
size++;
}
private Node insert(Node node, T key) {
if (node == null) {
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 {
// 重复键，不插入
size--; // 补偿外部size++
return node;
}
return rebalance(node);
}
/**
* 删除操作
*/
public void delete(T key) {
root = delete(root, key);
size--;
}
private Node delete(Node node, T key) {
if (node == null) {
size++; // 补偿外部size--
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 {
// 找到要删除的节点
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
// 有两个子节点：找到后继节点（右子树最小值）
Node successor = findMin(node.right);
node.key = successor.key;
node.right = delete(node.right, successor.key);
}
}
return rebalance(node);
}
private Node findMin(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
/**
* 查找操作
*/
public boolean contains(T key) {
return search(root, key) != null;
}
private Node search(Node node, T key) {
while (node != null) {
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else {
return node;
}
}
return null;
}
/**
* 获取第k小的元素（顺序统计）
* 利用子树大小信息实现O(log n)查询
*/
public T kthSmallest(int k) {
if (k < 1 || k > size) {
throw new IllegalArgumentException("k out of range");
}
return kthSmallest(root, k);
}
private T kthSmallest(Node node, int k) {
int leftSize = getSize(node.left);
if (k <= leftSize) {
return kthSmallest(node.left, k);
} else if (k == leftSize + 1) {
return node.key;
} else {
return kthSmallest(node.right, k - leftSize - 1);
}
}
/**
* 中序遍历
*/
public List<T> inorder() {
List<T> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(Node node, List<T> result) {
if (node != null) {
inorder(node.left, result);
result.add(node.key);
inorder(node.right, result);
}
}
public int size() {
return size;
}
}
/**
* 红黑树实现：基于颜色约束的近似平衡二叉搜索树
* 保证最长路径不超过最短路径的2倍
*/
class RedBlackTree<T extends Comparable<T>> {
// 颜色枚举
private enum Color { RED, BLACK }
class Node {
T key;
Node left, right, parent;
Color color;
Node(T key, Color color) {
this.key = key;
this.color = color;
}
}
private Node root;
private final Node NIL; // 所有叶子共享的哨兵节点
public RedBlackTree() {
NIL = new Node(null, Color.BLACK);
root = NIL;
}
/**
* 左旋操作
*/
private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != NIL) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
/**
* 右旋操作
*/
private void rightRotate(Node y) {
Node x = y.left;
y.left = x.right;
if (x.right != NIL) {
x.right.parent = y;
}
x.parent = y.parent;
if (y.parent == null) {
root = x;
} else if (y == y.parent.right) {
y.parent.right = x;
} else {
y.parent.left = x;
}
x.right = y;
y.parent = x;
}
/**
* 插入操作
* 1. 标准BST插入，新节点设为红色
* 2. 通过旋转和重新着色修复红黑性质
*/
public void insert(T key) {
Node z = new Node(key, Color.RED);
z.left = z.right = NIL;
Node y = null;
Node x = root;
// 标准BST插入
while (x != NIL) {
y = x;
if (key.compareTo(x.key) < 0) {
x = x.left;
} else {
x = x.right;
}
}
z.parent = y;
if (y == null) {
root = z;
} else if (key.compareTo(y.key) < 0) {
y.left = z;
} else {
y.right = z;
}
// 修复红黑性质
insertFixup(z);
}
/**
* 插入修复：处理红色节点相邻的违规情况
*/
private void insertFixup(Node z) {
while (z.parent != null && z.parent.color == Color.RED) {
if (z.parent == z.parent.parent.left) {
Node y = z.parent.parent.right; // 叔叔节点
if (y.color == Color.RED) {
// 情况1：叔叔是红色
z.parent.color = Color.BLACK;
y.color = Color.BLACK;
z.parent.parent.color = Color.RED;
z = z.parent.parent;
} else {
if (z == z.parent.right) {
// 情况2：叔叔是黑色，z是右孩子
z = z.parent;
leftRotate(z);
}
// 情况3：叔叔是黑色，z是左孩子
z.parent.color = Color.BLACK;
z.parent.parent.color = Color.RED;
rightRotate(z.parent.parent);
}
} else {
// 对称情况
Node y = z.parent.parent.left;
if (y.color == Color.RED) {
z.parent.color = Color.BLACK;
y.color = Color.BLACK;
z.parent.parent.color = Color.RED;
z = z.parent.parent;
} else {
if (z == z.parent.left) {
z = z.parent;
rightRotate(z);
}
z.parent.color = Color.BLACK;
z.parent.parent.color = Color.RED;
leftRotate(z.parent.parent);
}
}
}
root.color = Color.BLACK; // 根节点始终为黑色
}
/**
* 查找操作
*/
public boolean contains(T key) {
Node node = root;
while (node != NIL) {
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else {
return true;
}
}
return false;
}
/**
* 中序遍历
*/
public List<T> inorder() {
List<T> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(Node node, List<T> result) {
if (node != NIL) {
inorder(node.left, result);
result.add(node.key);
inorder(node.right, result);
}
}
/**
* 计算树的黑高度（验证红黑树性质）
*/
public int blackHeight() {
return blackHeight(root);
}
private int blackHeight(Node node) {
if (node == NIL) return 0;
int left = blackHeight(node.left);
return left + (node.color == Color.BLACK ? 1 : 0);
}
}
/**
* 测试与演示
*/
public class BalancedTreeDemo {
public static void main(String[] args) {
// AVL树测试
System.out.println("=== AVL树测试 ===");
AVLTree<Integer> avl = new AVLTree<>();
// 插入有序数据（BST的最坏情况）
int[] orderedData = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (int x : orderedData) {
avl.insert(x);
}
System.out.println("插入有序数据后的中序遍历: " + avl.inorder());
System.out.println("树大小: " + avl.size());
System.out.println("第5小元素: " + avl.kthSmallest(5));
// 删除测试
avl.delete(5);
System.out.println("删除5后: " + avl.inorder());
// 红黑树测试
System.out.println("\n=== 红黑树测试 ===");
RedBlackTree<Integer> rbt = new RedBlackTree<>();
for (int x : orderedData) {
rbt.insert(x);
}
System.out.println("插入有序数据后的中序遍历: " + rbt.inorder());
System.out.println("包含7? " + rbt.contains(7));
System.out.println("包含100? " + rbt.contains(100));
System.out.println("黑高度: " + rbt.blackHeight());
// 大规模性能对比
System.out.println("\n=== 大规模性能对比 ===");
benchmark();
}
private static void benchmark() {
int n = 100000;
Random rand = new Random(42);
Integer[] data = new Integer[n];
for (int i = 0; i < n; i++) {
data[i] = rand.nextInt(n * 10);
}
// AVL树
long start = System.nanoTime();
AVLTree<Integer> avl = new AVLTree<>();
for (int x : data) avl.insert(x);
long avlInsert = System.nanoTime() - start;
start = System.nanoTime();
for (int i = 0; i < n; i++) {
avl.contains(rand.nextInt(n * 10));
}
long avlSearch = System.nanoTime() - start;
// 红黑树
start = System.nanoTime();
RedBlackTree<Integer> rbt = new RedBlackTree<>();
for (int x : data) rbt.insert(x);
long rbtInsert = System.nanoTime() - start;
start = System.nanoTime();
for (int i = 0; i < n; i++) {
rbt.contains(rand.nextInt(n * 10));
}
long rbtSearch = System.nanoTime() - start;
System.out.printf("AVL树 - 插入: %.2f ms, 查找: %.2f ms%n",
avlInsert / 1e6, avlSearch / 1e6);
System.out.printf("红黑树 - 插入: %.2f ms, 查找: %.2f ms%n",
rbtInsert / 1e6, rbtSearch / 1e6);
}
}
算法复杂度分析
| 操作 | AVL树 | 红黑树 | 说明 |
|---|---|---|---|
| 查找 | O(log n) | O(log n) | 两者均保证对数时间 |
| 插入 | O(log n) | O(log n) | AVL最多2次旋转，红黑树最多2次旋转+重新着色 |
| 删除 | O(log n) | O(log n) | AVL最多O(log n)次旋转，红黑树最多3次旋转 |
| 空间 | O(n) | O(n) | 每个节点额外存储高度或颜色信息 |
AVL树 vs 红黑树
| 特性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡严格度 | 严格（高度差≤1） | 宽松（最长路径≤2倍最短路径） |
| 查找效率 | 略快 | 略慢（但常数差异很小） |
| 插入/删除旋转次数 | 较多 | 较少 |
| 适用场景 | 读多写少 | 读写均衡（如Java TreeMap） |
关键知识点总结
-
平衡因子的作用：AVL树通过维护每个节点的平衡因子，确保树的严格平衡。当平衡因子超出范围时，通过四种旋转组合（LL、RR、LR、RL）恢复平衡。
-
旋转的本质：旋转不会改变中序遍历的顺序，因此不会改变BST的搜索性质。它仅仅是通过改变节点间的链接关系来调整树的高度分布。
-
红黑树的着色策略：通过颜色约束替代高度约束，减少了旋转次数。黑色高度的统一性保证了任意路径的长度不会相差超过一倍。
-
NIL哨兵节点：红黑树实现中使用共享的NIL节点作为所有叶子，简化了边界条件的处理，使代码更加统一和健壮。
-
工业应用：Java的
TreeMap和TreeSet基于红黑树实现；Linux内核的CFS调度器使用红黑树管理进程；数据库索引（如MySQL InnoDB）广泛使用B+树（平衡树的扩展）。
