TreeMap分析(中)

2018-06-18 00:42:41来源：未知阅读 ()

通过上篇文章，大家已经能够理解红黑树的基础数据结构，那么这篇文章就来分析下，在红黑树中插入一个结点后，内部数据结构发生了哪些变化。

TreeMap插入某个结点的源码分析

 1     /**
 2      * 插入节点,并平衡红黑树的操作
 3      * 如果原先map中已经有该key对应的键值对，则替换原先该key对应的value为新的value
 4      * 如果原先map中没有该key对应的键值对，则在map中新插入一个该key和value对应的键值对
 5      *
 6      * @param key 键
 7      * @param value 新值
 8      *
 9      * @return 返回原先的值 或者 null
10      * 
11      * @throws ClassCastException 如果用户传入了一个不可和其他key比较的key（违反泛型约定），则抛出该异常
12      * @throws NullPointerException key传入了null，则报此异常
13      */
14     public V put(K key, V value) {
15         Entry<K,V> t = root;   //获取根节点
16         if (t == null) {  //如果根节点为空，则当前的树还没有初始化
17             compare(key, key); // 检查key的类型以及是否为null
18 
19             root = new Entry<>(key, value, null); //根据key和value创建一个黑色新节点作为树的根节点
20             size = 1;  //结点总数+1
21             modCount++;
22             return null;  //直接返回
23         }
24         //根节点不为空
25         int cmp;  //结点的比较结果  >0 OR <0 OR =0
26         Entry<K,V> parent;
27         // 区分是使用key的自然排序进行结点比较 还是 使用用户传入的比较器进行结点的比较
28         Comparator<? super K> cpr = comparator;
29         if (cpr != null) {  //如果用户传入了自定义比较器
30             do {
31                 parent = t;  //每次进行比较的节点，一开始t变量保存的是树的根节点
32                 cmp = cpr.compare(key, t.key); //使用自定义比较器的compare方法，对传入的结点和当前遍历到结点的key进行比较
33                 if (cmp < 0)  //如果传入节点的key比当前遍历到节点的key小
34                     t = t.left;  //把下次进行比较的节点设置为当前遍历到的节点的左子节点
35                 else if (cmp > 0)  //如果传入节点的key比当前遍历到节点的key大
36                     t = t.right; //把下次进行比较的节点设置为当前遍历到的节点的右子节点
37                 else  //如果传入节点的key和当前遍历到节点的key一样大
38                     return t.setValue(value);  //说明这是一个替换原有key对应的value的操作,替换完成后直接返回（不需要再进行下面的插入操作）
39             } while (t != null);  //直到遍历到某一个叶子结点才结束,最终t变量保存的是当前遍历到的叶子节点
40         }
41         else {  //没有自定义比较器，使用key的自然排序进行比较
42             if (key == null)
43                 throw new NullPointerException();  //如果传入key为null，则报异常
44                 Comparable<? super K> k = (Comparable<? super K>) key;
45             do {
46                 parent = t;  //每次进行比较的节点，一开始t变量保存的是树的根节点
47                 cmp = k.compareTo(t.key); //使用Comparable接口的compareTo方法，对传入的结点和当前遍历到结点的key进行比较
48                 if (cmp < 0)  //以下步骤和上面if的步骤完全相同，不再赘述
49                     t = t.left;
50                 else if (cmp > 0)
51                     t = t.right;
52                 else
53                     return t.setValue(value);
54             } while (t != null);
55         }
56         //执行到这里说明遍历了整个树后没有发现存在与传入key相同的键值对，则需要将传入的键值对插入到树中
57         Entry<K,V> e = new Entry<>(key, value, parent);  //根据当前传入的key和value新建一个黑色节点
58         if (cmp < 0)  //如果之前最后一次比较的结果是传入的key比当时叶子结点的key小
59             parent.left = e;  //那么就将当时叶子结点的左子结点设置为当前传入的结点，当前传入的结点变为新的叶子节点
60         else  //如果之前最后一次比较的结果是传入的key比当时叶子结点的key大
61             parent.right = e;  //那么就将当时叶子结点的右子结点设置为当前传入的结点，当前传入的结点变为新的叶子节点
62         
63         fixAfterInsertion(e);  //红黑树的核心方法:在插入后通过左旋、右旋、变色将当前树变成符合红黑树规定的树
64         
65         size++;  //节点总数+1
66         modCount++;
67         return null;  //返回null
68     }

