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

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，它通过在每次插入和删除后执行颜色调整和旋转操作，确保树的高度始终维持在 O(log n) 级别。这一特性使其成为实现高效关联容器（如 Java 的 TreeMap 和 TreeSet）的核心数据结构。本文将用 Java 从零实现一个完整的红黑树，深入讲解左旋、右旋等核心旋转操作，以及插入修复中六种情况的分类处理策略。

一、为什么需要红黑树

普通二叉搜索树（BST）在最坏情况下（如按序插入）会退化为一条链表，导致查找、插入、删除的时间复杂度从 O(log n) 恶化到 O(n)。平衡二叉树通过约束树的结构来解决这一问题。

红黑树的平衡条件比 AVL 树更宽松，这意味着它在频繁插入和删除的场景下，旋转次数更少、常数因子更优。Java 的 java.util.TreeMap 正是基于红黑树实现。

二、红黑树的五条基本性质

一棵合法的红黑树必须同时满足以下五条性质：

1. 节点颜色性质：每个节点要么是红色，要么是黑色。
2. 根节点性质：根节点始终是黑色。
3. 叶子节点性质：所有叶子节点（NIL 空节点）都是黑色。
4. 红色节点性质：如果一个节点是红色的，则它的两个子节点都必须是黑色的（即不存在两个相邻的红色节点）。
5. 黑高性质：从任一节点到其每个叶子节点的所有简单路径上，包含相同数目的黑色节点（该数目称为”黑高”）。

关键推论：由性质 4 和性质 5 可推知，红黑树的最长路径（红黑交替）不会超过最短路径（全黑）的两倍，因此树高始终被限制在 2log(n+1) 以内。

三、节点定义与树结构

3.1 节点类设计

红黑树的节点除了存储键值对外，还需要维护指向父节点、左子节点、右子节点的引用，以及节点的颜色。

/**
 * 红黑树节点
 * 每个节点包含：键、值、颜色、父节点引用、左右子节点引用
 * @param <K> 键类型，需实现Comparable接口
 * @param <V> 值类型
 */
class RBNode<K extends Comparable<K>, V> {
    K key;
    V value;
    boolean isRed;      // true=红色, false=黑色
    RBNode<K, V> left;
    RBNode<K, V> right;
    RBNode<K, V> parent;

    RBNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.isRed = true;  // 新插入节点默认为红色
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

3.2 红黑树类框架

/**
 * 红黑树核心实现
 * 支持插入、查找、中序遍历操作
 * 插入后自动执行平衡修复，维持红黑树五条性质
 */
public class RedBlackTree<K extends Comparable<K>, V> {

    private RBNode<K, V> root;      // 根节点
    private int size;               // 节点数量

    // 空节点哨兵（所有叶子指向此节点，简化空节点判断）
    private final RBNode<K, V> NIL;

