红黑树（Red-Black Tree）是一种自平衡二叉搜索树，在计算机科学中有着广泛的应用。Java的TreeMap、TreeSet底层就是使用红黑树实现的。本文将深入讲解红黑树的原理、性质以及如何用Java实现一棵完整的红黑树。

什么是红黑树？

定义

红黑树是一种特殊的二叉搜索树，每个节点都带有颜色属性（红色或黑色）。通过对节点颜色的约束，红黑树确保从根到叶子的最长路径不会超过最短路径的2倍，从而保持树的平衡。

红黑树的五条性质

1. 每个节点不是红色就是黑色

2. 根节点是黑色

3. 所有叶子节点（NIL节点）是黑色

4. 红色节点的两个子节点都是黑色（不能有两个连续的红色节点）

5. 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（黑色高度相同）

为什么需要红黑树？

• 普通二叉搜索树：可能退化成链表，时间复杂度O(n)

• AVL树：严格平衡，插入删除需要频繁旋转

• 红黑树：近似平衡，插入删除最多旋转3次，性能更稳定

红黑树节点的定义

/**
 * 红黑树节点类
 */
class RBNode<T extends Comparable<T>> {
    T data;                 // 数据
    RBNode<T> left;        // 左子节点
    RBNode<T> right;       // 右子节点
    RBNode<T> parent;      // 父节点
    boolean color;         // 颜色：true表示红色，false表示黑色
    
    // 颜色常量
    public static final boolean RED = true;
    public static final boolean BLACK = false;
    
    public RBNode(T data) {
        this.data = data;
        this.color = RED;  // 新插入的节点默认为红色
        this.left = null;
        this.right = null;
        this.parent = null;
    }
    
    public RBNode(T data, boolean color) {
        this.data = data;
        this.color = color;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
    
    @Override
    public String toString() {
        return data + "(" + (color == RED ? "R" : "B") + ")";
    }
}

红黑树的旋转操作

旋转是维护红黑树平衡的基本操作，分为左旋和右旋。

左旋（Left Rotate）

    x                    y
   / \    左旋(x)       / \
  α   y   ------->    x   γ
     / \             / \
    β   γ           α   β

右旋（Right Rotate）

