0. 引入

Java自带基础类库中的TreeMap也是一个实现了Map接口的类，它同HashMap一样用于存储键值对。与HashMap不一样的是，TreeMap内的数据是有序的，并且其内部是由一棵红黑树来实现的。也因为以上的原因，所以TreeMap的插入查找删除的速度都比HashMap慢，所以TreeMap一般在需要对数据进行排序的时候才会使用到。

1. 二叉查找树

红黑树和AVL树一样也是一种二叉查找树，关于二叉查找树的内容可以看我之前写过的二叉查找树与 AVL 树。我们已经知道，AVL树是通过调节左右子树的高度来控制插入和查找的速度的，红黑树虽然也是一棵二叉查找树，但是和AVL树不一样，它是通过给节点标记上不同的颜色来提高数据的插入和查找速度的。

AVL树为了保持自身的平衡，会频繁的进行旋转操作，而旋转操作是比较耗费时间的。红黑树会尽量的减少旋转操作，所以一般认为红黑树的操作效率会高于AVL树。

2. 红黑树的性质

红黑树的性质如下（摘自维基百科）：

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色（叶子是NIL节点）。
  4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

关于为什么通过这些性质就能使红黑树保证其高效率的证明，可以参考维基百科中的相关页面。

3. Entry<K,V>类

想要购建一颗树，首先需要构建出树中的的每一个节点。每一个节点中所包含的内容应该要合适、能够包含有所有我们需要用到数据即可。Java中是通过Entry<K,V>类来保存红黑树中的每一个节点信息的，具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 通过 bool 类型来保存红色和黑色的状态
private static final boolean RED   = false;
private static final boolean BLACK = true;

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;                  // Key
    V value;                // Value
    Entry<K,V> left;        // 左子节点
    Entry<K,V> right;       // 右子节点
    Entry<K,V> parent;      // 父节点
    boolean color = BLACK;  // 节点颜色默认黑色

    // 初始化一个节点，包含了 key、value 和 parent 三个参数
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

}

4. 红黑树插入一个节点

红黑树插入一个节点和二叉查找树的插入操作是一样的，对二叉查找树插入的过程不太了解可以查看二叉查找树与 AVL 树来进行了解。连接中二叉查找树的插入操作是通过递归来实现的，而TreeMap中是通过迭代来实现，不过其本质都是一样，都是通过和对应节点的值进行大小比较最终把要插入的值插入到合适的位置。

下面就是TreeMap中的插入操作，我省略掉了其中的一些不重要的步骤：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public V put(K key, V value) {
    Entry<K,V> t = root;
    // 如果根节点为空，就插入根节点（根据性质 2，根节点默认为黑色）
    if (t == null) {
        root = new Entry<>(key, value, null);
        return null;
    }
    int cmp; // 记录比较的值
    Entry<K,V> parent; // 记录当前的节点，如果在当前节点下插入了新节点，那么此节点就为新节点的父节点
    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); // 根据 key 的值来循环直到叶子节点
    Entry<K,V> e = new Entry<>(key, value, parent); // 创建新节点，其父节点为当前的叶子节点
    if (cmp < 0)
        parent.left = e; // 如果小于就把该节点作为当前节点左孩子
    else
        parent.right = e; // 如果大于就把该节点作为当前节点右孩子
    fixAfterInsertion(e); // 插入了新节点之后，如果想要保持好红黑树的性质，需要进行红黑树的修复操作（参见第 5 节）
    return null;
}

插入操作很简单，就是根据二叉查找树的性质在进行一个循环之后把节点插入在合适的叶子节点的位置，并把其父节点设置为上一个叶子节点，并且新插入的节点是上一个叶子节点的左（右）子节点。

5. 插入之后红黑树的修复*

红黑树和AVL都是二叉查找树，所以插入操作都是一样的，它们的差别就在于插入之后的修复操作不一样。因为红黑树和AVL的性质不一样，所以修复的方式也不一样。AVL树修复的目的是为了是树的高度降低，而红黑树的修复操作就是根据红黑树的5条性质而进行的。

首先我们会保证新插入的节点的颜色必然为红色，这样会使得情况变得比较简单（如果新插入的节点是黑色，那么必然会违背性质5，会增加修复开销）。当新插入的节点是红色的时候：

  • 如果插入的是根结点，因为原树是空树，此情况只会违反性质2，所以直接把此结点涂为黑色；
  • 如果插入的结点的父结点是黑色，由于此不会违反性质2和性质4，红黑树没有被破坏，所以此时也是什么也不做。

但是，以下三种情况则需要进行修复操作：

  • 插入修复情况1：当前结点的父结点是红色，叔叔结点是红色；
    对策：将当前结点的父结点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，从新的当前结点（即祖父节点）重新开始算法。
  • 插入修复情况2：当前结点的父结点是红色，叔叔结点是黑色，当前结点是其父结点的右子；
    对策：当前结点的父结点做为新的当前结点，以新当前结点为支点左旋。
  • 插入修复情况3：当前结点的父结点是红色，叔叔结点是黑色，当前结点是其父结点的左子；
    对策：父结点变为黑色，祖父结点变为红色，在祖父结点为支点右旋。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// 红黑树性质的修复
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)))) { // 如果 x 的父亲是 x 的祖父的左子节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));  // 那么 x 的叔叔 y 节点就是 x 祖父的右子节点
            if (colorOf(y) == RED) { // 如果叔叔是红色，修复情况 1
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED); // 这一步修改了当前节点的祖父节点的性质，因为其祖父节点的性质变化可能会引入新的影响红黑树性质的因素，所以需要把祖父节点作为新的当前节点来进行一次新的判断，这就是修复的时候需要循环的原因
                x = parentOf(parentOf(x)); // 把祖父节点作为新的当前节点
            } else {
                if (x == rightOf(parentOf(x))) { 修复情况 2
                    x = parentOf(x);
                    rotateLeft(x);
                }
				// 修复情况 3
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x))); // 相反的，x 的叔叔 y 节点就是 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)));
            }
        }
    }
    root.color = BLACK;
}

