JAVA：红黑树应用的技术指南

🌳 1、简述

红黑树是一种自平衡二叉查找树（Self-Balancing Binary Search Tree），被广泛应用于操作系统调度、Java集合、数据库索引等核心模块中。本文将从 基本原理 入手，结合 实际应用场景与代码实例，带你全面理解红黑树的精髓。

代码样例：https://gitee.com/lhdxhl/algorithm-example.git

📘 2、什么是红黑树？

红黑树是一种特殊的二叉查找树（BST），其核心目的是通过维护“颜色约束”来实现平衡，从而提高插入、查找和删除操作的效率。

红黑树的每个节点除了值和左右指针外，还会包含一个颜色字段（红或 黑）。

🎯 红黑树的五大性质

🔹 每个节点不是红色就是黑色。
🔹 根节点是黑色。
🔹 所有叶子节点（NIL）都是黑色的（虚拟叶子节点）。
🔹 若一个节点是红色，则其子节点必须是黑色（红色节点不能相邻）。
🔹 从任一节点到其叶子节点的所有路径上，黑色节点数量相同。

✅ 这些性质共同确保了树的“近似平衡”，从而使红黑树操作的时间复杂度保持在：

🔹 查找：O(log n)
🔹 插入：O(log n)
🔹 删除：O(log n)

🔧 3、红黑树的操作（核心逻辑）

📥 插入操作流程

🔹 插入节点为红色，作为 BST 插入。
🔹 若父节点为黑色，插入完成。
🔹 若父节点为红色，需通过旋转（左旋/右旋）+变色保持平衡。
🔹 最终保持根节点为黑色。

📤 删除操作流程

删除较复杂，需要考虑：
🔹 替代节点颜色是否影响黑平衡；
🔹 是否需要旋转或变色修复结构；
🔹 若删除的是黑节点，需额外修复。

🧪 3、实践样例

用 Java 手写简化版红黑树：

public class RedBlackTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        K key;
        V value;
        Node left, right;
        boolean color;

        Node(K key, V value, boolean color) {
            this.key = key;
            this.value = value;
            this.color = color;
        }
    }

    private Node root;

    // 判断节点是否为红色
    private boolean isRed(Node node) {
        return node != null && node.color == RED;
    }

    // 左旋
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        return x;
    }

    // 右旋
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        return x;
    }

    // 颜色翻转
    private void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        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) return new Node(key, value, RED);

        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, value);
        else if (cmp > 0) h.right = put(h.right, key, value);
        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 x = root;
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0) x = x.left;
            else if (cmp > 0) x = x.right;
            else return x.value;
        }
        return null;
    }
}

下面是基于上面实现的 RedBlackTree 类的使用样例，帮助你理解红黑树在 Java 中的基本操作与实际应用场景：

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

        // 插入元素
        tree.put(10, "十");
        tree.put(5, "五");
        tree.put(15, "十五");
        tree.put(1, "一");
        tree.put(7, "七");

        // 查询元素
        System.out.println("key=7 -> " + tree.get(7)); // 输出: 七
        System.out.println("key=10 -> " + tree.get(10)); // 输出: 十
        System.out.println("key=20 -> " + tree.get(20)); // 输出: null（不存在）
    }
}

💡 4、应用场景

🔍 红黑树 vs 其它平衡树对比

🧭 5、总结

红黑树的最大优点就是在保持结构平衡的同时，又能保证高效的增删查性能，是大规模数据结构的核心基石。

✨ 学完你可以掌握：

🔹 红黑树的原理与五大性质
🔹 插入操作过程中的旋转与变色
🔹 实际代码实现简化版红黑树
🔹 常见业务中红黑树的落地应用

📂 附：可选扩展方向

🔹 实现红黑树删除操作
🔹 结合 java.util.TreeMap 调试源码
🔹 使用红黑树管理区间（如IP段、时间段）