深入浅出红黑树：如何手写红黑树（基于TreeMap，算法导论的实现）

lifallen

2740人浏览 · 2025-06-09 16:32:04

lifallen · 2025-06-09 16:32:04 发布

红黑树是一种特殊的二叉搜索树，但它比普通的二叉搜索树更“聪明”。它通过一套巧妙的规则，在数据不断增删的过程中，始终能保持自身的“平衡”，从而确保了高效的查找、插入和删除操作，其时间复杂度都能稳定在 O(log n) 水平。

那么，红黑树是如何做到这一点的呢？这就要归功于它的五个核心性质：

每个节点要么是红色，要么是黑色。
根节点是黑色。
所有叶子节点（NIL节点，空节点）都是黑色。
每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
从任一节点到其每个叶子的所有简单路径都包含相同数量的黑色节点。

因为红色节点的不能相邻，所以任何一条路径黑色节点至少是总数的一半，任何一条L长的路径，黑色至少占 L/2。

假设红黑树高 h，因此黑色节点至少 h/2。

又因为每条路径的黑色节点都是一样的，因此至少有 h/2 的满二叉树（因为每条路径至少 h/2 的黑色节点），所以红黑树一定是 h = log n 的高度。

一颗 log n 高度的二叉搜索树，查询、插入和删除复杂度自然是 log n。

TreeMap 的整体结构与红黑树实现

TreeMap 是 Java 集合框架中基于红黑树实现的有序 Map。它的核心数据结构是一个红黑树，每个节点存储键值对，并保证树的平衡和有序性。实现基于算法导论。

主要内部类和字段

Entry<K,V>：TreeMap 的核心节点类，每个 Entry 代表红黑树的一个节点，包含了 key、value、left/right/parent、color（颜色标记，true 为红色，false 为黑色）。【Tree Map实现红黑树没有显式的NIL哨兵，但是逻辑上null可以视为黑色】

private static <K,V> boolean colorOf(Entry<K,V> p) {
   return (p == null ? BLACK : p.color);
}

root：指向红黑树的根节点。
size：记录元素数量。

Entry 结构

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; // 默认黑色
    // ...
}

TreeMap 通过 Entry<K,V> 节点类实现红黑树，每个节点有颜色、父子指针。
插入操作后用 fixAfterInsertion 保证平衡，核心是“红红冲突”修正和旋转。相当于双红节向上移动，如果到根节点还是双红，直接染成黑色，黑高加1。
删除操作后用 fixAfterDeletion 保证平衡，核心是“黑高不平衡”修正和旋转。相当于双黑节点上移，如果到根节点还是双黑，直接去掉一重黑，黑高减一。

旋转操作

左旋：将节点 p 的右子节点 r 移动到 p 的位置，并将 p 作为 r 的左子节点。

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

右旋：将节点 p 的左子节点 l 移动到 p 的位置，并将 p 作为 l 的右子节点。

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

插入操作（put）

插入分为两步：

二叉查找树方式定位插入点。
插入后执行红黑树的自平衡操作（修正颜色和结构）。

定位插入点

沿根节点查找，比较 key 的大小，找到合适的叶子位置插入新节点。
新节点初始为红色节点。

插入后的修正（fixAfterInsertion）源码核心方法如下：

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;
    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) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // 与上面对称（左右互换）
        }
    }
    root.color = BLACK;
}

初始着色：新插入的节点 x 被着色为红色。

循环修正：当节点 x 不是根节点且它的父节点是红色时，进入循环进行修正。