      y                x
     / \   右旋(y)     / \
    x   γ  ------->  α   y
   / \                  / \
  α   β                β   γ

Java实现

/**
 * 左旋操作
 * @param x 要旋转的节点
 */
private void leftRotate(RBNode<T> x) {
    RBNode<T> y = x.right;
    
    // 1. 将y的左子树变成x的右子树
    x.right = y.left;
    if (y.left != null) {
        y.left.parent = x;
    }
    
    // 2. 将x的父节点变成y的父节点
    y.parent = x.parent;
    if (x.parent == null) {
        this.root = y;  // x是根节点
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }
    
    // 3. 将x变成y的左子节点
    y.left = x;
    x.parent = y;
}
​
/**
 * 右旋操作
 * @param y 要旋转的节点
 */
private void rightRotate(RBNode<T> y) {
    RBNode<T> x = y.left;
    
    // 1. 将x的右子树变成y的左子树
    y.left = x.right;
    if (x.right != null) {
        x.right.parent = y;
    }
    
    // 2. 将y的父节点变成x的父节点
    x.parent = y.parent;
    if (y.parent == null) {
        this.root = x;  // y是根节点
    } else if (y == y.parent.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }
    
    // 3. 将y变成x的右子节点
    x.right = y;
    y.parent = x;
}

插入操作

红黑树的插入分为两步：

1. 按照二叉搜索树的方式插入节点（节点颜色为红色）

2. 修复红黑树的性质

插入修复的三种情况

情况1：叔叔节点是红色

• 解决方法：将父节点和叔叔节点变黑，祖父节点变红，然后以祖父节点为当前节点继续向上修复

情况2：叔叔节点是黑色，且当前节点是右子节点

• 解决方法：以父节点为支点进行左旋，转化为情况3

情况3：叔叔节点是黑色，且当前节点是左子节点

• 解决方法：将父节点变黑，祖父节点变红，以祖父节点为支点右旋

Java实现

/**
 * 插入节点
 */
public void insert(T data) {
    RBNode<T> newNode = new RBNode<>(data);
    
    // 1. 按照二叉搜索树的方式插入
    if (root == null) {
        root = newNode;
        root.color = RBNode.BLACK;  // 根节点必须是黑色
        return;
    }
    
    RBNode<T> parent = null;
    RBNode<T> current = root;
    
    while (current != null) {
        parent = current;
        if (data.compareTo(current.data) < 0) {
            current = current.left;
        } else if (data.compareTo(current.data) > 0) {
            current = current.right;
        } else {
            return;  // 已存在，不插入
        }
    }
    
    newNode.parent = parent;
    if (data.compareTo(parent.data) < 0) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    
    // 2. 修复红黑树性质
    insertFixup(newNode);
}
​
/**
 * 插入后修复红黑树性质
 */
private void insertFixup(RBNode<T> node) {
    // 当父节点是红色时需要修复
    while (node.parent != null && node.parent.color == RBNode.RED) {
        // 父节点是祖父节点的左子节点
        if (node.parent == node.parent.parent.left) {
            RBNode<T> uncle = node.parent.parent.right;  // 叔叔节点
            
            // 情况1：叔叔节点是红色
            if (uncle != null && uncle.color == RBNode.RED) {
                node.parent.color = RBNode.BLACK;
                uncle.color = RBNode.BLACK;
                node.parent.parent.color = RBNode.RED;
                node = node.parent.parent;  // 向上继续修复
            } else {
                // 情况2：叔叔是黑色，且当前节点是右子节点
                if (node == node.parent.right) {
                    node = node.parent;
                    leftRotate(node);
                }
                // 情况3：叔叔是黑色，且当前节点是左子节点
                node.parent.color = RBNode.BLACK;
                node.parent.parent.color = RBNode.RED;
                rightRotate(node.parent.parent);
            }
        } else {  // 父节点是祖父节点的右子节点（镜像操作）
            RBNode<T> uncle = node.parent.parent.left;
            
            if (uncle != null && uncle.color == RBNode.RED) {
                node.parent.color = RBNode.BLACK;
                uncle.color = RBNode.BLACK;
                node.parent.parent.color = RBNode.RED;
                node = node.parent.parent;
            } else {
                if (node == node.parent.left) {
                    node = node.parent;
                    rightRotate(node);
                }
                node.parent.color = RBNode.BLACK;
                node.parent.parent.color = RBNode.RED;
                leftRotate(node.parent.parent);
            }
        }
    }
    
    root.color = RBNode.BLACK;  // 确保根节点是黑色
}

删除操作

删除操作比插入更复杂，分为三步：

1. 按照二叉搜索树的方式删除节点

2. 如果删除的是黑色节点，需要修复红黑树性质

3. 调整颜色和结构

Java实现

/**
 * 删除节点
 */
public void delete(T data) {
    RBNode<T> node = search(data);
    if (node == null) {
        return;
    }
    deleteNode(node);
}
​
/**
 * 删除指定节点
 */
private void deleteNode(RBNode<T> node) {
    RBNode<T> replace;
    RBNode<T> child;
    
    // 1. 找到实际要删除的节点
    if (node.left != null && node.right != null) {
        // 有两个子节点，找到后继节点
        replace = successor(node);
        node.data = replace.data;
        node = replace;
    }
    
    // 2. 此时node最多只有一个子节点
    child = (node.left != null) ? node.left : node.right;
    
    // 3. 删除节点
    if (child != null) {
        child.parent = node.parent;
    }
    
    if (node.parent == null) {
        root = child;
    } else if (node == node.parent.left) {
        node.parent.left = child;
    } else {
        node.parent.right = child;
    }
    
    // 4. 如果删除的是黑色节点，需要修复
    if (node.color == RBNode.BLACK) {
        if (child != null) {
            deleteFixup(child);
        } else if (node.parent != null) {
            deleteFixup(node);
            // 删除node
            if (node == node.parent.left) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
        }
    }
}
​
/**
 * 删除后修复红黑树性质
 */
private void deleteFixup(RBNode<T> node) {
    while (node != root && getColor(node) == RBNode.BLACK) {
        if (node == node.parent.left) {
            RBNode<T> sibling = node.parent.right;
            
            // 情况1：兄弟节点是红色
            if (getColor(sibling) == RBNode.RED) {
                sibling.color = RBNode.BLACK;
                node.parent.color = RBNode.RED;
                leftRotate(node.parent);
                sibling = node.parent.right;
            }
            
            // 情况2：兄弟节点是黑色，且两个子节点都是黑色
            if (getColor(sibling.left) == RBNode.BLACK && 
                getColor(sibling.right) == RBNode.BLACK) {
                sibling.color = RBNode.RED;
                node = node.parent;
            } else {
                // 情况3：兄弟节点是黑色，左子是红色，右子是黑色
                if (getColor(sibling.right) == RBNode.BLACK) {
                    if (sibling.left != null) {
                        sibling.left.color = RBNode.BLACK;
                    }
                    sibling.color = RBNode.RED;
                    rightRotate(sibling);
                    sibling = node.parent.right;
                }
                // 情况4：兄弟节点是黑色，右子是红色
                sibling.color = node.parent.color;
                node.parent.color = RBNode.BLACK;
                if (sibling.right != null) {
                    sibling.right.color = RBNode.BLACK;
                }
                leftRotate(node.parent);
                node = root;
            }
        } else {
            // 镜像操作
            RBNode<T> sibling = node.parent.left;
            
            if (getColor(sibling) == RBNode.RED) {
                sibling.color = RBNode.BLACK;
                node.parent.color = RBNode.RED;
                rightRotate(node.parent);
                sibling = node.parent.left;
            }
            
            if (getColor(sibling.right) == RBNode.BLACK && 
                getColor(sibling.left) == RBNode.BLACK) {
                sibling.color = RBNode.RED;
                node = node.parent;
            } else {
                if (getColor(sibling.left) == RBNode.BLACK) {
                    if (sibling.right != null) {
                        sibling.right.color = RBNode.BLACK;
                    }
                    sibling.color = RBNode.RED;
                    leftRotate(sibling);
                    sibling = node.parent.left;
                }
                sibling.color = node.parent.color;
                node.parent.color = RBNode.BLACK;
                if (sibling.left != null) {
                    sibling.left.color = RBNode.BLACK;
                }
                rightRotate(node.parent);
                node = root;
            }
        }
    }
    if (node != null) {
        node.color = RBNode.BLACK;
    }
}
​
/**
 * 找到后继节点（右子树的最小节点）
 */
private RBNode<T> successor(RBNode<T> node) {
    if (node.right != null) {
        RBNode<T> current = node.right;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }
    return null;
}
​
/**
 * 获取节点颜色（处理null节点）
 */
private boolean getColor(RBNode<T> node) {
    return node == null ? RBNode.BLACK : node.color;
}

完整的红黑树实现

import java.util.*;
​
/**
 * 红黑树的完整实现
 */
public class RedBlackTree<T extends Comparable<T>> {
    private RBNode<T> root;
    
