Zacard's Notes

红黑树&TreeMap的实现原理

发表于 | 分类于 | | 阅读次数

前言

由于TreeMap的实现原理就是以红黑树为基础数据结构的，所以基本也是红黑树的原理解读。

红黑树

红黑树是一种自平衡的二叉查找树。是一种复杂但高效的数据结构，它可以在O(log n)时间内做查找，插入和删除。

红黑树的规定：

1.一个节点只能是红色或者黑色
2.根节点是黑色
3.每个叶节点（null节点/空节点）为黑色
4.如果一个节点为红色，则他们的2个子节点都为黑色
5.从任意节点到其每个叶节点

红黑树结构java代码示例：（TreeMap中的内部类Entry）

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
/**
 * 红黑树节点结构
 */
   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; // 节点颜色，默认为黑
       /**
        * Make a new cell with given key, value, and parent, and with
        * {@code null} child links, and BLACK color.
        */
       Entry(K key, V value, Entry<K, V> parent) {
           this.key = key;
           this.value = value;
           this.parent = parent;
       }
       /**
        * Returns the key.
        *
        * @return the key
        */
       public K getKey() {
           return key;
       }
       /**
        * Returns the value associated with the key.
        *
        * @return the value associated with the key
        */
       public V getValue() {
           return value;
       }
       /**
        * Replaces the value currently associated with the key with the given
        * value.
        *
        * @return the value associated with the key before this method was
        * called
        */
       public V setValue(V value) {
           V oldValue = this.value;
           this.value = value;
           return oldValue;
       }
       public boolean equals(Object o) {
           if (!(o instanceof Map.Entry))
               return false;
           Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
           return valEquals(key, e.getKey()) && valEquals(value, e.getValue());
       }
       public int hashCode() {
           int keyHash = (key == null ? 0 : key.hashCode());
           int valueHash = (value == null ? 0 : value.hashCode());
           return keyHash ^ valueHash;
       }
       public String toString() {
           return key + "=" + value;
       }
   }

红黑树的平衡

在介绍红黑树的插入前，先弄清楚红黑树如何保持平衡。因为一般在对红黑树插入后，需要对红黑树做平衡化处理。

红黑树的左旋

红黑树的左旋操作如下图：

代码如下所示：(TreeMap.rotateLeft)

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
/**
 * 红黑树左旋
 */
private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        // 获取p(对应动图中的E节点)的右子节点定义为r(对应为动图中的S)
        Entry<K, V> r = p.right;
        // 将p的右子节点设置为r的左子节点
        p.right = r.left;
        // 如果r的左子节点不为空,则设置r的左子节点的父节点为p
        if (r.left != null)
            r.left.parent = p;
        // 将r的父节点设置为p的父节点
        r.parent = p.parent;
        // 如果p没有父节点,则将r设置为根节点
        if (p.parent == null)
            root = r;
        // 如果p为p父节点的左子节点,则将p的父节点的左子节点设置为r
        else if (p.parent.left == p)
            p.parent.left = r;
        // 反之将p的父节点的右子结点设置为r
        else
            p.parent.right = r;
        // 将r的左子节点设置为p
        r.left = p;
        // 将p的父节点设置为r
        p.parent = r;
    }
}

红黑树的右旋

红黑树的右旋操作如下图：

代码如下所示：（TreeMap.rotateRight）

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
/**
 * 红黑树右旋
 */
private void rotateRight(Entry<K, V> p) {
    if (p != null) {
        // 将p的左子节点定义为l
        Entry<K, V> l = p.left;
        // 将p的左子节点设置为l的右子节点
        p.left = l.right;
        // 如果l的右子节点不为空,则将l的右子节点的父节点设置为p
        if (l.right != null) l.right.parent = p;
        // 将l的父节点设置为p的父节点
        l.parent = p.parent;
        // 如果p的父节点为空,则将l设置为根节点
        if (p.parent == null)
            root = l;
        // 如果p为p的父节点的右子节点,则将p的父节点的右子节点设置为l
        else if (p.parent.right == p)
            p.parent.right = l;
        // 反之将p的父节点的左子节点设置为l
        else p.parent.left = l;
        // 将l的右子节点设置为p
        l.right = p;
        // 将p的父节点设置为l
        p.parent = l;
    }
}

