在数据结构领域，平衡二叉搜索树（BST）是解决 “普通 BST 极端场景退化为链表” 问题的关键。红黑树作为平衡二叉搜索树的经典实现，凭借 “近似平衡” 的特性，将插入、删除、查询的时间复杂度稳定在 O (logn)，成为 Java 集合框架中 TreeMap、TreeSet 的底层核心。本文将从红黑树的基础特性出发，拆解插入与删除的平衡调整逻辑，再结合 Java TreeMap 源码，解析理论到工程实现的落地细节。

一、红黑树的核心定义与特性

红黑树并非 “绝对平衡” 的二叉树，而是通过 5 条核心特性约束节点颜色与结构，间接保证树的高度控制在 2log (n+1) 以内，从而实现高效操作。

1. 红黑树的 5 条核心特性

• 特性 1：每个节点的颜色只能是红色或黑色。
• 特性 2：根节点必须是黑色（避免后续调整时出现 “根节点为红” 的连锁问题）。
• 特性 3：所有 “NIL 节点”（即叶子节点，实际实现中可能省略，用 null 表示）均为黑色。
• 特性 4：若一个节点是红色，则它的两个子节点必须是黑色（禁止 “红节点连续”，避免局部黑高失衡）。
• 特性 5：从任意节点出发，到其所有叶子节点的 “黑色路径长度”（路径中黑色节点的数量，不含当前节点）必须相等（这是保证树近似平衡的关键）。

2. 特性的核心作用

上述特性的本质是 “通过颜色约束控制黑高”：由于红色节点不增加黑高，且禁止连续红节点，树的最大高度不会超过最小高度的 2 倍（最小高度为纯黑树的高度 logn，最大高度为红黑交替的高度 2logn）。这种 “近似平衡” 既避免了 AVL 树 “严格平衡” 带来的高频调整开销，又保证了操作效率。

二、红黑树插入：从 BST 到平衡调整

红黑树的插入流程遵循 “先按 BST 规则插入节点，再通过颜色调整 + 旋转修复平衡” 的逻辑。新节点默认着色为红色（若着色为黑色，会直接破坏特性 5 的黑高平衡，调整成本更高）。

1. 插入的两步核心流程

步骤 1：BST 规则插入新节点

与普通 BST 一致：从根节点出发，比较新节点 key 与当前节点 key 的大小，小于则走左子树，大于则走右子树，直至找到 null 位置插入新节点，并将新节点颜色设为红色。

步骤 2：判断失衡并修复

插入后需检查是否破坏红黑树特性，核心冲突场景是 “新节点（红）的父节点也是红色”（违反特性 4）。此时需根据 “叔叔节点（父节点的兄弟）的颜色” 分 3 种情况调整：

场景分类	叔叔节点颜色	调整策略
Case1	红色	1. 父节点、叔叔节点改为黑色；2. 祖父节点改为红色；3. 将祖父节点作为新节点，递归检查上层平衡
Case2	黑色（父节点为左孩子，新节点为右孩子）	1. 对父节点执行 “左旋”，将新节点与父节点位置互换；2. 转化为 Case3 处理
Case3	黑色（父节点为左孩子，新节点为左孩子）	1. 父节点改为黑色，祖父节点改为红色；2. 对祖父节点执行 “右旋”，修复树结构

注：若父节点为右孩子，逻辑与上述对称，只需将 “左旋” 改为 “右旋”，“左孩子” 改为 “右孩子” 即可。

2. 调整案例：Case3 场景示例

假设插入前树结构满足红黑特性，新节点（红）的父节点（红）是祖父节点的左孩子，叔叔节点（黑）：

1. 将父节点设为黑色，祖父节点设为红色；
2. 对祖父节点执行右旋：祖父节点的左孩子（原父节点）成为新的父节点，原祖父节点成为其右孩子；
3. 调整后，红节点不再连续，黑高平衡也未被破坏，特性 4 和特性 5 均恢复。

三、红黑树删除：复杂场景下的平衡修复

红黑树的删除比插入更复杂，核心原因是 “删除黑色节点可能导致黑高减少”，出现 “双重黑色” 节点（即该节点的黑高贡献需额外叠加 1）。删除流程同样遵循 “BST 删除 + 平衡修复”，但修复需解决 “双重黑色” 的传递与消除。

1. 删除的三步核心流程

步骤 1：BST 规则删除目标节点

与普通 BST 一致，需先找到目标节点，再根据节点子树情况分 3 种情况删除：

• 情况 A：目标节点为叶子节点（无子女），直接删除；
• 情况 B：目标节点有一个子女，用子女替换目标节点后删除；
• 情况 C：目标节点有两个子女，找到 “前驱节点”（左子树最大节点）或 “后继节点”（右子树最小节点）替换目标节点，再删除前驱 / 后继节点（转化为情况 A 或 B）。

步骤 2：标记 “待修复节点”

