红黑树(RBT)

Posted on | Edited on | In , | Views:

红黑树

１．基本知识：

1.1什么是红黑树？

​ 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪．

​ 和AVL树相比，AVL树是一棵严格的平衡树（它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1），它的所有子数都满足平衡二叉树的定义．因此，AVL树的查找效率很高，但是插入，删除旋转次数比红黑树多．

1.2红黑树的性质：

​ a．每个结点都是红色或者黑色；

​ b．根结点是黑色．

​ c．每个叶结点都是黑色（注意这里的叶结点都是指空结点）；

​ d．如果一个结点是红色的，则它的两个儿子是黑色的；

​ e．对于每一个结点，从该结点到其叶子结点构成的所有路径上的黑结点个数相同．

２．TreeSet and TreeMap

2.1总体介绍

​ 红黑树应用之一就是Java集合类中TreeSet和TreeMap的实现．以TreeMap的源码为例来讲解红黑树．

​ 我们上边学习了红黑树的性质，但是当我们进行插入或者删除操作时，性质d，c可能会被破坏，因此我们需要进行调整使它成为一颗合格的红黑树．

​ 调整的方法一般有两类：颜色调整和结构调整（左旋，右旋）．

2.2预备知识

2.2.1左旋

​ 左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

​ (图片暂时没有)

​ TreeMap源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void rotateLeft(TreeMap.Entry<K, V> p) {
        if (p != null) {
            TreeMap.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) {
                this.root = r;
            } else if (p.parent.left == p) {
                p.parent.left = r;
            } else {
                p.parent.right = r;
            }

            r.left = p;
            p.parent = r;
        }

    }

2.2.2右旋

​ 右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

​ TreeMap源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void rotateRight(TreeMap.Entry<K, V> p) {
        if (p != null) {
            TreeMap.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) {
                this.root = l;
            } else if (p.parent.right == p) {
                p.parent.right = l;
            } else {
                p.parent.left = l;
            }

            l.right = p;
            p.parent = l;
        }

    }

2.2.3寻找结点后继

​ 对于一棵二叉查找树，给定节点t，其后继（树中比大于t的最小的那个元素）可以通过如下方式找到：

  1. t的右子树不空，则t的后继是其右子树中最小的那个元素（右子树中最左边的）。
  2. t的右孩子为空，则t的后继是其第一个向左走的祖先。

后继节点在红黑树的删除操作中将会用到。

​ TreeMap源代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static <K, V> TreeMap.Entry<K, V> successor(TreeMap.Entry<K, V> t) {
        if (t == null) {
            return null;
        } else {
            TreeMap.Entry p;
            if (t.right != null) {
                for(p = t.right; p.left != null; p = p.left) {
                }
                return p;
            } else {
                p = t.parent;
                for(TreeMap.Entry ch = t; p != null && ch == p.right; p = p.parent) {
                    ch = p;
                }
                return p;
            }
        }
    }

2.3主要方法分析

2.3.1 get()

​ get(Object key)根据key找到指定键值的value，或者null.该方法中核心是通过getEntry(Object key)来的到entry，然后返回entry.value．

​ 算法思想是根据key的自然顺序（或比较器顺序）对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry．

​ get()源码：

1
2
3
4
public V get(Object key) {
        TreeMap.Entry<K, V> p = this.getEntry(key);
        return p == null ? null : p.value;
    }

​ getEntry()源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
final TreeMap.Entry<K, V> getEntry(Object key) {
    if (this.comparator != null) {
        return this.getEntryUsingComparator(key);
    } else if (key == null) {
        throw new NullPointerException();
    } else {
        Comparable<? super K> k = (Comparable)key;
        TreeMap.Entry p = this.root;
        while(p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0) {
                p = p.left;
            } else {
                if (cmp <= 0) {
                    return p;
                }
                p = p.right;
            }
        }
        return null;
    }
}

2.3.2 put()