View Code

逻辑还是比较简单的，只要区分两点即可：

1.比较规则是使用key的自然排序进行比较还是使用用户自定义的排序规则进行比较。

2.原来的红黑树中是否已经存在这次插入结点key对应的结点？如果是，则此次操作其实是更新旧值的操作；否则就是新增一个结点的操作。

这里有个需要着重理解的方法，在第 63 行的 fixAfterInsertion(e) 方法。这个方法是红黑树新增一个结点的核心方法。

要理解这个方法，首先需要先了解一些预备知识。

关于树的旋转

之前已经说过，因为红黑树自身的特性，其在插入和删除结点后还要通过旋转、着色的操作来使整个树的定义符合红黑树的定义。

着色很好理解，无非就是更改结点为红色或黑色，那么关于树的旋转操作，大家是否还记得上大学时老师在黑板上画了好多树的左旋、右旋图呢?

我在这儿就稍微介绍下树的旋转相关的知识吧。

以树的右旋转为例，先看一张图：

图中描述的是针对a结点的一次右旋操作。

然后是右旋操作的源码：

 1     /** 树的右旋操作 */
 2     private void rotateRight(Entry<K,V> p) {
 3         if (p != null) {   //如果待右旋节点p不为空
 4             Entry<K,V> l = p.left;  //获取待右旋节点p的左子节点l
 5             p.left = l.right;  //将p的左子节点指向l的右子节点
 6             //l的右子节点不为空
 7             if (l.right != null) l.right.parent = p; //l的右子节点的父节点指向p（p与l的右子节点建立父子节点关系）
 8             l.parent = p.parent;  //l的父节点指向p的父节点(相当于l取代p的位置)
 9             if (p.parent == null) //p父节点是否为空?
10                 root = l;  //p就是根节点，则将当前根节点变更为l
11             else if (p.parent.right == p) //p是否为其父节点的右子节点?
12                 p.parent.right = l;  //p的父节点的右子节点指向l
13             else p.parent.left = l;   //p的父节点的左子节点指向l
14             l.right = p;  //l的右子节点指向p
15             p.parent = l;  //p的父节点指向l
16         }
17     }

源码中的P变量就是上图的a结点，l变量就是上图的b结点，大家可以对照源码和图，在纸上将图中的节点一步一步按照源码的操作画出来，这样比较容易理解。

左旋的操作和右旋是相似的，就不再啰嗦了，大家可以把上图中的右旋后的树作为基础，左旋后得到的就是原先的树。左旋源码如下：

 1     /** 树的左旋操作 */
 2     private void rotateLeft(Entry<K,V> p) {
 3         if (p != null) {
 4             Entry<K,V> r = p.right;
 5             p.right = r.left;
 6             if (r.left != null)
 7                 r.left.parent = p;
 8             r.parent = p.parent;
 9             if (p.parent == null)
10                 root = r;
11             else if (p.parent.left == p)
12                 p.parent.left = r;
13             else
14                 p.parent.right = r;
15             r.left = p;
16             p.parent = r;
17         }
18     }

了解树的旋转操作以后，还需要了解一个小知识。因为红黑树本身是一棵二叉树，二叉树的每个结点最多有两个子结点（左子结点和右子结点）

那么在插入一个结点时，可能插入的结点是左子结点，也可能插入的是右子结点，如下图：

因为结点3和结点8都是在根结点10的左子结点下插入的，所以这种插入方式称之为左子树插入。

上图中左边插入的结点3是结点6的左子结点，这种情况我们称为左子树外侧插入；

而右边的结点8是结点6的右子结点，这种情况我们称为左子树内侧插入。

当然，右子树插入，右子树外侧、内侧插入，聪明如大家，应该不难自行推导出来吧~~

OK，到这里关于红黑树插入结点的前置知识已经介绍完毕，接下来就要分析插入结点的核心源码了 : )