红黑树插入

首先红黑树是一棵二叉查找树，所以新增一个节点，首先根据二叉树的性质找到相应的节点位置。然后根据红黑树的特点进行调整和平衡。

红黑树新增节点需要注意以下三点：

1.新增节点默认为红色。
2.如果新增的节点的父节点为黑色，那么能维持红黑树的性质。
3.如果新增的节点的父节点为红色，那么会破坏红黑树的性质。需要通过重新着色、旋转等手段来维持红黑树的性质。

红黑树的节点新增有以下5种情况：
(以下约定,新增节点为N,父节点为P,叔父节点为U,祖父节点为G)

1.新增节点没有父节点，即为跟节点，直接设置为黑色。
2.新增节点的父节点为黑色，则直接插入。
3.新增节点(N)的父节点(P)和叔父节点(U)都为红色->将父节点(P)和叔父节点(U)设置为黑，祖父节点(G)设置为红。这时候，由于经由父节点(P)和叔父节点(U)的路径必经过祖父节点(G)，所以这些路径上的黑色节点数目还是相同的。但是祖父节点(G)变为红色之后，祖父节点(G)的父节点可能也是红色，这时候就要将祖父节点(G)当做新增节点递归处理。如下图所示：

4.新增节点(N)的父节点(P)为红色，父节点(P)为祖父节点(G)的左子节点，叔父节点(U)都为黑色或者缺少，且新增节点(N)为父节点(P)的右子节点->将节点N,P左旋（如下图所所示）。这里注意，如果父节点(P)为祖父节点(G)的右子节点时是要进行右旋。然后产生的结果其实还没有完成，以为违反了规则4，将P节点作为新增节点进行情况5的操作。

5.新增节点(N)的父节点(P)为红色，父节点(P)为祖父节点(G)的左子节点，叔父节点(U)都为黑色或者缺少，且新增节点(N)为父节点(P)的左子节点->将祖父节(G)与父节点(P)进行右旋（如果父节点(P)为祖父节点(G)的右子节点，进行左旋），然而还没有完成，因为节点P,N都为红色，违反了规则4。将P,G的颜色进行交换。如下图所示：

TreeMap中元素的插入

TreeMap的put()方法其实只是找到新增节点插入的位置，而插入之后的红黑树平黑调整调用了fixAfterInsertion()方法进行。put()方法代码如下：

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
/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key   key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with {@code key}, or
 * {@code null} if there was no mapping for {@code key}.
 * (A {@code null} return can also indicate that the map
 * previously associated {@code null} with {@code key}.)
 * @throws ClassCastException   if the specified key cannot be compared
 *                              with the keys currently in the map
 * @throws NullPointerException if the specified key is null
 *                              and this map uses natural ordering, or its comparator
 *                              does not permit null keys
 */