​ put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则替换旧值，查找过程类似于getEntry()方法；如果没有找到则会在红黑树中插入新的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
public V put(K key, V value) {
	TreeMap.Entry<K, V> t = this.root;
        if (t == null) {
            this.compare(key, key);
            this.root = new TreeMap.Entry(key, value, (TreeMap.Entry)null);
            this.size = 1;
            ++this.modCount;
            return null;
        } else {
            Comparator<? super K> cpr = this.comparator;
            int cmp;
            TreeMap.Entry parent;
            if (cpr != null) {　//按照比较器顺序
                do {
                    parent = t;
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0) {
                        t = t.left;
                    } else {
                        if (cmp <= 0) {
                            return t.setValue(value);
                        }
                        t = t.right;
                    }
                } while(t != null);
            } else {
                //按照key的自然顺序查找
                if (key == null) {
                    throw new NullPointerException();
                }
                Comparable k = (Comparable)key;
                do {
                    parent = t;
                    cmp = k.compareTo(t.key);
                    if (cmp < 0) {
                        t = t.left;
                    } else {
                        //若之前有，用新值替换旧值
                        if (cmp <= 0) {
                            return t.setValue(value);
                        }
                        t = t.right;
                    }
                } while(t != null);
            }
            //创建并插入新的entry
            TreeMap.Entry<K, V> e = new TreeMap.Entry(key, value, parent);
            if (cmp < 0) {
                parent.left = e;
            } else {
                parent.right = e;
            }
			//调整红黑树
            this.fixAfterInsertion(e);
            ++this.size;
            ++this.modCount;
            return null;
        }
    }

​ 上述代码的插入部分并不难理解：首先在红黑树上找到合适的位置，然后创建新的entry并插入（当然，新插入的节点一定是树的叶子）．难点是调整函数fixAfterInsertion()，前面已经说过，调整往往需要1.改变某些节点的颜色，2.对某些节点进行旋转。

​ 在介绍该方法之前，我们先来学习一下关于红黑树的插入操作：

红黑树的插入：

​ 首先，插入的结点默认为红色．为何？可以从两个方面来解释：一，由性质d我们知道红黑树中黑节点至少是红节点的两倍，因此插入节点的父节点为黑色的概率较大，而此时并不需要作任何调整，因此效率较高；二，由性质e我们可以知道，当我们插入红色结点时，破坏的性质少，性质e并没有被破坏．

​ 插入过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
１．父为黑
	插入后无需任何操作．由于黑节点个数至少为红节点的两倍，因此父为黑的情况较多，而这种情况在插入后一般无需任何调整．
２．父为红
	这时红黑树的性质被破坏，此时我们需要根据叔叔结点（和父结点有同一父亲的结点）的颜色分情况讨论．
2.1 叔叔为红
	只需交换爸爸、叔叔和爷爷的颜色即可．（父＝black, 叔＝black，爷＝red）
	此时若爷爷节点和太爷爷节点颜色相同，再以爷爷节点为起始节点，进行刚才相同的操作．
2.2 叔叔为黑
此时分四种情况：
a)爸爸在左，叔叔在右，我在左
	对爷爷结点，进行一次R旋转．（旋转后爸爸为根结点）
b)爸爸在左，叔叔在右，我在左
	对父亲结点，进行一次L旋转； 
	对爷爷结点，进行一次R旋转．（旋转后我为根结点）
	（此时，多进行一次L旋转）
c)叔叔在左、爸爸在右、我在右
	对爷爷结点，进行一次L旋转．（旋转后爸爸为根结点）
d)叔叔在左、爸爸在右、我在左
	对父亲结点，进行一次R旋转； 
	对爷爷结点，进行一次L旋转．（旋转后我为根结点）
要注意旋转完进行颜色调整．