红黑树插入结点核心方法源码分析

 1     /**  平衡树的相关操作  */
 2     
 3     /**  返回当前节点的颜色，如果节点为空则默认返回黑色 */
 4     private static <K,V> boolean colorOf(Entry<K,V> p) {
 5         return (p == null ? BLACK : p.color);
 6     }
 7 
 8     /**  返回当前节点的父节点，没有父节点则返回空 */
 9     private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
10         return (p == null ? null: p.parent);
11     }
12 
13     /**  给当前结点设置颜色  */
14     private static <K,V> void setColor(Entry<K,V> p, boolean c) {
15         if (p != null)
16             p.color = c;
17     }
18 
19     /**  返回当前节点的左子节点，没有左子节点则返回空 */
20     private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
21         return (p == null) ? null: p.left;
22     }
23 
24     /**  返回当前节点的右子节点，没有右子节点则返回空 */
25     private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
26         return (p == null) ? null: p.right;
27     }
28 
29 
30    /**
31      * 树插入一个新结点后，将其根据红黑树的规则进行修正
32      * @param x   当前插入树的节点
33      */
34     private void fixAfterInsertion(Entry<K,V> x) {
35         //默认将当前插入树的节点颜色设置为红色，为什么???
36         //因为红黑树有一个特性: "从根节点到所有叶子节点上的黑色节点数量是相同的"
37         //如果当前插入的节点是黑色的，那么必然会违反这个特性，所以必须将插入节点的颜色先设置为红色
38         x.color = RED;
39         //第一次遍历时，x变量保存的是当前新插入的节点
40         //为什么要用while循环?
41         //因为在旋转的过程中可能还会出现父子节点均为红色的情况，所以要不断往上遍历直至整个树都符合红黑树的规则
42         while (x != null && x != root && x.parent.color == RED) { //如果当前节点不为空且不是根节点，并且当前节点的父节点颜色为红色
43             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //如果当前节点的父节点等于当前节点父节点的父节点的左子节点（即当前节点为左子树插入）
44                 
45                 Entry<K,V> y = rightOf(parentOf(parentOf(x)));  //获取当前节点的叔父节点(和当前插入节点的父节点同辈的另外那个节点)
46                 if (colorOf(y) == RED) {  //如果叔父节点的颜色为红色
47                     //以下4步用来保证不会连续出现两个红色节点
48                     setColor(parentOf(x), BLACK);  //将当前节点的父节点设置为黑色
49                     setColor(y, BLACK);  //将当前节点的叔父节点设置为黑色
50                     setColor(parentOf(parentOf(x)), RED);  //将当前节点的祖父节点设置为红色
51                     x = parentOf(parentOf(x));  //当前遍历节点变更为当前节点的祖父节点
52                 } else {  //如果叔父节点的颜色为黑色,或没有叔父节点
53                     if (x == rightOf(parentOf(x))) {  //如果当前节点为左子树内侧插入
54                         x = parentOf(x);  //将x变更为当前节点的父节点
55                         rotateLeft(x);  //对当前节点的父节点进行一次左旋操作（旋转完毕后x对应的就是最左边的叶子节点）
56                     }
57                     //如果当前节点为左子树外侧插入
58                     setColor(parentOf(x), BLACK); //将当前节点的父节点设置为黑色
59                     setColor(parentOf(parentOf(x)), RED); //将当前节点的祖父节点设置为红色
60                     rotateRight(parentOf(parentOf(x)));  //对当前节点的祖父节点进行一次右旋
61                 }
62             } else {  //当前节点为右子树插入
63                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));  //以下步骤与上面基本相似，只是旋转方向相反，不再赘述
64                 if (colorOf(y) == RED) {
65                     setColor(parentOf(x), BLACK);
66                     setColor(y, BLACK);
67                     setColor(parentOf(parentOf(x)), RED);
68                     x = parentOf(parentOf(x));
69                 } else {
70                     if (x == leftOf(parentOf(x))) {
71                         x = parentOf(x);
72                         rotateRight(x);
73                     }
74                     setColor(parentOf(x), BLACK);
75                     setColor(parentOf(parentOf(x)), RED);
76                     rotateLeft(parentOf(parentOf(x)));
77                 }
78             }
79         }
80         root.color = BLACK;//注意在旋转的过程中可能将根节点变更为红色的，但红黑树的特性要求根节点必须为黑色，所以无论如何最后总要执行这行代码,将根节点设置为黑色
81     }