删除后，若被删除节点是黑色，会导致其所在路径的黑高减少 1，此时需将 “替换被删除节点的节点” 标记为 “双重黑色”（记为x），进入修复流程；若被删除节点是红色，直接删除无需修复（红色节点不影响黑高）。

步骤 3：修复 “双重黑色” 节点

修复的核心是通过 “兄弟节点的颜色” 和 “兄弟节点子女的颜色” 分 4 种场景，消除 “双重黑色”：

场景分类	兄弟节点颜色	兄弟节点子女颜色	调整策略
Case1	红色	任意	1. 兄弟节点改为黑色，父节点改为红色；2. 对父节点执行左旋 / 右旋，将兄弟节点变为新的父节点；3. 重新确定x的兄弟节点，进入其他场景
Case2	黑色	两个子女均为黑色	1. 兄弟节点改为红色；2. 将 “双重黑色” 传递给父节点，更新x为父节点；3. 递归修复父节点
Case3	黑色	兄弟的左子女红、右子女黑（兄弟为右孩子）	1. 兄弟的左子女改为黑色，兄弟改为红色；2. 对兄弟执行右旋，更新兄弟节点；3. 转化为 Case4 处理
Case4	黑色	兄弟的右子女红（兄弟为右孩子）	1. 兄弟节点颜色改为父节点颜色；2. 父节点改为黑色，兄弟的右子女改为黑色；3. 对父节点执行左旋，消除 “双重黑色”

注：若兄弟节点为左孩子，逻辑与上述对称，只需调整旋转方向和子女位置描述。

2. 修复核心：避免黑高失衡

所有调整动作的本质是 “将双重黑色的负担转移给其他节点，或通过旋转重新分配黑色节点”，最终保证特性 5（黑高平衡）不被破坏。例如 Case4 中，通过左旋将兄弟节点的红色子女 “提升”，填补黑高缺口，同时通过颜色调整避免红节点连续。

四、Java TreeMap 源码：红黑树的工程实现

Java 中的 TreeMap 实现了 SortedMap 接口，底层完全基于红黑树，支持 “自然排序”（Key 实现 Comparable 接口）或 “定制排序”（传入 Comparator）。下面从 “节点结构”“核心方法” 两个维度，解析红黑树理论在源码中的落地。

1. 核心数据结构：红黑树节点 Entry

TreeMap 的红黑树节点由内部类Entry<K,V>实现，包含红黑树节点的核心属性：

java

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;          // 键（用于排序）
    V value;        // 值
    Entry<K,V> left; // 左子节点
    Entry<K,V> right;// 右子节点
    Entry<K,V> parent;// 父节点
    boolean color = BLACK; // 颜色，默认黑色（与理论中“新节点红”不同，源码中插入时会动态调整）

    // 构造方法、getter/setter等省略
}

• 颜色定义：源码中用private static final boolean RED = false; private static final boolean BLACK = true;表示，与理论描述一致；
• 父节点引用：为了方便遍历和调整（如旋转、找前驱 / 后继），每个节点都持有父节点引用，这是工程实现中对理论模型的优化。

2. 插入实现：put 方法与 fixAfterInsertion

TreeMap 的put(K key, V value)方法对应红黑树的插入逻辑，核心是 “找到插入位置→插入节点→修复平衡”，其中平衡修复由fixAfterInsertion(Entry<K,V> x)实现。

关键源码片段 1：put 方法的核心逻辑

java

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 1. 若树为空，直接创建根节点（颜色默认黑色，符合特性2）
    if (t == null) {
        root = new Entry<>(key, value, null);
        size = 1;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // 2. 根据比较器找到插入位置（BST插入逻辑）
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) t = t.left;    // 键小，走左子树
            else if (cmp > 0) t = t.right;// 键大，走右子树
            else return t.setValue(value); // 键相等，更新值
        } while (t != null);
    } else {
        // 自然排序，要求Key实现Comparable接口
        // 逻辑与定制排序一致，省略...
    }
    // 3. 创建新节点（默认黑色，插入后会通过fixAfterInsertion改为红色）
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    // 4. 插入后修复红黑树平衡
    fixAfterInsertion(e);
    size++;
    return null;
}

关键源码片段 2：fixAfterInsertion（插入后平衡修复）

该方法完全对应前文 “插入调整” 的 3 种场景，核心逻辑是 “判断父节点颜色→根据叔叔节点颜色执行调整”：

java

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED; // 新节点设为红色，符合理论逻辑
    // 循环条件：x不是根节点，且x的父节点是红色（违反特性4）
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 场景：父节点是祖父节点的左孩子
            Entry<K,V> y = rightOf(parentOf(parentOf(x))); // 叔叔节点
            if (colorOf(y) == RED) {
                // Case1：叔叔节点是红色，执行变色
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x)); // 递归检查祖父节点
            } else {
                if (x == rightOf(parentOf(x))) {
                    // Case2：叔叔节点是黑色，x是右孩子，先左旋
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // Case3：叔叔节点是黑色，x是左孩子，右旋+变色
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // 场景：父节点是祖父节点的右孩子，逻辑与左孩子对称
            // 代码与上述对称，省略...
        }
    }
    root.color = BLACK; // 确保根节点始终是黑色，修复可能的根节点变红问题
}