​ 现在我们来看看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
private void fixAfterInsertion(TreeMap.Entry<K, V> x) {
        x.color = false;	//false == red　插入的新结点为红结点
        while(x != null && x != this.root && !x.parent.color) {	//爸爸结点为红
            TreeMap.Entry y;
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //爸爸结点在左
                y = rightOf(parentOf(parentOf(x))); //叔叔结点在右
                if (!colorOf(y)) {　//叔叔结点为红
                    setColor(parentOf(x), true);
                    setColor(y, true);
                    setColor(parentOf(parentOf(x)), false);
                    x = parentOf(parentOf(x));
                } else { //叔叔结点为黑
                    if (x == rightOf(parentOf(x))) {　//爸爸在左，叔叔在右，我在右
                        x = parentOf(x);
                        this.rotateLeft(x);
                    }
                    //爸爸在左，叔叔在右，我在左
                    setColor(parentOf(x), true);
                    setColor(parentOf(parentOf(x)), false);
                    this.rotateRight(parentOf(parentOf(x)));
                }
            } else {　//爸爸结点在右
                y = leftOf(parentOf(parentOf(x)));	//叔叔结点在左
                if (!colorOf(y)) {　//叔叔结点为红
                    setColor(parentOf(x), true);
                    setColor(y, true);
                    setColor(parentOf(parentOf(x)), false);
                    x = parentOf(parentOf(x));
                } else {　//叔叔结点为黑
                    if (x == leftOf(parentOf(x))) {	//叔叔在左、爸爸在右、我在左
                        x = parentOf(x);
                        this.rotateRight(x);
                    }
					//叔叔在左、爸爸在右、我在右
                    setColor(parentOf(x), true);
                    setColor(parentOf(parentOf(x)), false);
                    this.rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
		//爸爸结点为黑，不调整
        this.root.color = true;
    }

2.3.3 remove()

​ remove(Object key)的作用是删除key值对应的entry，该方法首先通过上文中提到的getEntry(Object key)方法找到key值对应的entry，然后调用deleteEntry(Entry<K,V> entry)删除对应的entry．由于删除操作会改变红黑树的结构，有可能破坏红黑树的约束条件，因此有可能要进行调整．

​ getEntry()函数上面已经讲解过，这里重点放deleteEntry()上，该函数删除指定的entry并在红黑树的约束被破坏时进行调用fixAfterDeletion(Entry<K,V> x)进行调整．

​ 我们先来看看红黑树的删除操作．

红黑树的删除：

​ 由于红黑树是一棵改良版的二叉查找树，红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似，唯一的区别是红黑树在节点删除之后可能需要进行调整．现在考虑一棵普通二叉查找树的删除过程，可以简单分为两种情况：

  1. 删除点p的左右子树都为空，或者只有一棵子树非空。
  2. 删除点p的左右子树都非空。

​ 对于上述＂情况1＂处理起来比较简单，直接将p删除（左右子树都为空时），或者用非空子树替代p（只有一棵子树非空时）；

​ 对于＂情况2＂可以用p的后继s（树中大于x的最小的那个元素）代替p，然后使用情况1删除s（此时s一定满足情况1.可以画画看）．

​ 我们来看看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
private void deleteEntry(TreeMap.Entry<K, V> p) {
       ++this.modCount;
       --this.size;
       TreeMap.Entry replacement;
       if (p.left != null && p.right != null) {	//双子树都为非空，情况２
           replacement = successor(p);	//找到p的后继
           /*将后继复制到p上，相当于已经把原来p删除，现在目的是需要把原来结点的后继删除
		  需要注意的是，只是修改了原结点的k，value，但是结点的颜色并没有改变
		  删除操作的对象已经完全变成原来的后继结点
		*/
           p.key = replacement.key;	
           p.value = replacement.value;
           //p指向后继结点
           p = replacement;
       }
	//如果p有左子结点，找到左字节点，否则用右子结点
       replacement = p.left != null ? p.left : p.right;
       if (replacement != null) {	//p结点有一个子树
           //将p的父结点设置为replacement的父结点
           replacement.parent = p.parent;
    		//将p的子结点和p的父结点向连
           if (p.parent == null) {　//p本身就是根结点
               this.root = replacement;
           } else if (p == p.parent.left) {
               p.parent.left = replacement;
           } else {
               p.parent.right = replacement;
           }
		//将p结点删除
           p.left = p.right = p.parent = null;
           //p为黑结点，需要调整树
           if (p.color) {
               this.fixAfterDeletion(replacement);
           }
       } else if (p.parent == null) {　//若p为空，则树为空
           this.root = null;
       } else {　//被删除的结点为叶子结点
           if (p.color) {
               this.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;
           }
       }

   }

​ 当结点被删除后，红黑树需要考虑是否需要调整．我们发现，如果删除的是红色结点，并不会破坏红黑树的性质．只有删除点是黑结点的时候，才会触发调整函数，

​ 跟上文中讲过的fixAfterInsertion()函数一样，fixAfterDeletion(Entry<K,V> x)也要分成若干种情况．记住，无论有多少情况，具体的调整操作只有两种：1.改变某些节点的颜色，2.对某些节点进行旋转．

​ 删除黑结点后的调整情况．

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
我们先假设：
P为删除的结点；
x为P的子结点，x会覆盖到P的位置；
sib为P的兄弟结点，同时也是x现在兄弟结点；
pp为sib和x(p)父结点；

1　x为红色时，直接覆盖，保留父结点的颜色（黑色）．
2　x为黑色时，此时需要考虑sib
	2.1 sib为红色的时候：(此时，pp一定为黑)
		2.1.1 x在左，sib在右
			sib黑，pp红，并对pp进行左旋；
			这时，现sib = 原来sib.left
		2.1.2 x在右，sib在左
			sib黑，pp红，并对pp进行右旋；
			这时，现sib = 原来sib.right
	2.2 sib为黑时（不能判断pp的颜色）
		2.2.1 pp红，sib的两子结点为黑
			sib红，pp黑　（此时，x和sib的左右顺序无关）
		2.2.1 pp黑，sib的两子结点为黑
			sib红，pp黑　（此时，x和sib的左右顺序无关）
		2.2.3 pp颜色随意，sib至少有一个红子结点
			2.2.3.1 红侄为左左（sib左，sib左儿子红）
				没有删除之前，pp的右边至少两个黑结点，现在为１个
				对sib进行右旋
				红侄为黑，交换sib和pp的颜色．
			2.2.3.2 红侄为左右（sib左，sib右儿子红）
				对sib进行左旋，对pp进行右旋，将红侄移到子数的根结点
				红侄染成pp颜色，pp为黑色
			2.2.3.3 红侄为右右（sib右，sib右儿子红）
				对sib进行左旋，
				红侄为黑，交换sib和pp的颜色．
			2.2.3.4 红侄为右左（sib右，sib左儿子红）
				对sib进行右旋，对pp进行左旋，将红侄移到子数的根结点
				红侄染成pp颜色，pp为黑色

​ 我们现在来看看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
private void fixAfterDeletion(TreeMap.Entry<K, V> x) {
        //当x为根结点　或者　x为红结点时，直接染成黑结点即可
    	while(x != this.root && colorOf(x)) {　//当x为黑　且　不是根结点
            TreeMap.Entry sib;
            if (x == leftOf(parentOf(x))) {　//x为pp的左儿子
                sib = rightOf(parentOf(x));　//sib为pp的右儿子
                if (!colorOf(sib)) {　	//sib为红　2.2.1
//--情况１
                   	setColor(sib, true);
                    setColor(parentOf(x), false);
                    this.rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));//现sib = 原来sib.left
//情况１--
                }
				// sib一定为黑（没有进入上一个if 或者　sib为红，则它的子结点一定为黑）　
//--情况2
                if (colorOf(leftOf(sib)) && colorOf(rightOf(sib))) {
                    //此时，只需让sib为红，就能满足pp为根结点的子数左右黑结点数相同（2-1 == 2-1）
                    setColor(sib, false);
                    //pp的结点颜色不确定，让x指向x.parent，若为红直接跳出，若为黑，继续进入循环
                    x = parentOf(x);
//情况2-- 
                } else {// sib为黑，sib子结点至少有一个为红
                    if (colorOf(rightOf(sib))) {//2.2.3.4
//--情况3
                        setColor(leftOf(sib), true);
                        setColor(sib, false);
                        this.rotateRight(sib);
                        sib = rightOf(parentOf(x));
//情况3--
                    }
//--情况4
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), true);
                 	setColor(rightOf(sib), true);
                    this.rotateLeft(parentOf(x));
                    x = this.root;
//情况4--
                }
            } else { //与上边对称
                sib = leftOf(parentOf(x));
                if (!colorOf(sib)) {
//--情况5
                    setColor(sib, true);
                    setColor(parentOf(x), false);
                    this.rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
//情况5--
                }

                if (colorOf(rightOf(sib)) && colorOf(leftOf(sib))) {
//情况6
                    setColor(sib, false);
                    x = parentOf(x);
//情况6--
                } else {
                    if (colorOf(leftOf(sib))) {
//--情况7             
                        setColor(rightOf(sib), true);
                        setColor(sib, false);
                        this.rotateLeft(sib);
                        sib = leftOf(parentOf(x));
//情况7--  
                    }
//--情况8
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), true);
                    setColor(leftOf(sib), true);
                    this.rotateRight(parentOf(x));
                    x = this.root;
//情况8--    
                }
            }
        }

        setColor(x, true);
    }

​ 我们分析代码可以知道，如果进入循环中的情况一，将情况1首先转换成情况2，或者转换成情况3和情况4。当然，并不意味着调整过程一定是从情况1开始．通过后续代码我们还会发现几个有趣的规则：

​ a).如果是由情况1之后紧接着进入的情况2，那么情况2之后一定会退出循环（因为x为红色）；

​ b).一旦进入情况3和情况4，一定会退出循环（因为x为root）．

​ c).情况3其实是落在情况4内的．

​ d).情况5～情况8跟前四种情况是对称的．

参考资料：

https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/5-TreeSet%20and%20TreeMap.md

https://blog.csdn.net/qq_34173549/article/details/79636764