    public RedBlackTree() {
        this.root = null;
    }
    
    // [插入、删除、旋转等方法的完整实现见上文]
    
    /**
     * 搜索节点
     */
    public RBNode<T> search(T data) {
        return searchHelper(root, data);
    }
    
    private RBNode<T> searchHelper(RBNode<T> node, T data) {
        if (node == null) {
            return null;
        }
        
        int cmp = data.compareTo(node.data);
        if (cmp < 0) {
            return searchHelper(node.left, data);
        } else if (cmp > 0) {
            return searchHelper(node.right, data);
        } else {
            return node;
        }
    }
    
    /**
     * 查找最小值
     */
    public T findMin() {
        if (root == null) {
            return null;
        }
        RBNode<T> node = root;
        while (node.left != null) {
            node = node.left;
        }
        return node.data;
    }
    
    /**
     * 查找最大值
     */
    public T findMax() {
        if (root == null) {
            return null;
        }
        RBNode<T> node = root;
        while (node.right != null) {
            node = node.right;
        }
        return node.data;
    }
    
    /**
     * 中序遍历（升序输出）
     */
    public void inorderTraversal() {
        System.out.print("中序遍历: ");
        inorderHelper(root);
        System.out.println();
    }
    
    private void inorderHelper(RBNode<T> node) {
        if (node != null) {
            inorderHelper(node.left);
            System.out.print(node + " ");
            inorderHelper(node.right);
        }
    }
    
