红黑树

微信公众号：如有问题或建议，请在下方留言

最近更新：2018-09-05

二分查找树(BST)

1、定义：

二分查找树又称二叉查找树、二叉 排序 树，英文缩写为BST，即Binary Search Tree。该数据结构的出现，是为了提高查找的效率。之所以成为二分查找树，是因为其采用二分查找的算法。

2、特性：

• 若左子树不为空，左子树上所有节点的值均小于根节点的值
• 若右子树不为空，右子树上所有节点的值均大于根节点的值
• 左右子树又分别是一棵二分查找树

3、示例：

下图是一个典型的二分查找树：

查找节点10：

1. 查看根节点5，因为10>5，往右子树走

2. 查看节点8，因为10>8，往右子树走

3. 查看节点15，因为10<15，往左子树走

4. 查看节点12，因为10<12，往左子树走

5. 查看节点10，正是我们要找的节点

4、思考：

虽然二叉查找树提高了查询的效率，但是依旧存在着缺陷，请看下面例子：

当依次插入6、5、4、3、2时，发现树成了线性形式，在此种情况下，查找效率大打折扣，因此就有了自平衡的二叉查找树，名为红黑树。

红黑树(RBT)

1、定义：

红黑树，是一个自平衡的二叉排序树，英文简称为RBT，即Red Black Tree。每个节点上增加了颜色属性，要么为红，要么为黑。

2、特性：