while (x != null && x != root && x.parent.color == RED) {

父节点是红色，祖先节点一定是黑色

情况判断：根据 x 的父节点是其祖父节点的左子节点还是右子节点，分为两种情况处理。

父节点是左子节点：
```
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
    Entry<K,V> y = rightOf(parentOf(parentOf(x)));
```
- 叔叔节点是红色：将父节点和叔叔节点着色为黑色，祖父节点着色为红色，并将 x 更新为祖父节点（递归思想），继续循环。
```
if (colorOf(y) == RED) {
    setColor(parentOf(x), BLACK);
    setColor(y, BLACK);
    setColor(parentOf(parentOf(x)), RED);
    x = parentOf(parentOf(x));
}
```
- 叔叔节点是黑色：根据 x 是父节点的左子节点还是右子节点，进行不同的处理。
  - x 是右子节点：对 x 的父节点进行左旋，将 x 更新为它的父节点。（经过这一步，x一定是左子节点，进入后面一种情况）
```
if (x == rightOf(parentOf(x))) {
    x = parentOf(x);
    rotateLeft(x);
}
```
  - x 是左子节点：对 x 的祖父节点进行右旋，并交换父节点和祖父节点的颜色。
    这一步虽然没有重新赋值 x，但是因为对祖父右旋，x离根节点距离减少了1
```
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
```

父节点是右子节点：与父节点是左子节点的情况对称处理。

else {
    Entry<K,V> y = leftOf(parentOf(parentOf(x)));
    if (colorOf(y) == RED) {
        setColor(parentOf(x), BLACK);
        setColor(y, BLACK);
        setColor(parentOf(parentOf(x)), RED);
        x = parentOf(parentOf(x));
    } else {
        if (x == leftOf(parentOf(x))) {
            x = parentOf(x);
            rotateRight(x);
        }
        setColor(parentOf(x), BLACK);
        setColor(parentOf(parentOf(x)), RED);
        rotateLeft(parentOf(parentOf(x)));
    }
}

根节点着色：循环结束后，将根节点着色为黑色。

删除操作（remove）

删除比插入复杂，分为删除节点和修正红黑树结构两步。

删除节点

若节点有两个子节点，用后继节点（右子树最小节点）替换，然后删除后继节点（后继最多只有一个子节点）。
若节点有一个或零个子节点，直接用子节点替换。

deleteEntry

这个函数的实现有自身的考虑，不是必然逻辑

private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

successor的逻辑只有在有右孩子的时候，后继才是只有一个节点，这就是这里判断做的

        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

做了这一步，p 只有一个子节点，因为 s 的值被保留了，所以现在要删除 p = s

如果有一个孩子，这里进入的时候，p已经被删除了，颜色是需要补偿的

Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        }

没孩子是类似的

successor

找到的是右子树的最左节点。

如果没有右孩子，会找到最近祖先p，使得 t 是 p 的左子树节点，因此这个时候 p 可能有两个子节点

    static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

删除后的修正（fixAfterDeletion）

源码核心方法如下：

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else {
            // 左右对称的处理
        }
    }
    setColor(x, BLACK);
}

关键点说明

删除黑色节点可能导致红黑树黑高不一致，通过兄弟节点的颜色和结构旋转、变色修正。
主要有四种情况，代码参考算法导论的实现，这里与红黑树的标准修正操作对应。

最透彻的分析删除后修正

当删除一个黑色节点时，会破坏黑高平衡，需要进行修复。

注意：在进入函数之后，x是不需要被删除的【见deleteEntry中的讨论】，只是从根到 x 这条路径路径少了一个黑色，所以可以把 x 视为外面多了一层黑的节点，如果x是红色，显然把x赋值为黑色就结束了，如果x是根，直接丢掉这个多出来的黑就行。

理解这一点才能明白后面的条件判断和赋值。

主循环条件

while (x != root && colorOf(x) == BLACK)

x是待修复的节点（通常是被删除节点的替代节点）
只有当x是黑色且不是根节点时才需要修复

修复策略（以左孩子为例，x == leftOf(parentOf(x)) ）

Entry<K,V> sib = rightOf(parentOf(x));

情况1：兄弟节点是红色（此时兄弟节点的孩子一定是黑色，null节点被视为黑色）

左旋x的父节点，使得 sib 的左孩子变为 x 的兄弟