public V put(K key, V value) {
    // 用t表示当前root节点(也就是整棵数)
    Entry<K, V> t = root;
    // 当t为null时,说明是空树,treeMap中没有元素,直接插入
    if (t == null) {
        /*
          这里key自我比较很奇怪。
          其实是为了key的null校验和k类型检查。
          校验key是否可比较的.
          这里其实可以用类泛型限定,如TreeMap<key extends Comparable>,之所以没有这么做应该是jdk版本兼容性的考虑
         */
        compare(key, key); // type (and possibly null) check
        // 根据key-value,生成节点赋值为root
        root = new Entry<>(key, value, null);
        // 容器的元素数量赋值为1
        size = 1;
        // 修改次数+1
        modCount++;
        return null;
    }
    int cmp;// key排序比较的结果
    Entry<K, V> parent;// 父节点
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    // 如果指定的比较器不为空,使用指定的比较器进行比较
    if (cpr != null) {
        do {
            parent = t;//parent赋值为上次循环后的t
            // 比较key和当前节点的key
            cmp = cpr.compare(key, t.key);
            // key小于当前节点的key,则t指向t的左子节点
            if (cmp < 0)
                t = t.left;
            // key大于当前节点的key,则t指向t的右子节点
            else if (cmp > 0)
                t = t.right;
            // key等于当前节点的key,直接在当前节点设置新值并返回
            else
                return t.setValue(value);
        } while (t != null);//递归的进行上述操作,直到t==null
    } else { // 如果没有知道比较器,则按照默认的比较方式(即自然顺序)
        // 如果key==null抛出空指针异常
        if (key == null)
            throw new NullPointerException();
        // 以下处理过程和上面的一样
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 将新增的节点当做parent的子节点
    Entry<K, V> e = new Entry<>(key, value, parent);
    // 新增节点key小于parent的key,则作为左子节点
    if (cmp < 0)
        parent.left = e;
    // 新增节点key大于parent的key,则作为右子节点
    else
        parent.right = e;
    // 新增节点已经在合适的位置了,然后进行红黑树的平衡调整
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

再来看看fixAfterInsertion()如何进行红黑树的平衡的，代码如下：

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
/**
 * 红黑树平衡
 */
private void fixAfterInsertion(Entry<K, V> x) {
    x.color = RED; // 新增节点的颜色设置为红色
    // 循环直到x为null或者x是根节点或者x的父节点为黑色
    while (x != null && x != root && x.parent.color == RED) {
        // 如果x的父节点为x的祖父节点的左节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 获取x的叔父节点定义为y
            Entry<K, V> y = rightOf(parentOf(parentOf(x)));
            // 如果叔父节点的颜色为红色(情况3)
            if (colorOf(y) == RED) {
                // 设置父节点的颜色为黑色
                setColor(parentOf(x), BLACK);
                // 设置叔父节点的颜色为黑色
                setColor(y, BLACK);
                // 设置祖父节点的颜色为红色
                setColor(parentOf(parentOf(x)), RED);
                // x赋值为祖父节点,递归判断
                x = parentOf(parentOf(x));
            }
            // 如果叔父节点的颜色为黑色
            else {
                // 如果x为其父节点的右节点(情况4)
                if (x == rightOf(parentOf(x))) {
                    // x赋值为其父节点
                    x = parentOf(x);
                    // 根据x的父节点进行左旋
                    rotateLeft(x);
                }
                // 情况5
                // 设置x的父节点为黑色
                setColor(parentOf(x), BLACK);
                // 设置x的祖父节点为红色
                setColor(parentOf(parentOf(x)), RED);
                // 根据x的祖父节点右旋
                rotateRight(parentOf(parentOf(x)));
            }
        }
        // 如果x的父节点为x的祖父节点的右节点
        else {
            // 定义x的叔父节点为y
            Entry<K, V> y = leftOf(parentOf(parentOf(x)));
            // 如果叔父节点的颜色为红色(情况3)
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            }
            // 如果叔父节点的颜色为黑色
            else {
                // 如果x为其父节点的左子节点(情况4)
                if (x == leftOf(parentOf(x))) {
                    // x赋值为其父节点
                    x = parentOf(x);
                    // 针对x父节点右旋
                    rotateRight(x);
                }
                // 情况5
                // 设置x的父节点颜色为黑色
                setColor(parentOf(x), BLACK);
                // 设置祖父节点颜色为红色
                setColor(parentOf(parentOf(x)), RED);
                // 根据祖父节点进行左旋
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    // 设置根节点颜色为黑色
    root.color = BLACK;
}

红黑树的删除

相比较红黑树的插入，红黑树的删除更加复杂。删除一个节点，一般要寻找一个真正的删除点,替代删除点，然后根据删除点做红黑树的平衡。

如何寻找到真正的删除点呢？其实就是寻找待删除点的中序遍历(LDR)的前继节点或者后继节点。即待删除点的最左父树的右父节点或者右子树的最左节点。

所以可以推断出，真正的删除点必定是一个只有一个孩子或者没有孩子的节点，而根据红黑树的性质，可以得出以下2个结论：

  • 真正的删除点必定只有一个红色孩子节点或者没有孩子节点
  • 如果真正的删除点是一个红色节点，那它必定是个叶子节点

所以，红黑树的删除步骤如下：

1.寻找真正的删除点，将真正删除点的元素赋值为待删除点
2.删除真正的删除点，如果删除点有子节点，以子节点代替其位置
3.以删除点开始判定红黑树的平衡性质
4.如有必要做相应的平衡操作

以下开始讨论红黑树删除的几种情况。我们约定，真正的删除点使用“旧”标记，旧点所在位置将被他的子节点取代（最多只会有一个子节点），我们使用“新”标记旧点的孩子节点。删除操作会有以下集中情况：

1.旧点为红色节点

若旧点为红色节点，则它必定为叶子节点，直接删除即可。

2.一黑一红

当旧点为黑色结点，新点为红色结点时，将新点取代旧点位置后，将新点染成黑色即可（如下图所示）。这里需要注意：旧点为红色，新点为黑色的情况不可能存在。

3.双黑

当旧点和新点都为黑色是（新点为空节点也属于这种情况），情况比较复杂，需要根据旧点兄弟结点的颜色来决定进行什么样的操作。我们使用“兄”来表示旧点的兄弟结点。

3.1 红兄

由于兄弟结点为红色，所以父结点必定为黑色，而旧点被删除后，新点取代了它的位置。下图演示了两种可能的情况：

红兄的情况需要进行RR或LL型旋转，然后将父结点染成红色，兄结点染成黑色。然后重新以新点为判定点进行平衡操作。我们可以观察到，旋转操作完成后，判定点没有向上回溯，而是降低了一层，此时变成了黑兄的情况（可能会是3.2.1、3.2.2、3.2.3）。

3.2 黑兄

黑兄的情况最为复杂，需要根据黑兄孩子结点（这里用“侄”表示）和父亲结点的颜色来决定做什么样的操作。

3.2.1 黑兄二黑侄

这种情况比较简单，只需将兄结点变为红色即可，然后根据父节点继续平衡。（其实这时候如果父节点为红色，将父节点设置为黑色，删除操作就结束了）如下图所示：

3.2.2 黑兄右黑侄

黑兄，左侄红色，右侄黑色这种情况需要区分新点是起父节点的左子节点还是右子节点。

3.2.2-1 新点是其父的左子节点

将左侄设置为黑，兄节点设置为红色，然后以兄节点右旋（将情况转为了3.2.3-1）。如下图所示：

3.2.2-2 新点为其父节点的右子节点

将兄节点的颜色设置为父节点颜色，父节点和左侄节点设置为黑色，然后根据父节点右旋。删除操作结束。如下图所示：

3.2.3 黑兄左黑侄

黑兄，左黑侄，右红侄的情况也是需要区分新点是起父节点的左子节点还是右子节点.

3.2.3-1 新点是左子节点

将兄节点的颜色设置为父节点的颜色，父节点和右侄节点设置为黑色,然后根据父节点左旋。删除结束。如下图所示：

3.2.3-2 新点是右子节点

将右侄设置为黑色，兄节点设置为红色，然后以兄节点左旋（将情况转为3.2.2-2）。如下图说示：

TreeMap删除代码

TreeMap.remove代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public V remove(Object key) {
    // 根据key查找出节点p
    Entry<K, V> p = getEntry(key);
    // 如果p不存在,直接返回null
    if (p == null)
        return null;
    V oldValue = p.value;
    // 根据节点p删除节点
    deleteEntry(p);
    return oldValue;
}

remove其实只是根据key找出对应的节点。真正的删除在deleteEntry方法中,代码如下所示:

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
/**
 * 删除节点p,然后平衡红黑树.
 */
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.
    // 如果节点p存在左右子节点,则寻找其真正的删除点(其实是中序遍历的后继节点)
    if (p.left != null && p.right != null) {
        // 寻找中序遍历的后继节点
        Entry<K, V> s = successor(p);
        // 将后继节点的元素值赋给节点p
        p.key = s.key;
        p.value = s.value;
        // 将真正删除点赋值为节点p
        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);
    } 
    // 如果真正删除点的父节点为空,那其实treeMap中只有一个元素,直接删除
    else if (p.parent == null) { // return if we are the only node.
        root = null;
    } 
    // 如果真正删除点p没有子节点,这里有2中情况,如果p为红色即为情况1,直接删除。反之需要树的平衡
    else { //  No children. Use self as phantom replacement and unlink.
        // 如果p节点为黑色,则需要平衡树操作
        if (p.color == BLACK)
            fixAfterDeletion(p);
        // 删除节点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;
        }
    }
}

