算法背景
二叉搜索树（BST）在最坏情况下会退化为链表，导致查找、插入、删除操作的时间复杂度从 O(log n) 恶化到 O(n)。红黑树（Red-Black Tree）通过引入颜色标记和五条约束规则，确保树的高度始终保持在 O(log n)，是 Java TreeMap、TreeSet 以及 Linux 内核 CFS 调度器的底层实现，也是工程中最常用的平衡树结构。
核心思想
红黑树节点维护一个颜色属性（红或黑），并满足以下规则：
1. 每个节点是红色或黑色；
2. 根节点是黑色；
3. 所有叶子（NIL）是黑色；
4. 红色节点的子节点必须是黑色（无连续红节点）；
5. 从任一节点到其每个叶子的简单路径上，黑色节点数量相同（黑高相等）。
通过这些约束，红黑树保证任意路径长度不超过最短路径的两倍，从而实现近似平衡。
完整Java实现
public class RedBlackTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
K key;
V value;
Node left, right, parent;
boolean color;
Node(K key, V value) {
this.key = key;
this.value = value;
this.color = RED; // 新节点默认为红色
}
}
private Node root;
private int size;
public RedBlackTree() {
root = null;
size = 0;
}
private boolean isRed(Node node) {
return node != null && node.color == RED;
}
/**
* 左旋操作：将右子节点提升为父节点
*/
private void rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != null) 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 rotateRight(Node y) {
Node x = y.left;
y.left = x.right;
if (x.right != null) 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;
}
/**
* 插入操作：先按BST规则插入，再通过旋转和变色修复平衡
*/
public void put(K key, V value) {
Node newNode = new Node(key, value);
if (root == null) {
root = newNode;
root.color = BLACK;
size++;
return;
}
// BST插入
Node parent = null, current = root;
while (current != null) {
parent = current;
int cmp = key.compareTo(current.key);
if (cmp < 0) current = current.left;
else if (cmp > 0) current = current.right;
else { current.value = value; return; }
}
newNode.parent = parent;
int cmp = key.compareTo(parent.key);
if (cmp < 0) parent.left = newNode;
else parent.right = newNode;
size++;
// 修复红黑树性质
fixInsert(newNode);
}
private void fixInsert(Node z) {
while (z.parent != null && z.parent.color == RED) {
if (z.parent == z.parent.parent.left) {
Node y = z.parent.parent.right; // 叔节点
if (isRed(y)) {
// Case 1: 叔节点为红色，变色即可
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else {
if (z == z.parent.right) {
// Case 2: 当前节点是右子节点，先左旋
z = z.parent;
rotateLeft(z);
}
// Case 3: 当前节点是左子节点，右旋并变色
z.parent.color = BLACK;
z.parent.parent.color = RED;
rotateRight(z.parent.parent);
}
} else {
// 对称情况
Node y = z.parent.parent.left;
if (isRed(y)) {
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else {
if (z == z.parent.left) {
z = z.parent;
rotateRight(z);
}
z.parent.color = BLACK;
z.parent.parent.color = RED;
rotateLeft(z.parent.parent);
}
}
}
root.color = BLACK; // 确保根节点为黑色
}
/**
* 查找操作
*/
public V get(K key) {
Node current = root;
while (current != null) {
int cmp = key.compareTo(current.key);
if (cmp < 0) current = current.left;
else if (cmp > 0) current = current.right;
else return current.value;
}
return null;
}
public boolean contains(K key) {
return get(key) != null;
}
public int size() {
return size;
}
/**
* 中序遍历输出（验证BST性质）
*/
public void inorder() {
inorderHelper(root);
System.out.println();
}
private void inorderHelper(Node node) {
if (node == null) return;
inorderHelper(node.left);
System.out.print(node.key + "(" + (node.color == RED ? "R" : "B") + ") ");
inorderHelper(node.right);
}
public static void main(String[] args) {
RedBlackTree<Integer, String> tree = new RedBlackTree<>();
int[] keys = {10, 20, 30, 15, 25, 5, 1};
System.out.println("依次插入: " + java.util.Arrays.toString(keys));
for (int k : keys) {
tree.put(k, "val" + k);
System.out.print("插入 " + k + " 后中序: ");
tree.inorder();
}
System.out.println("\\n查找 15: " + tree.get(15));
System.out.println("查找 100: " + tree.get(100));
System.out.println("树大小: " + tree.size());
}
}
复杂度分析
- 查找：O(log n) 时间，树高不超过 2log₂(n+1)。
- 插入：O(log n) 时间，最多两次旋转即可恢复平衡。
- 删除：O(log n) 时间，最多三次旋转。
- 空间：O(n) 存储节点。
应用场景
红黑树是工程实现中的首选平衡树：Java 的 java.util.TreeMap 和 java.util.TreeSet 基于红黑树；C++ STL 的 map 和 set 通常也采用红黑树实现；Linux 内核的完全公平调度器（CFS）使用红黑树管理进程调度实体。理解红黑树的旋转与变色操作，是掌握高级数据结构的重要一步。
