每日算法 — 使用java实现红黑树：自平衡二叉搜索树与旋转修复策略

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，由Rudolf Bayer于1972年发明。它通过对节点着色（红色或黑色）并维护五条核心性质，确保任意路径的长度不超过其他路径的两倍，从而保证了查找、插入、删除操作的最坏时间复杂度均为O(log n)。红黑树是Java中TreeMap、TreeSet以及JDK 8后HashMap链表转树的底层实现，是工业级代码中最常用的平衡树结构。

五条核心性质

1. 每个节点要么是红色，要么是黑色
2. 根节点永远是黑色
3. 所有叶子节点（NIL节点）都是黑色
4. 红色节点的两个子节点必须是黑色（不存在连续红节点）
5. 从任一节点到其每个叶子节点的所有简单路径上，黑色节点数量相同（黑高一致）

性质4和5共同保证了树的高度上限为 $2\log_2(n+1)$，从而确保了操作的对数级复杂度。

Java完整实现

/**
 * 红黑树实现 - 自平衡二叉搜索树
 * 支持动态插入、删除与有序遍历，保证最坏O(log n)操作效率
 * @param <T> 元素类型，需实现Comparable接口
 */
public class RedBlackTree<T extends Comparable<T>> {
    /** 定义颜色常量 */
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    /**
     * 树节点内部类
     * 包含数据、颜色、左右子节点和父节点引用
     */
    private class Node {
        T value;
        boolean color;
        Node left, right, parent;

        Node(T value) {
            this.value = value;
            this.color = RED; // 新插入节点默认为红色
            this.left = this.right = this.parent = null;
        }
    }

    private Node root;
    private int size;

    public RedBlackTree() {
        this.root = null;
        this.size = 0;
    }

    /**
     * 判断节点颜色，NIL节点视为黑色
     */
    private boolean isRed(Node node) {
        return node != null && node.color == RED;
    }

    /**
     * 左旋操作：以node为支点逆时针旋转
     * 适用于修复"右右"或"右左"型不平衡
     * @param node 旋转支点
     */
    private void rotateLeft(Node node) {
        Node rightChild = node.right;
        node.right = rightChild.left;
        if (rightChild.left != null) {
            rightChild.left.parent = node;
        }
        rightChild.parent = node.parent;
        if (node.parent == null) {
            root = rightChild;
        } else if (node == node.parent.left) {
            node.parent.left = rightChild;
        } else {
            node.parent.right = rightChild;
        }
        rightChild.left = node;
        node.parent = rightChild;
    }

    /**
     * 右旋操作：以node为支点顺时针旋转
     * 适用于修复"左左"或"左右"型不平衡
     * @param node 旋转支点
     */
    private void rotateRight(Node node) {
        Node leftChild = node.left;
        node.left = leftChild.right;
        if (leftChild.right != null) {
            leftChild.right.parent = node;
        }
        leftChild.parent = node.parent;
        if (node.parent == null) {
            root = leftChild;
        } else if (node == node.parent.right) {
            node.parent.right = leftChild;
        } else {
            node.parent.left = leftChild;
        }
        leftChild.right = node;
        node.parent = leftChild;
    }

    /**
     * 插入新元素
     * 先执行标准BST插入，再自底向上修复红黑性质
     * @param value 待插入的值
     */
    public void insert(T value) {
        Node newNode = new Node(value);
        Node parent = null;
        Node current = root;

        // 标准BST查找插入位置
        while (current != null) {
            parent = current;
            int cmp = value.compareTo(current.value);
            if (cmp < 0) {
                current = current.left;
            } else if (cmp > 0) {
                current = current.right;
            } else {
                return; // 值已存在，不重复插入
            }
        }

        newNode.parent = parent;
        if (parent == null) {
            root = newNode;
        } else if (value.compareTo(parent.value) < 0) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        size++;

        // 修复因插入红色节点可能破坏的红黑性质
        fixInsert(newNode);
        root.color = BLACK; // 确保根节点始终为黑色
    }

    /**
     * 插入修复：处理连续红色节点的冲突
     * 分三种情况：叔叔节点为红、叔叔为黑且呈三角形、叔叔为黑且呈直线
     * @param node 新插入的红色节点
     */
    private void fixInsert(Node node) {
        while (isRed(node.parent)) {
            if (node.parent == node.parent.parent.left) {
                Node uncle = node.parent.parent.right;
                // 情况1：叔叔节点为红色，直接变色即可
                if (isRed(uncle)) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                } else {
                    // 情况2：叔叔为黑，当前节点是右孩子（三角形）
                    if (node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);
                    }
                    // 情况3：叔叔为黑，当前节点是左孩子（直线）
                    node.parent.color = BLACK;
                    node.parent.parent.color = RED;
                    rotateRight(node.parent.parent);
                }
            } else {
                // 对称情况：父节点是右孩子
                Node uncle = node.parent.parent.left;
                if (isRed(uncle)) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.left) {
                        node = node.parent;
                        rotateRight(node);
                    }
                    node.parent.color = BLACK;
                    node.parent.parent.color = RED;
                    rotateLeft(node.parent.parent);
                }
            }
        }
    }

    /**
     * 查找元素
     * @param value 目标值
     * @return 存在返回true
     */
    public boolean contains(T value) {
        Node current = root;
        while (current != null) {
            int cmp = value.compareTo(current.value);
            if (cmp == 0) return true;
            current = (cmp < 0) ? current.left : current.right;
        }
        return false;
    }

    /**
     * 中序遍历输出有序序列
     */
    public void inorderTraversal() {
        System.out.print("中序遍历结果: ");
        inorderHelper(root);
        System.out.println();
    }

    private void inorderHelper(Node node) {
        if (node != null) {
            inorderHelper(node.left);
            System.out.print(node.value + "(" + (node.color == RED ? "R" : "B") + ") ");
            inorderHelper(node.right);
        }
    }

    /**
     * 获取树的高度（用于验证平衡性）
     */
    public int height() {
        return heightHelper(root);
    }

    private int heightHelper(Node node) {
        if (node == null) return 0;
        return 1 + Math.max(heightHelper(node.left), heightHelper(node.right));
    }

    public int size() {
        return size;
    }

    /**
     * 主方法：演示红黑树的动态平衡特性
     */
    public static void main(String[] args) {
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        int[] data = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};

        System.out.println("依次插入: " + java.util.Arrays.toString(data));
        for (int num : data) {
            tree.insert(num);
            System.out.println("插入 " + num + " 后树高: " + tree.height());
        }

        tree.inorderTraversal();
        System.out.println("\n查找测试:");
        System.out.println("contains(25): " + tree.contains(25));
        System.out.println("contains(100): " + tree.contains(100));
        System.out.println("\n总节点数: " + tree.size() + ", 树高: " + tree.height());
        System.out.println("理想最小高度: " + (int)(Math.log(tree.size()) / Math.log(2)) + 
            ", 红黑树保证高度 ≤ 2*理想高度");
    }
}

复杂度分析

红黑树的平衡性弱于AVL树（允许高度差两倍），但插入和删除所需的旋转次数更少（最多3次旋转），因此写操作更频繁的场景下性能更优。

与AVL树的对比

工业级应用

• Java集合框架：TreeMap、TreeSet基于红黑树实现有序映射/集合
• HashMap优化：JDK 8中当链表长度超过8时转为红黑树，将查询复杂度从O(n)降至O(log n)
• Linux内核：CFS调度器使用红黑树管理进程vruntime，实现O(log n)的任务选择
• 数据库索引：部分数据库使用红黑树作为内存索引结构