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

算法概述

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，由Rudolf Bayer于1972年发明。它通过在每个节点上增加一个存储位表示节点的颜色（红或黑），并确保从根到叶子的最长路径不会超过最短路径的两倍，从而保证树的高度始终为O(log n)。

红黑树的五条性质

1. 每个节点要么是红色，要么是黑色
2. 根节点是黑色
3. 所有叶子节点（NIL）都是黑色
4. 如果一个节点是红色，则它的两个子节点都是黑色（红色节点不能相邻）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（黑高相同）

核心操作：旋转

旋转是维持红黑树平衡的核心操作，分为左旋和右旋。

左旋（Left Rotation）

以某个节点为支点，将其右子节点提升为新的父节点，原节点成为新父节点的左子节点。

右旋（Right Rotation）

以某个节点为支点，将其左子节点提升为新的父节点，原节点成为新父节点的右子节点。

Java完整实现

import java.util.Comparator;

/**
 * 红黑树完整Java实现
 * 支持插入、删除、查找操作，保证O(log n)时间复杂度
 */
public class RedBlackTree<K extends Comparable<K>, V> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;
    private int size;

    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; // 新插入节点默认为红色
            this.left = this.right = this.parent = null;
        }
    }

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

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

    /**
     * 左旋操作
     * @param h 旋转支点
     * @return 新的子树根节点
     */
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        if (x.left != null) {
            x.left.parent = h;
        }
        x.parent = h.parent;
        if (h.parent == null) {
            root = x;
        } else if (h == h.parent.left) {
            h.parent.left = x;
        } else {
            h.parent.right = x;
        }
        x.left = h;
        h.parent = x;
        x.color = h.color;
        h.color = RED;
        return x;
    }

    /**
     * 右旋操作
     * @param h 旋转支点
     * @return 新的子树根节点
     */
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        if (x.right != null) {
            x.right.parent = h;
        }
        x.parent = h.parent;
        if (h.parent == null) {
            root = x;
        } else if (h == h.parent.right) {
            h.parent.right = x;
        } else {
            h.parent.left = x;
        }
        x.right = h;
        h.parent = x;
        x.color = h.color;
        h.color = RED;
        return x;
    }

    /**
     * 颜色翻转：将父节点变红，两个子节点变黑
     */
    private void flipColors(Node h) {
        h.color = RED;
        if (h.left != null) h.left.color = BLACK;
        if (h.right != null) h.right.color = BLACK;
    }

    /**
     * 公共插入方法
     */
    public void put(K key, V value) {
        root = put(root, key, value);
        root.color = BLACK; // 根节点始终为黑色
    }

    /**
     * 递归插入并修复红黑树性质
     */
    private Node put(Node h, K key, V value) {
        if (h == null) {
            size++;
            return new Node(key, value);
        }

        int cmp = key.compareTo(h.key);
        if (cmp < 0) {
            h.left = put(h.left, key, value);
            h.left.parent = h;
        } else if (cmp > 0) {
            h.right = put(h.right, key, value);
            h.right.parent = h;
        } else {
            h.value = value; // 更新已有键的值
        }

        // 修复红黑树性质：右红则左旋，左红且左左红则右旋，左右皆红则翻转颜色
        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);

        return h;
    }

    /**
     * 查找键对应的值
     */
    public V get(K key) {
        Node node = get(root, key);
        return node == null ? null : node.value;
    }

    private Node get(Node h, K key) {
        while (h != null) {
            int cmp = key.compareTo(h.key);
            if (cmp < 0) h = h.left;
            else if (cmp > 0) h = h.right;
            else return h;
        }
        return null;
    }

    /**
     * 中序遍历输出有序序列
     */
    public void inOrderTraversal() {
        inOrder(root);
        System.out.println();
    }

    private void inOrder(Node h) {
        if (h == null) return;
        inOrder(h.left);
        System.out.print(h.key + " ");
        inOrder(h.right);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {
        RedBlackTree<Integer, String> tree = new RedBlackTree<>();

        // 测试插入操作
        int[] keys = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35};
        for (int key : keys) {
            tree.put(key, "value_" + key);
        }

        System.out.println("中序遍历结果（应有序）：");
        tree.inOrderTraversal();

        System.out.println("查找键40的值：" + tree.get(40));
        System.out.println("查找键100的值：" + tree.get(100));
        System.out.println("树的大小：" + tree.size());
    }
}

插入修复策略详解

当红黑树插入新节点时，新节点默认为红色。如果父节点也是红色，则违反了性质4，需要进行修复。修复分三种情况：

情况1：叔叔节点是红色

将父节点和叔叔节点变为黑色，祖父节点变为红色，然后将祖父节点作为新的当前节点向上递归修复。

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

对父节点进行左旋，将情况转化为情况3。

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

对祖父节点进行右旋，交换父节点和祖父节点的颜色。

复杂度分析

红黑树的高度始终不超过2log₂(n+1)，因此所有操作都能在O(log n)时间内完成。

应用场景

• Java的TreeMap和TreeSet底层使用红黑树实现
• Linux内核的CFS调度器使用红黑树管理进程
• C++ STL的map和set通常使用红黑树实现
• 数据库索引结构中广泛应用

总结

红黑树通过巧妙的颜色标记和旋转操作，在保持二叉搜索树结构的同时实现了自平衡。相比于AVL树的严格平衡，红黑树的平衡条件更宽松，插入和删除操作所需的旋转次数更少，因此在频繁修改的场景下性能更优。