// 左旋
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;
    }
}

// 右旋
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;
    }
}

// 下面 5 个都是工具方法，在 fixAfterInsertion 方法中使用到了
private static <K,V> boolean colorOf(Entry<K,V> p) {
    return (p == null ? BLACK : p.color);
}

private static <K,V> void setColor(Entry<K,V> p, boolean c) {
    if (p != null)
        p.color = c;
}

private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
    return (p == null ? null: p.parent);
}

private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
    return (p == null) ? null: p.left;
}

private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
    return (p == null) ? null: p.right;
}

上面代码中的前三个方法都有一个 /** From CLR */ 的注释，表示它们其实是借鉴了C#的 Common Language Runtime 中的代码，可能Java的开发者是在看了CLR的源码之后才开发的TreeMap XD。

在进行了修复操作之后，红黑树又恢复其本身的性质，接下来我们看看红黑树的删除操作。

6. 红黑树的删除

红黑树的删除和普通的二叉查找树的删除操作是一样的，删除一个节点会分为以下三种情况：

  1. 没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了；
  2. 只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了；
  3. 当被删除结点存在左右孩子的时候，真正被删除的点应该是该节点的左子树的最大的节点（或者是右子树的最小的节点，根据实际需要来进行选择即可），之后当前节点的值被替换为真正被删除掉的节点的值（即把子节点的值保存在当前节点了），这样一来问题就变成了第1或者第2种情况了。

我们先来看一下Java中是如何进行进行删除操作的，具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    // 1. 删除点 p 有左右两个子节点，对应上面的情况 3，需要执行 successor 函数来把问题转化为第 1 或者第 2 种情况
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {// 2. 删除点 p 只有一个子节点
        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;
        p.left = p.right = p.parent = null;
        if (p.color == BLACK)
            fixAfterDeletion(replacement);// 调整
    } else if (p.parent == null) {
        root = null;
    } else { // 3. 删除点 p 的左右子树都为空
        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;
        }
    }
}

观察上面的源码就可以知道，Java会先对要删除的节点进行判断，分为以下三种情况，对应了我们在上面所说的三种理论情况

  1. 左右两个子树都不为空，就执行 successor 方法来把问题转化为只有一个子树或没有子树的情况（successor方法就是把当前节点和其右子树的最小值进行替换的方法，或者说把其右子树的最小值赋给当前节点，比较简单，就不贴出来了，相信你自己肯定也能够写出来）；
  2. 只有一个子树，把子节点接在父节点上，当前节点删除；
  3. 没有子节点，即叶子节点，直接删除即可。

上面的三种情况中，左右都不为空的情况会转化为子节点为一个或者没有子节点的情况，也就是说真正执行了删除操作的其实只是后两种情况。而在执行了删除操作之后，红黑树的性质可能发生了变化，所以在后两种情况执行了删除操作之后就要执行方法 fixAfterDeletion 来修复红黑树的性质。

我在之前的博客二叉查找树与 AVL 树有过介绍二叉查找树的删除操作，也可以做作为参考。

执行了删除操作之后，红黑树的性质可能分已经发生了改变，需要进行红黑树的修复操作，需要执行方法 fixAfterDeletion。

7. 删除之后红黑树的修复*

红黑树删除后的修复操作的源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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)); // x 的兄弟节点

            if (colorOf(sib) == RED) { // 情况 1
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }

            if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 情况 2
                setColor(sib, RED);
                x = parentOf(x);
            } else { // 情况 3
                if (colorOf(rightOf(sib)) == BLACK) { // 情况 4
                    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 { // 和上面的那种情形成对称
            Entry<K,V> sib = leftOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }

            if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }

    setColor(x, BLACK);
}

下面这张图从两种不同的初始状态开始，对应了红黑树的修复操作。虽然两颗红黑树的初始状态不一致，但是事实上还是符合上面源代码中所写的流程的。只不过在这两棵树中因为 sib 的左子树的左儿子颜色不一样，导致了对应情况 2和情况3两种情况（即第13行的那个判定条件，左边流程图对应情况2，右边的流程图对应情况3）。

从第29行开始，是一种和上面的那种操作构成镜像的情形，不多说了。然后之所以在这里我们需要进行一个循环操作是因为情况2中会把当前节点的父节点作为新的当前节点，这步操作可能会引入新的问题，所以需要再对当前节点进行性质判断，由此引发了一个迭代的过程，最终完成红黑树的性质的修复，操作完成。

参考：

  1. 教你透彻了解红黑树
  2. TreeSet and TreeMap