• 每个节点要么为红色，要么为黑色
• 根节点为黑色
• 每个叶子节点（NIL）是黑色 [ 注意： 这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
• 不允许连续两个红色节点
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点

3、示例：

下图是一个典型的红黑树：

4、思考：

针对于BST中提到的缺陷，依次插入6、5、4、3、2，红黑树是如何处理的呢？此处不做解答，请继续往下看。

红黑树实践-TreeMap

1、TreeMap.Entry：

首先我们来看下TreeMap中存储键值对的类-TreeMap.Entry，该类定义了红黑树的数据结构。查看其成员变量，除了存储key、value外，还存储了左节点、右节点、父节点、颜色(默认为黑色)。

 1 static final class Entry<K,V> implements Map.Entry<K,V> {
 2    K key;
 3    V value;
 4    Entry<K,V> left;
 5    Entry<K,V> right;
 6    Entry<K,V> parent;
 7    boolean color = BLACK;
 8
 9    /**
10     * Make a new cell with given key, value, and parent, and with
11     * {@code null} child links, and BLACK color.
12     */
13    Entry(K key, V value, Entry<K,V> parent) {
14        this.key = key;
15        this.value = value;
16        this.parent = parent;
17    }
18
19    /**
20     * Returns the key.
21     *
22     * @return the key
23     */
24    public K getKey() {
25        return key;
26    }
27
28    /**
29     * Returns the value associated with the key.
30     *
31     * @return the value associated with the key
32     */
33    public V getValue() {
34        return value;
35    }
36
37    /**
38     * Replaces the value currently associated with the key with the given
39     * value.
40     *
41     * @return the value associated with the key before this method was
42     *         called
43     */
44    public V setValue(V value) {
45        V oldValue = this.value;
46        this.value = value;
47        return oldValue;
48    }
49
50    public boolean equals(Object o) {
51        if (!(o instanceof Map.Entry))
52            return false;
53        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
54
55        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
56    }
57
58    public int hashCode() {
59        int keyHash = (key==null ? 0 : key.hashCode());
60        int valueHash = (value==null ? 0 : value.hashCode());
61        return keyHash ^ valueHash;
62    }
63
64    public String toString() {
65        return key + "=" + value;
66    }
67}
复制代码

2、添加元素代码实现：

 1public V put(K key, V value) {
 2    //找到合适的位置插入Entry元素
 3    Entry<K,V> t = root;
 4    if (t == null) {
 5        compare(key, key); // type (and possibly null) check
 6
 7        root = new Entry<>(key, value, null);
 8        size = 1;
 9        modCount++;
10        return null;
11    }
12    int cmp;
13    Entry<K,V> parent;
14    // split comparator and comparable paths
15    Comparator<? super K> cpr = comparator;
16    if (cpr != null) {
17        do {
18            parent = t;
19            cmp = cpr.compare(key, t.key);
20            if (cmp < 0)
21                t = t.left;
22            else if (cmp > 0)
23                t = t.right;
24            else
25                return t.setValue(value);
26        } while (t != null);
27    }
28    else {
29        if (key == null)
30            throw new NullPointerException();
31        @SuppressWarnings("unchecked")
32            Comparable<? super K> k = (Comparable<? super K>) key;
33        do {
34            parent = t;
35            cmp = k.compareTo(t.key);
36            if (cmp < 0)
37                t = t.left;
38            else if (cmp > 0)
39                t = t.right;
40            else
41                return t.setValue(value);
42        } while (t != null);
43    }
44    Entry<K,V> e = new Entry<>(key, value, parent);
45    if (cmp < 0)
46        parent.left = e;
47    else
48        parent.right = e;
49    //进行插入后的平衡调整
50    fixAfterInsertion(e);
51    size++;
52    modCount++;
53    return null;
54}
复制代码

因为插入后可能带来红黑树的不平衡，所以需要进行平衡调整，方法无非两种：

• 变色
• 旋转(左旋或者右旋)

 1private void fixAfterInsertion(Entry<K,V> x) {
 2    //默认插入元素颜色为红色
 3    x.color = RED;
 4
 5    //只要x不为根且父亲节点为红色就继续调整
 6    while (x != null && x != root && x.parent.color == RED) {
 7        //父节点为爷爷节点的左节点
 8        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
 9            //获取右叔节点
10            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
11            //右叔节点为红色(此时父节点也为红色)
12            if (colorOf(y) == RED) {
13                //变色
14                //父节点改为黑色
15                setColor(parentOf(x), BLACK);
16                //右叔节点改为黑色
17                setColor(y, BLACK);
18                //爷爷节点改成红色
19                setColor(parentOf(parentOf(x)), RED);
20                //爷爷节点所在的子树已平衡，所以让x指向爷爷节点，继续往上调整
21                x = parentOf(parentOf(x));
22            } else {
23                //父亲节点在爷爷节点的左边，而x在父亲节点的右边，则需要调整到同一侧
24                if (x == rightOf(parentOf(x))) {
25                    //x指向父节点
26                    x = parentOf(x);
27                    //以x进行左旋
28                    rotateLeft(x);
29                }
30                //变色
31                //父节点改为黑色
32                setColor(parentOf(x), BLACK);
33                //右叔节点改为黑色-本身已经为黑色
34                //爷爷节点改为红色
35                setColor(parentOf(parentOf(x)), RED);
36                //右叔为黑，变色后左边黑色多与右边，故以爷爷节点为中心右旋
37                rotateRight(parentOf(parentOf(x)));
38            }
39        } else {//父节点为爷爷节点的右节点
40            //获取左叔节点
41            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
42            //左叔节点为红色(此时父节点也为红色)
43            if (colorOf(y) == RED) {
44                //变色
45                //父节点改为黑色
46                setColor(parentOf(x), BLACK);
47                //左叔节点改为黑色
48                setColor(y, BLACK);
49                //爷爷节点改为红色
50                setColor(parentOf(parentOf(x)), RED);
51                //爷爷节点所在的子树已平衡，所以让x指向爷爷节点，继续往上调整
52                x = parentOf(parentOf(x));
53            } else {
54                //父亲节点在爷爷节点的右边，而x在父亲节点的左边，则需要调整到同一侧
55                if (x == leftOf(parentOf(x))) {
56                    //x指向父节点
57                    x = parentOf(x);
58                    //以x进行右旋
59                    rotateRight(x);
60                }
61                //变色
62                //父节点改为黑色
63                setColor(parentOf(x), BLACK);
64                //左叔节点改为黑色-本身已经为黑色
65                //爷爷节点改为红色
66                setColor(parentOf(parentOf(x)), RED);
67                //左叔为黑，变色后右边黑色多与左边，故以爷爷节点为中心左旋
68                rotateLeft(parentOf(parentOf(x)));
69            }
70        }
71    }
72    //根节点设置为黑色
73    root.color = BLACK;
74}
复制代码

3、添加元素流程图：

4、添加元素精简流程图：

通过上述流程图可以看出，红黑树的调整是采用局部平衡的方式，从下往上依次处理，最终达到整棵树的平衡。

5、实践：

依次插入2、3、4、5、7、8、16、15、14、10、12，画出红黑树插入过程。

上述例子，涵盖了元素插入中遇到的所有情况。相信通过学习优化后的流程图，对于红黑树的元素插入问题，大家的思路是足够清晰的。

总结

本文主要是通过二分查找树的缺陷，引出了红黑树的说明。通过分析TreeMap插入元素的源码，整理出红黑树调整的流程图，最后通过示例来加深对于红黑树的理解。

此时，再回到BST中的缺陷问题，红黑树是如何进行解决的，想必大家都已经有了答案。

文章的最后，感谢大家的支持，如有疑问，欢迎大家留言，一起讨论和学习。