3. 删除实现：remove 方法与 fixAfterDeletion

TreeMap 的remove(Object key)方法对应红黑树的删除逻辑，核心是 “找到目标节点→BST 规则删除→修复双重黑色”，平衡修复由fixAfterDeletion(Entry<K,V> x)实现。

关键逻辑梳理

1. 找到目标节点：通过getEntry(Object key)方法，根据比较器找到待删除的 Entry；
2. BST 删除：若目标节点有两个子女，先找到后继节点（右子树最小节点），用后继节点替换目标节点，再删除后继节点（转化为单子女或叶子节点删除）；
3. 平衡修复：若被删除节点是黑色，调用fixAfterDeletion(x)修复双重黑色，逻辑与前文 “删除调整” 的 4 种场景完全对应。

关键源码片段：fixAfterDeletion（删除后平衡修复）

该方法的核心是 “判断兄弟节点颜色→处理双重黑色传递与消除”：

java

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            // 场景：x是父节点的左孩子
            Entry<K,V> sib = rightOf(parentOf(x)); // 兄弟节点
            if (colorOf(sib) == RED) {
                // Case1：兄弟节点是红色，先调整为黑色兄弟场景
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
                // Case2：兄弟节点是黑色，且两个子女均为黑色，传递双重黑色
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    // Case3：兄弟节点是黑色，右子女黑、左子女红，先调整为右子女红
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                // Case4：兄弟节点是黑色，右子女红，消除双重黑色
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root; // 修复完成，退出循环
            }
        } else {
            // 场景：x是父节点的右孩子，逻辑与左孩子对称
            // 代码与上述对称，省略...
        }
    }
    setColor(x, BLACK); // 消除双重黑色，将x设为黑色
}

4. 辅助方法：旋转与颜色操作

红黑树的调整依赖 “左旋” 和 “右旋”，TreeMap 源码中通过rotateLeft和rotateRight实现这两个操作，核心是 “调整节点引用关系，保持 BST 特性”。

以rotateLeft（左旋）为例，源码逻辑如下：

java

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right; // p的右子节点（旋转后成为新的父节点）
        p.right = r.left;       // r的左子节点变为p的右子节点
        if (r.left != null) r.left.parent = p; // 更新父节点引用
        r.parent = p.parent;    // r的父节点改为p的原父节点
        if (p.parent == null) root = r;        // 若p是根节点，r成为新根
        else if (p == p.parent.left) p.parent.left = r; // p是左孩子，r接替其位置
        else p.parent.right = r;               // p是右孩子，r接替其位置
        r.left = p;             // p成为r的左子节点
        p.parent = r;           // 更新p的父节点为r
    }
}

右旋逻辑与左旋对称，只需将 “左”“右” 节点位置互换即可。

五、红黑树与 TreeMap 的应用场景

TreeMap 的价值完全依赖红黑树的特性，其应用场景需围绕 “有序性” 和 “高效动态操作” 展开：

1. 有序遍历需求：需按 Key 的自然顺序或定制顺序遍历键值对（如按时间戳排序的日志、按 ID 排序的用户信息），TreeMap 的entrySet()遍历是有序的，而 HashMap 是无序的；
2. 范围查询需求：需快速获取 “Key 在 [min, max] 区间内的所有元素”，TreeMap 提供subMap(K fromKey, K toKey)方法，基于红黑树的 BST 特性，可在 O (logn + k) 时间内完成（k 为区间内元素个数）；
3. 动态排序需求：需频繁插入 / 删除元素，同时保持有序性（如实时排行榜），红黑树的 O (logn) 插入 / 删除效率远高于数组（插入删除需 O (n)）。

六、结语

红黑树的核心是 “用颜色约束换近似平衡”，通过插入 / 删除后的变色与旋转，在 “调整开销” 和 “查询效率” 之间取得最优平衡。而 Java TreeMap 作为红黑树的经典工程实现，不仅严格遵循红黑树理论，还通过 “父节点引用”“默认黑色节点” 等细节优化，提升了代码的可读性与执行效率。

理解红黑树的原理，不仅能帮助我们更合理地选择集合类（如明确 TreeMap 与 HashMap 的适用场景），还能为后续学习更复杂的数据结构（如 B + 树、R 树）打下基础 —— 这些结构的核心思想，本质上都是 “通过规则约束实现平衡，进而保证高效操作”。

为了帮你更直观地理解红黑树的调整过程，要不要我帮你整理一份红黑树插入 / 删除场景的可视化流程图？包含关键场景的节点颜色变化、旋转步骤，可直接用于学习或笔记整理。