    /**
     * 前序遍历
     */
    public void preorderTraversal() {
        System.out.print("前序遍历: ");
        preorderHelper(root);
        System.out.println();
    }
    
    private void preorderHelper(RBNode<T> node) {
        if (node != null) {
            System.out.print(node + " ");
            preorderHelper(node.left);
            preorderHelper(node.right);
        }
    }
    
    /**
     * 层序遍历
     */
    public void levelOrderTraversal() {
        if (root == null) {
            return;
        }
        
        System.out.println("层序遍历:");
        Queue<RBNode<T>> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                RBNode<T> node = queue.poll();
                System.out.print(node + " ");
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            System.out.println();
        }
    }
    
    /**
     * 打印树形结构
     */
    public void printTree() {
        System.out.println("\n树形结构:");
        printTreeHelper(root, "", true);
    }
    
    private void printTreeHelper(RBNode<T> node, String prefix, boolean isTail) {
        if (node == null) {
            return;
        }
        
        System.out.println(prefix + (isTail ? "└── " : "├── ") + node);
        
        if (node.left != null || node.right != null) {
            if (node.right != null) {
                printTreeHelper(node.right, prefix + (isTail ? "    " : "│   "), false);
            } else {
                System.out.println(prefix + (isTail ? "    " : "│   ") + "├── null");
            }
            
            if (node.left != null) {
                printTreeHelper(node.left, prefix + (isTail ? "    " : "│   "), true);
            } else {
                System.out.println(prefix + (isTail ? "    " : "│   ") + "└── null");
            }
        }
    }
    
    /**
     * 验证是否为有效的红黑树
     */
    public boolean isValidRedBlackTree() {
        if (root == null) {
            return true;
        }
        
        // 性质2：根节点必须是黑色
        if (root.color != RBNode.BLACK) {
            System.out.println("违反性质2：根节点不是黑色");
            return false;
        }
        
        // 检查其他性质
        return validateHelper(root) != -1;
    }
    
    private int validateHelper(RBNode<T> node) {
        if (node == null) {
            return 0;  // NIL节点是黑色，黑高为0
        }
        
        // 性质4：红色节点的子节点必须是黑色
        if (node.color == RBNode.RED) {
            if ((node.left != null && node.left.color == RBNode.RED) ||
                (node.right != null && node.right.color == RBNode.RED)) {
                System.out.println("违反性质4：红色节点 " + node.data + " 有红色子节点");
                return -1;
            }
        }
        
        // 递归检查左右子树
        int leftBlackHeight = validateHelper(node.left);
        int rightBlackHeight = validateHelper(node.right);
        
        if (leftBlackHeight == -1 || rightBlackHeight == -1) {
            return -1;
        }
        
        // 性质5：从节点到叶子节点的所有路径必须包含相同数量的黑色节点
        if (leftBlackHeight != rightBlackHeight) {
            System.out.println("违反性质5：节点 " + node.data + 
                             " 的左右子树黑高不同 (" + leftBlackHeight + 
                             " vs " + rightBlackHeight + ")");
            return -1;
        }
        
        // 返回黑高
        return leftBlackHeight + (node.color == RBNode.BLACK ? 1 : 0);
    }
    
    /**
     * 获取树的高度
     */
    public int getHeight() {
        return getHeightHelper(root);
    }
    
    private int getHeightHelper(RBNode<T> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(getHeightHelper(node.left), getHeightHelper(node.right));
    }
    
    /**
     * 获取黑高
     */
    public int getBlackHeight() {
        return getBlackHeightHelper(root);
    }
    
    private int getBlackHeightHelper(RBNode<T> node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = getBlackHeightHelper(node.left);
        return leftHeight + (node.color == RBNode.BLACK ? 1 : 0);
    }
    
    /**
     * 获取节点数量
     */
    public int size() {
        return sizeHelper(root);
    }
    
    private int sizeHelper(RBNode<T> node) {
        if (node == null) {
            return 0;
        }
        return 1 + sizeHelper(node.left) + sizeHelper(node.right);
    }
}