在删除节点后，可能需要调用fixAfterDeletion方法来平衡红黑树。fixAfterDeletion方法代码如下所示：

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
102
103
104
105
106
107
108
/**
 * 红黑树节点删除后平衡操作
 */
private void fixAfterDeletion(Entry<K, V> x) {
    // 循环平衡红黑树直到根节点或者节点的颜色为红色
    while (x != root && colorOf(x) == BLACK) {
        // 当节点x为其父节点的左子节点时
        if (x == leftOf(parentOf(x))) {
            // 将x的兄节点定义为sib
            Entry<K, V> sib = rightOf(parentOf(x));
            // 当兄节点为红色时,情况3.1
            if (colorOf(sib) == RED) {
                // 将兄节点设置为黑色
                setColor(sib, BLACK);
                // 将父节点设置为黑色
                setColor(parentOf(x), RED);
                // 以父节点左旋
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            // 如果兄节点的左右子节点都为黑色,情况3.2.1
            if (colorOf(leftOf(sib)) == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                // 将兄节点设置为红色
                setColor(sib, RED);
                // 以x的父节点在递归平衡
                x = parentOf(x);
            }
            // 如果兄节点左右子节点的颜色不一致
            else {
                // 如果只有右侄节点为黑色,情况3.2.2-1
                if (colorOf(rightOf(sib)) == BLACK) {
                    // 将左侄设置为黑色
                    setColor(leftOf(sib), BLACK);
                    // 将兄节点设置为红色
                    setColor(sib, RED);
                    // 以兄节点右旋
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                // 情况3.2.3-1
                // 将兄节点的颜色设置为父节点的颜色
                setColor(sib, colorOf(parentOf(x)));
                // 将父节点设置为黑色
                setColor(parentOf(x), BLACK);
                // 将右侄节点设置为黑色
                setColor(rightOf(sib), BLACK);
                // 根据父节点左旋
                rotateLeft(parentOf(x));
                x = root;
            }
        }
        // 当节点x为其父节点的右子节点
        else { // symmetric
            // 定义其兄节点为sib
            Entry<K, V> sib = leftOf(parentOf(x));
            // 当兄节点为红色,情况3.1
            if (colorOf(sib) == RED) {
                // 将兄节点颜色设置为黑色
                setColor(sib, BLACK);
                // 将父节点颜色设置为红色
                setColor(parentOf(x), RED);
                // 以父节点右旋
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }
            // 如果2个侄子节点都是黑色,情况3.2.1
            if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                // 将兄节点设置为红色
                setColor(sib, RED);
                // 以父节点递归平衡
                x = parentOf(x);
            }
            // 如果2个侄子节点的颜色不一致
            else {
                // 如果左侄节点颜色为黑色,情况3.2.3-2
                if (colorOf(leftOf(sib)) == BLACK) {
                    // 将右侄节点颜色设置为黑色
                    setColor(rightOf(sib), BLACK);
                    // 将兄节点颜色设置为红色
                    setColor(sib, RED);
                    // 以兄节点左旋
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                // 情况3.2.2-2
                // 将兄节点颜色设置为父节点颜色
                setColor(sib, colorOf(parentOf(x)));
                // 将父节点颜色设置为黑色
                setColor(parentOf(x), BLACK);
                // 将左侄节点颜色设置为黑色
                setColor(leftOf(sib), BLACK);
                // 以父节点右旋
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }
    // 将x节点设置为黑色
    setColor(x, BLACK);
}

后记

这篇笔记写了4天时间。参考了大量大牛的文章，遇到不太懂的时候就拿viso自己画图帮助理解。这次的学习过程收获良多，让我不得不再次感叹数据结构的精妙与算法的魅力。

坚持原创技术分享，您的支持将鼓励我继续创作！

热评文章