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

引言

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，它通过在节点中引入颜色属性（红或黑）并维护一组严格的平衡规则，确保树的高度始终保持在 $O(\log n)$ 级别。相比AVL树，红黑树的旋转次数更少，在实际应用中（如Java的TreeMap和TreeSet）表现更为出色。

红黑树的五大核心性质

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

节点定义

public class RBTreeNode<K extends Comparable<K>, V> {
    K key;
    V value;
    RBTreeNode<K, V> left, right, parent;
    boolean isRed; // true=红色, false=黑色

    public RBTreeNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.isRed = true; // 新节点默认红色
    }
}

核心操作：左旋与右旋

旋转操作是维护红黑树平衡的基础。左旋将右子节点提升为父节点，右旋则相反。

public class RedBlackTree<K extends Comparable<K>, V> {
    private RBTreeNode<K, V> root;
    private final RBTreeNode<K, V> NIL; // 哨兵叶子节点

    public RedBlackTree() {
        NIL = new RBTreeNode<>(null, null);
        NIL.isRed = false; // NIL为黑色
        root = NIL;
    }

    // 左旋：以x为支点，将其右子节点y提升
    private void leftRotate(RBTreeNode<K, V> x) {
        RBTreeNode<K, V> y = x.right;
        x.right = y.left;
        if (y.left != NIL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == NIL) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // 右旋：以y为支点，将其左子节点x提升
    private void rightRotate(RBTreeNode<K, V> y) {
        RBTreeNode<K, V> x = y.left;
        y.left = x.right;
        if (x.right != NIL) {
            x.right.parent = y;
        }
        x.parent = y.parent;
        if (y.parent == NIL) {
            root = x;
        } else if (y == y.parent.right) {
            y.parent.right = x;
        } else {
            y.parent.left = x;
        }
        x.right = y;
        y.parent = x;
    }
}

插入操作与平衡修复

新节点插入后若破坏红黑性质，需通过变色和旋转修复。修复分为三种情况：

    public void insert(K key, V value) {
        RBTreeNode<K, V> z = new RBTreeNode<>(key, value);
        z.left = z.right = NIL;

        RBTreeNode<K, V> y = NIL;
        RBTreeNode<K, V> x = root;

        // 标准BST插入
        while (x != NIL) {
            y = x;
            int cmp = key.compareTo(x.key);
            if (cmp < 0) x = x.left;
            else if (cmp > 0) x = x.right;
            else { x.value = value; return; } // 键已存在，更新值
        }

        z.parent = y;
        if (y == NIL) {
            root = z;
        } else if (key.compareTo(y.key) < 0) {
            y.left = z;
        } else {
            y.right = z;
        }

        z.isRed = true; // 新节点为红色
        insertFixup(z);
    }

    // 插入修复：处理红-红冲突
    private void insertFixup(RBTreeNode<K, V> z) {
        while (z.parent.isRed) {
            if (z.parent == z.parent.parent.left) {
                RBTreeNode<K, V> y = z.parent.parent.right; // 叔节点
                if (y.isRed) {
                    // 情况1：叔节点为红，变色上移
                    z.parent.isRed = false;
                    y.isRed = false;
                    z.parent.parent.isRed = true;
                    z = z.parent.parent;
                } else {
                    if (z == z.parent.right) {
                        // 情况2：z是右孩子，先左旋
                        z = z.parent;
                        leftRotate(z);
                    }
                    // 情况3：z是左孩子，右旋+变色
                    z.parent.isRed = false;
                    z.parent.parent.isRed = true;
                    rightRotate(z.parent.parent);
                }
            } else {
                // 对称情况
                RBTreeNode<K, V> y = z.parent.parent.left;
                if (y.isRed) {
                    z.parent.isRed = false;
                    y.isRed = false;
                    z.parent.parent.isRed = true;
                    z = z.parent.parent;
                } else {
                    if (z == z.parent.left) {
                        z = z.parent;
                        rightRotate(z);
                    }
                    z.parent.isRed = false;
                    z.parent.parent.isRed = true;
                    leftRotate(z.parent.parent);
                }
            }
        }
        root.isRed = false; // 根节点始终黑色
    }

查找与验证

    public V search(K key) {
        RBTreeNode<K, V> x = root;
        while (x != NIL) {
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x.value;
            x = (cmp < 0) ? x.left : x.right;
        }
        return null;
    }

    // 验证红黑树性质（调试用）
    public boolean validate() {
        if (root.isRed) return false;
        return validateNode(root) != -1;
    }

    private int validateNode(RBTreeNode<K, V> node) {
        if (node == NIL) return 1;
        if (node.isRed && node.parent.isRed) return -1; // 连续红节点
        int left = validateNode(node.left);
        int right = validateNode(node.right);
        if (left == -1 || right == -1 || left != right) return -1;
        return left + (node.isRed ? 0 : 1);
    }

复杂度分析

红黑树通过牺牲绝对平衡换取更少的旋转次数，在最坏情况下仍能保证对数级别的操作效率，是工程实践中最高效的自平衡树结构之一。