使用示例和测试

public class RedBlackTreeDemo {
    public static void main(String[] args) {
        demonstrateBasicOperations();
        System.out.println("\n" + "=".repeat(80) + "\n");
        demonstrateInsertionSequence();
        System.out.println("\n" + "=".repeat(80) + "\n");
        demonstrateDeletion();
    }
    
    /**
     * 演示基本操作
     */
    private static void demonstrateBasicOperations() {
        System.out.println("【演示1：红黑树基本操作】\n");
        
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        
        // 插入元素
        int[] values = {10, 20, 30, 15, 25, 5, 1};
        System.out.println("依次插入: " + Arrays.toString(values));
        
        for (int value : values) {
            tree.insert(value);
            System.out.println("\n插入 " + value + " 后:");
            tree.printTree();
        }
        
        System.out.println("\n树的信息:");
        System.out.println("节点数量: " + tree.size());
        System.out.println("树高度: " + tree.getHeight());
        System.out.println("黑高: " + tree.getBlackHeight());
        System.out.println("最小值: " + tree.findMin());
        System.out.println("最大值: " + tree.findMax());
        
        // 遍历
        System.out.println();
        tree.inorderTraversal();
        tree.preorderTraversal();
        tree.levelOrderTraversal();
        
        // 验证
        System.out.println("\n是否为有效的红黑树: " + tree.isValidRedBlackTree());
    }
    
    /**
     * 演示插入序列的变化
     */
    private static void demonstrateInsertionSequence() {
        System.out.println("【演示2：顺序插入的自平衡过程】\n");
        
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        
        System.out.println("顺序插入 1-7:");
        for (int i = 1; i <= 7; i++) {
            tree.insert(i);
            System.out.println("\n插入 " + i + " 后:");
            tree.printTree();
            System.out.println("树高度: " + tree.getHeight() + 
                             ", 黑高: " + tree.getBlackHeight());
        }
        
        System.out.println("\n最终树的遍历结果:");
        tree.inorderTraversal();
        System.out.println("是否为有效的红黑树: " + tree.isValidRedBlackTree());
    }
    
    /**
     * 演示删除操作
     */
    private static void demonstrateDeletion() {
        System.out.println("【演示3：删除操作】\n");
        
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        
        // 构建一棵红黑树
        int[] values = {50, 25, 75, 10, 30, 60, 80, 5, 15, 27, 55, 65};
        System.out.println("插入元素: " + Arrays.toString(values));
        for (int value : values) {
            tree.insert(value);
        }
        
        System.out.println("\n初始树结构:");
        tree.printTree();
        tree.inorderTraversal();
        
        // 删除节点
        int[] toDelete = {10, 25, 50};
        for (int value : toDelete) {
            System.out.println("\n删除 " + value + " 后:");
            tree.delete(value);
            tree.printTree();
            tree.inorderTraversal();
            System.out.println("是否有效: " + tree.isValidRedBlackTree());
        }
    }
}

性能分析

时间复杂度

操作	平均情况	最坏情况
搜索	O(log n)	O(log n)
插入	O(log n)	O(log n)
删除	O(log n)	O(log n)
最小值/最大值	O(log n)	O(log n)

空间复杂度

• O(n)，每个节点需要存储数据、颜色、三个指针

红黑树 vs AVL树

特性	红黑树	AVL树
平衡性	近似平衡	严格平衡
查询效率	O(log n)	O(log n)，略快
插入/删除	较快，最多旋转3次	较慢，可能多次旋转
适用场景	插入删除频繁	查询为主
实际应用	Java TreeMap/TreeSet	较少使用

红黑树的应用

1. Java集合框架

   • TreeMap

   • TreeSet

2. Linux内核

   • 进程调度（CFS调度器）

   • 虚拟内存管理

3. 数据库索引

   • MySQL的索引结构之一

4. C++ STL

   • map

   • set

   • multimap

   • multiset

关键要点总结

1. 插入策略

   • 新节点始终插入为红色

   • 根节点必须是黑色

   • 通过旋转和重新着色维护平衡

2. 删除策略

   • 删除黑色节点才需要修复

   • 通过兄弟节点的颜色判断情况