    public RedBlackTree() {
        NIL = new RBNode<>(null, null);
        NIL.isRed = false;  // NIL节点为黑色
        root = NIL;
        size = 0;
    }
}

四、核心旋转操作

旋转是红黑树维持平衡的基础操作，分为左旋和右旋。旋转操作不会改变二叉搜索树的中序遍历结果，但能改变树的结构，降低高度。

4.1 左旋（Left Rotation）

左旋以某个节点 x 为支点，将其右子节点 y 提升为子树的新根，x 下降为 y 的左子节点。

/**
 * 左旋操作
 * 前提：x 的右子节点 y 不为 NIL
 * 效果：将 y 提升为子树根，x 成为 y 的左孩子
 *
 *       x                 y
 *      / \              /   \
 *     a   y    ==>     x     c
 *        / \          / \
 *       b   c        a   b
 */
private void leftRotate(RBNode<K, V> x) {
    RBNode<K, V> y = x.right;

    // 步骤1：将 y 的左子树 b 变为 x 的右子树
    x.right = y.left;
    if (y.left != NIL) {
        y.left.parent = x;
    }

    // 步骤2：将 y 的父节点设为 x 的父节点
    y.parent = x.parent;
    if (x.parent == NIL) {
        root = y;           // x 是根节点，更新根
    } else if (x == x.parent.left) {
        x.parent.left = y;  // x 是左孩子
    } else {
        x.parent.right = y; // x 是右孩子
    }

    // 步骤3：将 x 作为 y 的左孩子
    y.left = x;
    x.parent = y;
}

4.2 右旋（Right Rotation）

右旋是左旋的镜像操作，以某个节点 y 为支点，将其左子节点 x 提升为子树的新根。

/**
 * 右旋操作
 * 前提：y 的左子节点 x 不为 NIL
 * 效果：将 x 提升为子树根，y 成为 x 的右孩子
 *
 *         y               x
 *        / \            /   \
 *       x   c   ==>    a     y
 *      / \                  / \
 *     a   b                b   c
 */
private void rightRotate(RBNode<K, V> y) {
    RBNode<K, V> x = y.left;

    // 步骤1：将 x 的右子树 b 变为 y 的左子树
    y.left = x.right;
    if (x.right != NIL) {
        x.right.parent = y;
    }

    // 步骤2：将 x 的父节点设为 y 的父节点
    x.parent = y.parent;
    if (y.parent == NIL) {
        root = x;
    } else if (y == y.parent.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }

    // 步骤3：将 y 作为 x 的右孩子
    x.right = y;
    y.parent = x;
}

五、插入操作与修复

5.1 标准BST插入

首先按照普通二叉搜索树的规则插入新节点，新节点初始颜色设为红色（设为红色可以在不违反黑高性质的前提下插入，仅需处理可能出现的相邻红节点问题）。

/**
 * 对外提供的插入接口
 * @param key 键
 * @param value 值
 */
public void insert(K key, V value) {
    RBNode<K, V> newNode = new RBNode<>(key, value);
    newNode.left = NIL;
    newNode.right = NIL;

    // 标准BST插入
    RBNode<K, V> parent = NIL;
    RBNode<K, V> current = root;

    while (current != NIL) {
        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;
    if (parent == NIL) {
        root = newNode;     // 树为空，新节点成为根
    } else if (key.compareTo(parent.key) < 0) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }

    size++;

    // 插入后执行修复，维持红黑树性质
    fixInsert(newNode);
}

5.2 插入修复（fixInsert）

插入新红节点后，唯一可能违反的性质是性质4（父节点和子节点不能同为红色）。修复过程从当前节点开始，向上递归处理。

根据父节点是祖父节点的左孩子还是右孩子，分为两大类，每类有3种情况，共6种。以下以父节点是祖父节点左孩子为例：

情况1：叔节点为红色
– 将父节点和叔节点变为黑色
– 将祖父节点变为红色
– 将当前节点上移为祖父节点，继续检查

情况2：叔节点为黑色，当前节点是右孩子
– 对父节点执行左旋，转换为情况3

情况3：叔节点为黑色，当前节点是左孩子
– 将父节点变为黑色，祖父节点变为红色
– 对祖父节点执行右旋

/**
 * 插入修复操作
 * 目标：修复因插入红节点可能导致的相邻红节点冲突
 * 核心策略：通过变色和旋转，将冲突向上转移或就地消除
 */
private void fixInsert(RBNode<K, V> node) {
    // 当父节点为红色时需要修复（根节点的父节点是NIL，为黑色）
    while (node.parent.isRed) {
        if (node.parent == node.parent.parent.left) {
            // ========== 父节点是祖父节点的左孩子 ==========
            RBNode<K, V> uncle = node.parent.parent.right;

            if (uncle.isRed) {
                // ---- 情况1：叔节点为红色 ----
                // 策略：父、叔变黑，祖父变红，冲突上移到祖父
                node.parent.isRed = false;
                uncle.isRed = false;
                node.parent.parent.isRed = true;
                node = node.parent.parent;  // 继续检查祖父
            } else {
                // 叔节点为黑色
                if (node == node.parent.right) {
                    // ---- 情况2：当前节点是右孩子 ----
                    // 策略：对父节点左旋，转换为情况3
                    node = node.parent;
                    leftRotate(node);
                }
                // ---- 情况3：当前节点是左孩子 ----
                // 策略：父变黑，祖父变红，对祖父右旋
                node.parent.isRed = false;
                node.parent.parent.isRed = true;
                rightRotate(node.parent.parent);
            }
        } else {
            // ========== 父节点是祖父节点的右孩子（镜像对称） ==========
            RBNode<K, V> uncle = node.parent.parent.left;

            if (uncle.isRed) {
                // 情况1（镜像）：叔节点为红色
                node.parent.isRed = false;
                uncle.isRed = false;
                node.parent.parent.isRed = true;
                node = node.parent.parent;
            } else {
                // 叔节点为黑色
                if (node == node.parent.left) {
                    // 情况2（镜像）：当前节点是左孩子
                    node = node.parent;
                    rightRotate(node);
                }
                // 情况3（镜像）：当前节点是右孩子
                node.parent.isRed = false;
                node.parent.parent.isRed = true;
                leftRotate(node.parent.parent);
            }
        }
    }

    // 确保根节点始终为黑色（性质2）
    root.isRed = false;
}

六、查找与中序遍历

/**
 * 根据键查找对应的值
 * @param key 目标键
 * @return 值，不存在返回null
 */
public V search(K key) {
    RBNode<K, V> current = root;
    while (current != NIL) {
        int cmp = key.compareTo(current.key);
        if (cmp == 0) {
            return current.value;
        } else if (cmp < 0) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return null;
}

/**
 * 中序遍历：按键的升序输出
 * 二叉搜索树的中序遍历天然有序
 */
public void inOrderTraversal() {
    System.out.print("中序遍历结果: ");
    inOrderHelper(root);
    System.out.println();
}

private void inOrderHelper(RBNode<K, V> node) {
    if (node == NIL) return;
    inOrderHelper(node.left);
    String color = node.isRed ? "红" : "黑";
    System.out.print(node.key + "(" + color + ") ");
    inOrderHelper(node.right);
}

七、完整Java代码

以下是可直接编译运行的完整红黑树实现：

import java.util.ArrayList;
import java.util.List;

/**
 * 红黑树完整实现（Java）
 * 支持：插入、查找、中序遍历
 * 自动维持平衡，保证 O(log n) 操作效率
 */
public class RedBlackTree<K extends Comparable<K>, V> {

    // ==================== 节点定义 ====================
    static class RBNode<K extends Comparable<K>, V> {
        K key;
        V value;
        boolean isRed;
        RBNode<K, V> left, right, parent;

        RBNode(K key, V value) {
            this.key = key;
            this.value = value;
            this.isRed = true;
        }
    }

    // ==================== 成员变量 ====================
    private RBNode<K, V> root;
    private final RBNode<K, V> NIL;
    private int size;

    public RedBlackTree() {
        NIL = new RBNode<>(null, null);
        NIL.isRed = false;
        root = NIL;
        size = 0;
    }

    // ==================== 旋转操作 ====================
    private void leftRotate(RBNode<K, V> x) {
        RBNode<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;
    }

    private void rightRotate(RBNode<K, V> y) {
        RBNode<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.left) y.parent.left = x;
        else y.parent.right = x;
        x.right = y;
        y.parent = x;
    }

    // ==================== 插入与修复 ====================
    public void insert(K key, V value) {
        RBNode<K, V> z = new RBNode<>(key, value);
        z.left = NIL; z.right = NIL;

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

        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;

        size++;
        fixInsert(z);
    }

    private void fixInsert(RBNode<K, V> z) {
        while (z.parent.isRed) {
            if (z.parent == z.parent.parent.left) {
                RBNode<K, V> u = z.parent.parent.right;
                if (u.isRed) {
                    z.parent.isRed = false;
                    u.isRed = false;
                    z.parent.parent.isRed = true;
                    z = z.parent.parent;
                } else {
                    if (z == z.parent.right) {
                        z = z.parent;
                        leftRotate(z);
                    }
                    z.parent.isRed = false;
                    z.parent.parent.isRed = true;
                    rightRotate(z.parent.parent);
                }
            } else {
                RBNode<K, V> u = z.parent.parent.left;
                if (u.isRed) {
                    z.parent.isRed = false;
                    u.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) {
        RBNode<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 contains(K key) {
        return search(key) != null;
    }

    public int size() {
        return size;
    }

    // ==================== 遍历与可视化 ====================
    public void inOrderTraversal() {
        System.out.print("中序遍历: ");
        inOrder(root);
        System.out.println();
    }

    private void inOrder(RBNode<K, V> node) {
        if (node == NIL) return;
        inOrder(node.left);
        System.out.printf("%s(%s) ", node.key, node.isRed ? "R" : "B");
        inOrder(node.right);
    }

    /**
     * 获取树的黑高（从根到任意叶子路径上的黑色节点数）
     * 用于验证红黑树的性质5
     */
    public int blackHeight() {
        return blackHeight(root);
    }

    private int blackHeight(RBNode<K, V> node) {
        if (node == NIL) return 0;
        int leftBH = blackHeight(node.left);
        int rightBH = blackHeight(node.right);
        if (leftBH != rightBH) {
            throw new IllegalStateException("黑高不一致，红黑树性质被破坏！");
        }
        return leftBH + (node.isRed ? 0 : 1);
    }

    /**
     * 打印树的层级结构（调试用）
     */
    public void printTree() {
        System.out.println("=== 红黑树结构 ===");
        List<RBNode<K, V>> current = new ArrayList<>();
        if (root != NIL) current.add(root);
        int level = 0;
        while (!current.isEmpty()) {
            System.out.print("Level " + level + ": ");
            List<RBNode<K, V>> next = new ArrayList<>();
            for (RBNode<K, V> node : current) {
                String color = node.isRed ? "R" : "B";
                System.out.printf("[%s:%s] ", node.key, color);
                if (node.left != NIL) next.add(node.left);
                if (node.right != NIL) next.add(node.right);
            }
            System.out.println();
            current = next;
            level++;
        }
        System.out.println("黑高: " + blackHeight());
    }

    // ==================== 主程序：演示 ====================
    public static void main(String[] args) {
        RedBlackTree<Integer, String> tree = new RedBlackTree<>();

        System.out.println("=== 红黑树插入演示 ===\n");

        // 按序插入：极易导致普通BST退化的场景
        int[] keys = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};

        for (int key : keys) {
            System.out.println("插入: " + key);
            tree.insert(key, "Value-" + key);
            tree.inOrderTraversal();
        }

        System.out.println("\n=== 最终树结构 ===");
        tree.printTree();

        System.out.println("\n=== 查找测试 ===");
        System.out.println("查找 25: " + tree.search(25));
        System.out.println("查找 99: " + tree.search(99));
        System.out.println("树大小: " + tree.size());

        System.out.println("\n=== 性质验证 ===");
        System.out.println("黑高一致性: " + tree.blackHeight() + " (已通过验证)");
    }
}

八、复杂度分析

九、总结

本文系统讲解了红黑树的五大性质，深入剖析了左旋、右旋两种核心旋转操作，并完整推导了插入修复的六种情况分类处理策略。通过可直接编译运行的 Java 代码，读者可以观察红黑树在顺序插入数据时如何通过自动旋转和变色维持平衡，避免退化为链表。

红黑树的设计哲学体现了算法领域中”适度平衡换取更高效率”的经典权衡：相比 AVL 树的严格平衡，红黑树的弱平衡策略用更少旋转次数换来了更优的写操作性能。理解红黑树的实现原理，是掌握 Java 集合框架（TreeMap、TreeSet）以及数据库索引（B+树亦基于类似思想）的重要基石。