if (colorOf(sib) == RED) {
    setColor(sib, BLACK);      
    setColor(parentOf(x), RED);
    rotateLeft(parentOf(x));    // 左旋父节点
    sib = rightOf(parentOf(x)); // 更新兄弟节点
}

目的：将红色兄弟转换为黑色兄弟的情况

情况2：兄弟节点是黑色，且兄弟的两个子节点都是黑色

if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
    setColor(sib, RED);  // 兄弟变红
    x = parentOf(x);     // 向上递归
}

通过将兄弟变红，让原本是 root->x 需要多一重黑，现在 root->sib 也要多一重黑，因此等价于 root->p 要多一层黑，因此 x = parent(x) 向上传递。

情况3：兄弟是黑色，兄弟的右子节点是黑色，左子节点是红色

if (colorOf(rightOf(sib)) == BLACK) {
    setColor(leftOf(sib), BLACK); // 兄弟左子节点变黑
    setColor(sib, RED);           // 兄弟变红
    rotateRight(sib);             // 右旋兄弟
    sib = rightOf(parentOf(x));   // 更新兄弟节点
}

目的：转换为情况4【sib的左孩子原来的左孩子一定是黑色，旋转后，原来的sib变为红色，是一个右子节点的红色】

情况4：兄弟是黑色，兄弟的右子节点是红色

setColor(sib, colorOf(parentOf(x)));  // 兄弟继承父节点颜色
setColor(parentOf(x), BLACK);         // 父节点变黑
setColor(rightOf(sib), BLACK);        // 兄弟右子节点变黑
rotateLeft(parentOf(x));              // 左旋父节点
x = root;                             // 修复完成，退出循环

这里实际做的是

交换 sib 和父节点p 的颜色，因此 root->sib 黑高不变。
sib的右孩子（原本是红色，情况4的条件），变为黑色，因此 root->sib.right需要删除一层黑
左旋父节点，
1. 原本 root->p->x 的路径变为 root->sib->p->x，因此这条路径被补偿了黑色（注意多了sib的颜色，sib原来颜色是黑的）；
2. 另一条路径 root->p->sib，变为 root->sib->sib.right 颜色上等价于 root->原来的p->black，因此黑高不变
恢复黑高平衡，x=root直接跳出循环

循环外：setColor(x, BLACK)确保最终节点为黑色。（容易证明，不管什么情况，这一赋值不会破坏红黑树的性质，而且能够修复root变为红色的情况，因为这一点，在循环内部没必要考虑root是不是变为了红色）

乐奇 Rokid 开放社区

更多推荐

FPC与机器人的双向赋能，解锁智能装备进化新势能

如果说AI算法、算力芯片是智能眼镜的“智慧大脑”，光学模组是智能眼镜的“视觉窗口”，那么FPC就是贯穿整机、连接所有功能模块的“柔性神经脉络”。方寸之间的柔性突破，破解了智能眼镜“轻薄形态”与“全能功能”的核心矛盾，是穿戴智能设备实现形态革新、体验升级的底层核心。未来，随着AR沉浸式技术、AI大模型、穿戴硬件技术的持续进化，智能眼镜将朝着更轻薄、更智能、更多场景、更高稳定性的方向持续迭代，对高端精

乐奇 Rokid 开放社区

AI眼镜里面有晶振吗？智能眼镜的时钟系统

乐奇 Rokid 开放社区

时笺：一个 AIUI 提醒智能体的实现解析

实践下来发现只靠 LLM 是虚的：它会一本正经地算错 dayOffset，偶尔还给你一个用 markdown 代码块包着的 JSON，最气的是不稳定——同一个句子上午答对下午翻车。）一键运行 42 个用例，覆盖：北京时间墙钟/日界、六种意图分类与反误判、相对/绝对/中文数字时刻、7 种排期、升级与错过判定、重复提醒判重与补排、容量上限、持久化 round-trip、脏数据兜底。我想要的是抬头能看见