1010cc时时彩标准版 > 三分时时彩1010CC > TreeMap源码分析,TreeMap完全剖判

原标题:TreeMap源码分析,TreeMap完全剖判

浏览次数:160 时间:2019-08-13

图解集合7:红黑树概念、红黑树的插入及旋转操作详细解读,红黑解读

原文地址

 

初识TreeMap

之前的文章讲解了两种Map,分别是HashMap与LinkedHashMap,它们保证了以O(1)的时间复杂度进行增、删、改、查,从存储角度考虑,这两种数据结构是非常优秀的。另外,LinkedHashMap还额外地保证了Map的遍历顺序可以与put顺序一致,解决了HashMap本身无序的问题。

尽管如此,HashMap与LinkedHashMap还是有自己的局限性----它们不具备统计性能,或者说它们的统计性能时间复杂度并不是很好才更准确,所有的统计必须遍历所有Entry,因此时间复杂度为O(N)。比如Map的Key有1、2、3、4、5、6、7,我现在要统计:

就类似这些操作,HashMap和LinkedHashMap做得比较差,此时我们可以使用TreeMap。TreeMap的Key按照自然顺序进行排序或者根据创建映射时提供的Comparator接口进行排序。TreeMap为增、删、改、查这些操作提供了log(N)的时间开销,从存储角度而言,这比HashMap与LinkedHashMap的O(1)时间复杂度要差些;但是在统计性能上,TreeMap同样可以保证log(N)的时间开销,这又比HashMap与LinkedHashMap的O(N)时间复杂度好不少。

因此总结而言:如果只需要存储功能,使用HashMap与LinkedHashMap是一种更好的选择;如果还需要保证统计性能或者需要对Key按照一定规则进行排序,那么使用TreeMap是一种更好的选择。

 

红黑树的一些基本概念

在讲TreeMap前还是先说一下红黑树的一些基本概念,这样可以更好地理解之后TreeMap的源代码。

二叉查找树是在生成的时候是非常容易失衡的,造成的最坏情况就是一边倒(即只有左子树/右子树),这样会导致树检索的效率大大降低。(关于树和二叉查找树可以看我之前写的一篇文章树型结构)

红黑树是为了维护二叉查找树的平衡而产生的一种树,根据维基百科的定义,红黑树有五个特性,但我觉得讲得不太易懂,我自己总结一下,红黑树的特性大致有三个(换句话说,插入、删除节点后整个红黑树也必须满足下面的三个性质,如果不满足则必须进行旋转):

上述的性质约束了红黑树的关键:从根到叶子的最长可能路径不多于最短可能路径的两倍长。得到这个结论的理由是:

此时(2)正好是(1)的两倍长。结果就是这个树大致上是平衡的,因为比如插入、删除和查找某个值这样的操作最坏情况都要求与树的高度成比例,这个高度的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树,最终保证了红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除

下面展示一张红黑树的实例图:

1010cc时时彩标准版 1

可以看到根节点到所有NULL LEAF节点(即叶子节点)所经过的黑色节点都是2个。

另外从这张图上我们还能得到一个结论:红黑树并不是高度的平衡树。所谓平衡树指的是一棵空树或它的左右两个子树的高度差的绝对值不超过1,但是我们看:

  • 最左边的路径0026-->0017-->0012-->0010-->0003-->NULL LEAF,它的高度为5
  • 最后边的路径0026-->0041-->0047-->NULL LEAF,它的高度为3

左右子树的高度差值为2,因此红黑树并不是高度平衡的,它放弃了高度平衡的特性而只追求部分平衡,这种特性降低了插入、删除时对树旋转的要求,从而提升了树的整体性能。而其他平衡树比如AVL树虽然查找性能为性能是O(logn),但是为了维护其平衡特性,可能要在插入、删除操作时进行多次的旋转,产生比较大的消耗。

 

四个关注点在LinkedHashMap上的答案

关 注 点 结  论
TreeMap是否允许键值对为空 Key不允许为空,Value允许为空 
TreeMap是否允许重复数据 Key重复会覆盖,Value允许重复 
TreeMap是否有序 按照Key的自然顺序排序或者Comparator接口指定的排序算法进行排序 
TreeMap是否线程安全  非线程安全

 

TreeMap基本数据结构

TreeMap基于红黑树实现,既然是红黑树,那么每个节点中除了Key-->Value映射之外,必然存储了红黑树节点特有的一些内容,它们是:

TreeMap的节点Java代码定义为:

1 static final class Entry<K,V> implements Map.Entry<K,V> {
2         K key;
3         V value;
4         Entry<K,V> left = null;
5         Entry<K,V> right = null;
6         Entry<K,V> parent;
7         boolean color = BLACK;
8         ...
9 }

由于颜色只有红色和黑色两种,因此颜色可以使用布尔类型(boolean)来表示,黑色表示为true,红色为false。

 

TreeMap添加数据流程总结

首先看一下TreeMap如何添加数据,测试代码为:

 1 public class MapTest {
 2 
 3     @Test
 4     public void testTreeMap() {
 5         TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
 6         treeMap.put(10, "10");
 7         treeMap.put(85, "85");
 8         treeMap.put(15, "15");
 9         treeMap.put(70, "70");
10         treeMap.put(20, "20");
11         treeMap.put(60, "60");
12         treeMap.put(30, "30");
13         treeMap.put(50, "50");
14 
15         for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
16             System.out.println(entry.getKey()   ":"   entry.getValue());
17         }
18     }
19     
20 }

本文接下来的内容会给出插入每条数据之后红黑树的数据结构是什么样子的。首先看一下treeMap的put方法的代码实现:

 1 public V put(K key, V value) {
 2     Entry<K,V> t = root;
 3     if (t == null) {
 4         compare(key, key); // type (and possibly null) check
 5 
 6         root = new Entry<>(key, value, null);
 7         size = 1;
 8         modCount  ;
 9         return null;
10     }
11     int cmp;
12     Entry<K,V> parent;
13     // split comparator and comparable paths
14     Comparator<? super K> cpr = comparator;
15     if (cpr != null) {
16         do {
17             parent = t;
18             cmp = cpr.compare(key, t.key);
19             if (cmp < 0)
20                 t = t.left;
21             else if (cmp > 0)
22                 t = t.right;
23             else
24                 return t.setValue(value);
25         } while (t != null);
26     }
27     else {
28         if (key == null)
29             throw new NullPointerException();
30         Comparable<? super K> k = (Comparable<? super K>) key;
31         do {
32             parent = t;
33             cmp = k.compareTo(t.key);
34             if (cmp < 0)
35                 t = t.left;
36             else if (cmp > 0)
37                 t = t.right;
38             else
39                 return t.setValue(value);
40         } while (t != null);
41     }
42     Entry<K,V> e = new Entry<>(key, value, parent);
43     if (cmp < 0)
44         parent.left = e;
45     else
46         parent.right = e;
47     fixAfterInsertion(e);
48     size  ;
49     modCount  ;
50     return null;
51 }

从这段代码,先总结一下TreeMap添加数据的几个步骤:

第1~第5步都没有什么问题,红黑树最核心的应当是第6步插入数据之后进行的修复工作,对应的Java代码是TreeMap中的fixAfterInsertion方法,下面看一下put每个数据之后TreeMap都做了什么操作,借此来理清TreeMap的实现原理。

 

put(10, "10")

首先是put(10, "10"),由于此时TreeMap中没有任何节点,因此10为根且根节点为黑色节点,put(10, "10")之后的数据结构为:

1010cc时时彩标准版 2

 

put(85, "85")

接着是put(85, "85"),这一步也不难,85比10大,因此在10的右节点上,但是由于85不是根节点,因此会执行fixAfterInsertion方法进行数据修正,看一下fixAfterInsertion方法代码实现:

 1 private void fixAfterInsertion(Entry<K,V> x) {
 2     x.color = RED;
 3 
 4     while (x != null && x != root && x.parent.color == RED) {
 5         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
 6             Entry<K,V> y = rightOf(parentOf(parentOf(x)));
 7             if (colorOf(y) == RED) {
 8                 setColor(parentOf(x), BLACK);
 9                 setColor(y, BLACK);
10                 setColor(parentOf(parentOf(x)), RED);
11                 x = parentOf(parentOf(x));
12             } else {
13                 if (x == rightOf(parentOf(x))) {
14                     x = parentOf(x);
15                     rotateLeft(x);
16                 }
17                 setColor(parentOf(x), BLACK);
18                 setColor(parentOf(parentOf(x)), RED);
19                 rotateRight(parentOf(parentOf(x)));
20             }
21         } else {
22             Entry<K,V> y = leftOf(parentOf(parentOf(x)));
23             if (colorOf(y) == RED) {
24                 setColor(parentOf(x), BLACK);
25                 setColor(y, BLACK);
26                 setColor(parentOf(parentOf(x)), RED);
27                 x = parentOf(parentOf(x));
28             } else {
29                 if (x == leftOf(parentOf(x))) {
30                     x = parentOf(x);
31                     rotateRight(x);
32                 }
33                 setColor(parentOf(x), BLACK);
34                 setColor(parentOf(parentOf(x)), RED);
35                 rotateLeft(parentOf(parentOf(x)));
36             }
37         }
38     }
39     root.color = BLACK;
40 }

我们看第2行的代码,它将默认的插入的那个节点着色成为红色,这很好理解:

根据红黑树的性质(3),红黑树要求从根节点到叶子所有叶子节点上经过的黑色节点个数是相同的,因此如果插入的节点着色为黑色,那必然有可能导致某条路径上的黑色节点数量大于其他路径上的黑色节点数量,因此默认插入的节点必须是红色的,以此来维持红黑树的性质(3)

当然插入节点着色为红色节点后,有可能导致的问题是违反性质(2),即出现连续两个红色节点,这就需要通过旋转操作去改变树的结构,解决这个问题。

接着看第4行的判断,前两个条件都满足,但是因为85这个节点的父节点是根节点的,根节点是黑色节点,因此这个条件不满足,while循环不进去,直接执行一次30行的代码给根节点着色为黑色(因为在旋转过程中有可能导致根节点为红色,而红黑树的根节点必须是黑色,因此最后不管根节点是不是黑色,都要重新着色确保根节点是黑色的)。

那么put(85, "85")之后,整个树的结构变为:

1010cc时时彩标准版 3

 

fixAfterInsertion方法流程

在看put(15, "15")之前,必须要先过一下fixAfterInsertion方法。第5行~第21行的代码和第21行~第38行的代码是一样的,无非一个是操作左子树另一个是操作右子树而已,因此就看前一半:

 1 while (x != null && x != root && x.parent.color == RED) {
 2     if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
 3         Entry<K,V> y = rightOf(parentOf(parentOf(x)));
 4         if (colorOf(y) == RED) {
 5             setColor(parentOf(x), BLACK);
 6             setColor(y, BLACK);
 7             setColor(parentOf(parentOf(x)), RED);
 8             x = parentOf(parentOf(x));
 9         } else {
10             if (x == rightOf(parentOf(x))) {
11                 x = parentOf(x);
12                 rotateLeft(x);
13             }
14             setColor(parentOf(x), BLACK);
15             setColor(parentOf(parentOf(x)), RED);
16             rotateRight(parentOf(parentOf(x)));
17         }
18     }
19     ....
20 }

第2行的判断注意一下,用语言描述出来就是:判断当前节点的父节点与当前节点的父节点的父节点的左子节点是否同一个节点。翻译一下就是:当前节点是否左子节点插入,关于这个不明白的我就不解释了,可以自己多思考一下。对这整段代码我用流程图描述一下:

1010cc时时彩标准版 4

这里有一个左子树内侧插入与左子树点外侧插入的概念,我用图表示一下:

1010cc时时彩标准版 5

其中左边的是左子树外侧插入,右边的是左子树内侧插入,可以从上面的流程图上看到,对于这两种插入方式的处理是不同的,区别是后者也就是左子树内侧插入多一步左旋操作

能看出,红黑树的插入最多只需要进行两次旋转,至于红黑树的旋转,后面结合代码进行讲解。

 

put(15, "15")

看完fixAfterInsertion方法流程之后,继续添加数据,这次添加的是put(15, "15"),15比10大且比85小,因此15最终应当是85的左子节点,默认插入的是红色节点,因此首先将15作为红色节点插入85的左子节点后的结构应当是:

1010cc时时彩标准版 6

但是显然这里违反了红黑树的性质(2),即连续出现了两个红色节点,因此此时必须进行旋转。回看前面fixAfterInsertion的流程,上面演示的是左子树插入流程,右子树一样,可以看到这是右子树内侧插入,需要进行两次旋转操作:

旋转是红黑树中最难理解也是最核心的操作,右旋和左旋是对称的操作,我个人的理解,以右旋为例,对某个节点x进行右旋,其实质是:

  • 降低左子树的高度,增加右子树的高度
  • 将x变为当前位置的右子节点

左旋是同样的道理,在旋转的时候一定要记住这两句话,这将会帮助我们清楚地知道在不同的场景下旋转如何进行。

先看一下(1)也就是"对新插入节点的父节点进行一次右旋操作",源代码为rotateRight方法:

 1 private void rotateRight(Entry<K,V> p) {
 2     if (p != null) {
 3         Entry<K,V> l = p.left;
 4         p.left = l.right;
 5         if (l.right != null) l.right.parent = p;
 6         l.parent = p.parent;
 7         if (p.parent == null)
 8            root = l;
 9         else if (p.parent.right == p)
10             p.parent.right = l;
11         else p.parent.left = l;
12         l.right = p;
13         p.parent = l;
14     }
15 }

右旋流程用流程图画一下其流程:

1010cc时时彩标准版 7

再用一张示例图表示一下右旋各节点的变化,旋转不会改变节点颜色,这里就不区分红色节点和黑色节点了,a是需要进行右旋的节点:

1010cc时时彩标准版 8

左旋与右旋是一个对称的操作,大家可以试试看把右图的b节点进行左旋,就变成了左图了。这里多说一句,旋转一定要说明是对哪个节点进行旋转,网上看很多文章讲左旋、右旋都是直接说旋转之后怎么样怎么样,我认为脱离具体的节点讲旋转是没有任何意义的。

这里可能会有的一个问题是:b有左右两个子节点分别为d和e,为什么右旋的时候要将右子节点e拿到a的左子节点而不是b的左子节点d?

一个很简单的解释是:如果将b的左子节点d拿到a的左子节点,那么b右旋后右子节点指向a,b原来的右子节点e就成为了一个游离的节点,游离于整个数据结构之外

回到实际的例子,对85这个节点进行右旋之后还有一次着色操作(2),分别是将x的父节点着色为黑色,将x的祖父节点着色为红色,那么此时的树形结构应当为:

1010cc时时彩标准版 9

然后对节点10进行一次左旋操作(3),左旋之后的结构为:

1010cc时时彩标准版 10

最后不管根节点是不是黑色,都将根节点着色为黑色,那么插入15之后的数据结构就变为了上图,满足红黑树的三条特性。

 

put(70, "70")

put(70, "70")就很简单了,70是85的左子节点,由于70的父节点以及叔父节点都是红色节点,因此直接将70的父节点85、将70的叔父节点10着色为黑色即可,70这个节点着色为红色,即满足红黑树的特性,插入70之后的结构图为:

1010cc时时彩标准版 11

 

put(20, "20")

put(20, "20"),插入的位置应当是70的左子节点,默认插入红色,插入之后的结构图为:

1010cc时时彩标准版 12

问题很明显,出现了连续两个红色节点,20的插入位置是一种左子树外侧插入的场景,因此只需要进行着色 对节点85进行一次右旋即可,着色 右旋之后数据结构变为:

1010cc时时彩标准版 13

 

put(60, "60")

下面进行put(60, "60")操作,节点60插入的位置是节点20的右子节点,由于节点60的父节点与叔父节点都是红色节点,因此只需要将节点60的父节点与叔父节点着色为黑色,将节点60的组父节点着色为红色即可。

那么put(60, "60")之后的结构为:

1010cc时时彩标准版 14

 

put(30, "30")

put(30, "30"),节点30应当为节点60的左子节点,因此插入节点30之后应该是这样的:

1010cc时时彩标准版 15

显然这里违反了红黑树性质(2)即连续出现了两个红色节点,因此这里要进行旋转。

put(30, "30")的操作和put(15, "15")的操作类似,同样是右子树内侧插入的场景,那么需要进行两次旋转:

右旋 着色 左旋之后,put(30, "30")的结果应当为:

1010cc时时彩标准版 16

 

put(50, "50")

下一个操作是put(50, "50"),节点50是节点60的左子节点,由于节点50的父亲节点与叔父节点都是红色节点,因此只需要将节点50的父亲节点与叔父节点着色为黑色,将节点50的祖父节点着色为红色即可:

1010cc时时彩标准版 17

节点50的父节点与叔父节点都是红色节点(注意不要被上图迷糊了!上图是重新着色之后的结构而不是重新着色之前的结构,重新着色之前的结构为上上图),因此插入节点50只需要进行着色,本身这样的操作是没有任何问题的,但问题的关键在于,着色之后出现了连续的红色节点,即节点30与节点70。这就是为什么fixAfterInsertion方法的方法体是while循环的原因:

1 private void fixAfterInsertion(Entry<K,V> x) {
2     x.color = RED;
3 
4     while (x != null && x != root && x.parent.color == RED) {
5     ...
6     }
7 }

因为这种着色方式是将插入节点的祖父节点着色为红色,因此着色之后必须将当前节点指向插入节点的祖父节点,判断祖父节点与父节点是否连续红色的节点,是就进行旋转,重新让红黑树平衡。

接下来的问题就是怎么旋转了。我们可以把节点15-->节点70-->节点30连起来看,是不是很熟悉?这就是上面重复了两次的右子树内侧插入的场景,那么首先对节点70进行右旋,右旋后的结果为:

1010cc时时彩标准版 18

下一步,节点70的父节点着色为黑色,节点70的祖父节点着色为红色(这一步不理解或者忘了为什么的,可以去看一下之前对于fixAfterInsertion方法的解读),重新着色后的结构为:

1010cc时时彩标准版 19

最后一步,对节点70的父节点节点15进行一次左旋,左旋之后的结构为:

1010cc时时彩标准版 20

重新恢复红黑树的性质:

 

后记

本文通过不断向红黑树的右子树插入数据,演示了红黑树右侧插入时可能出现的各种情况且应当如何处理这些情况,左侧插入同理。

红黑树还是有点难,因此我个人建议在学习红黑树的时候一定要多画(像我个人就画了3张A4纸) 多想,这样才能更好地理解红黑树的原理,尤其是旋转的原理。

TreeMap的插入操作和旋转操作已经讲完,后文会着眼于TreeMap的删除操作以及一些统计操作(比如找到节点比50大的所有节点)是如何实现的。

原文地址...

红黑树的插入操作                                                                    

如果插入第一个节点,我们直接用树根记录这个节点,并设置为黑色,否则作递归查找插入。

默认插入的节点颜色都是红色,因为插入黑色节点会破坏根路径上的黑色节点总数,但即使如此,也会出现连续红色节点的情况。因此在一般的插入操作之后,出现红黑树约束条件不满足的情况(称为失去平衡)时,就必须要根据当前的红黑树的情况做相应的调整。和AVL树的平衡调整通过旋转操作的实现类似,红黑树的调整操作一般都是通过旋转结合节点的变色操作来完成的。

  • 叔父节点是黑色(若是空节点则默认为黑色)

这种情况下通过旋转和变色操作可以使红黑树恢复平衡。但是考虑当前节点n和父节点p的位置又分为四种情况:

A、n是p左子节点,p是g的左子节点。

B、n是p右子节点,p是g的右子节点。

C、n是p左子节点,p是g的右子节点。

D、n是p右子节点,p是g的左子节点。

  • 情况A:n是p左子节点,p是g的左子节点。针对该情况可以通过一次右旋转操作,并将p设为黑色,g设为红色完成重新平衡。

1010cc时时彩标准版 21

右旋操作的步骤是将p挂接在g节点原来的位置(如果g原是根节点,需要考虑边界条件),将p的右子树x挂到g的左子节点,再把g挂在p的右子节点上,完成右旋操作。这里将最终旋转结果的子树的根节点作为旋转轴(p节点),也就是说旋转轴在旋转结束后称为新子树的根节点!

  • 情况B则需要使用左单旋操作来解决平衡问题,方法和情况A类似。

1010cc时时彩标准版 22

  • 情况C:n是p左子节点,p是g的右子节点。针对该情况通过一次左旋,一次右旋操作(旋转轴都是n,注意不是p),并将n设为黑色,g设为红色完成重新平衡。

1010cc时时彩标准版 23

需要注意的是,由于此时新插入的节点是n,它的左右子树x,y都是空节点,但即使如此,旋转操作的结果需要将x,y新的位置设置正确(如果不把p和g的对应分支设置为空节点的话,就会破坏树的结构)。在之后的其他操作中,待旋转的节点n的左右子树可能就不是空节点了。

  • 情况D则需要使用一次右单旋,一次左单旋操作来解决平衡问题,方法和情况C类似。

1010cc时时彩标准版 24

  • 叔父节点是红色

当叔父节点是红色时,则不能直接通过上述方式处理了(把前边的所有情况的u节点看作红色,会发现节点u和g是红色冲突的)。但是我们可以交换g与p,u节点的颜色完成当前冲突的解决。

1010cc时时彩标准版 25

但是仅仅这样做颜色交换是不够的,因为祖父节点g的父节点(记作gp)如果也是红色的话仍然会有冲突(g和gp是连续的红色,违反规则2)。为了解决这样的冲突,我们需要从当前插入点n向根节点root回溯两次。

第一次回溯时处理所有拥有两个红色节点的节点,并按照上图中的方式交换父节点g与子节点p,u的颜色,并暂时忽略gp和p的颜色冲突。如果根节点的两个子节点也是这种情况,则在颜色交换完毕后重新将根节点设置为黑色。

第二次回溯专门处理连续的红色节点冲突。由于经过第一遍的处理,在新插入点n的路径上一定不存在同为红色的兄弟节点了。而仍出现gp和p的红色冲突时,gp的兄弟节点(gu)可以断定为黑色,这样就回归前边讨论的叔父节点为黑色时的情况处理。

1010cc时时彩标准版 26

由于发生冲突的两个红色节点位置可能是任意的,因此会出现上述的四种旋转情况。不过我们把靠近叶子的红色节点(g)看作新插入的节点,这样面对A,B情况则把p的父节点gp作为旋转轴,旋转后gp会是新子树的根,而面对C,D情况时把p作为旋转轴即可,旋转后p为新子树的根(因此可以把四种旋转方式封装起来)。

在第二次回溯时,虽然每次遇到红色冲突旋转后都会提升g和gp节点的位置(与根节点的距离减少),但是无论g和gp谁是新子树的根都不会影响新插入节点n到根节点root路径的回溯,而且一旦新子树的根到达根节点(parent指针为空)就可以停止回溯了。

4.7.3 红黑树节点删除

暂省略;

二 树的操作与源码实现

在文章01Java关于数据结构的实现:表、栈与队列中我们
讨论了ArrayList与LinkedList的实现,它们的瓶颈在于查找效率低下。因而Java集合设计了Set与Map接口,它们在插入、删除与查找等基本操作都有良好的表现。

红黑树的添加原理及TreeMap的put实现

将一个节点添加到红黑树中,通常需要下面几个步骤:

  • 将红黑树当成一颗二叉查找树,将节点插入。这一步比较简单,就跟开始我们自己写的二叉查找树的操作一样,至于为什么可以这样插入,是因为红黑树本身就是一个二叉查找树。
  • 将新插入的节点设置为红色。有没有疑问,为什么新插入的节点一定要是红色的,因为新插入节点为红色,不会违背红黑规则第条,少违背一条就少处理一种情况。
  • 通过旋转和着色,使它恢复平衡,重新变成一颗符合规则的红黑树。

要想知道怎么样进行左旋和右旋,首先就要知道为什么要进行左旋和右旋。我们来对比下红黑树的规则和新插入节点后的情况,看下新插入节点会违背哪些规则。

  1. 节点是红色或黑色。这一点肯定是不会违背的了。
  2. 根节点是黑色。这一点也不会违背了,如果是根节点,只需将根节点插入就好了,因为默认是黑色。
  3. 每个叶节点(NIL节点,空节点)是黑色的。这一点也不会违背的,我们插入的是非空的节点,不会影响空节点。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)。这一点是有可能违背的,我们将新插入的节点都设置成红色,如果其父节点也是红色的话,那就产生冲突了。
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。这一点也不会违背,因为我们将新插入的节点都设置成红色。

了解了红黑树左旋和右旋操作,以及新插入节点主要是可能会违背红黑树的规则后,我们来分析下,添加新节点的过程有哪几种情况:

  1. 新插入节点为根节点。这种情况直接将新插入节点设置为根节点即可,无需进行后续的旋转和着色处理。
  2. 新插入节点的父节点是黑色。这种情况直接将新节点插入即可,不会违背规则。
  3. 新插入节点的父节点是红色。这种情况会违背规则,而这种情况又分为了以下几种,下面进行图解:

①新插入节点N的父节点P和叔叔节点U都是红色。

方法是:将祖父节点G设置为红色,父节点P和叔叔节点U设置为黑色,这时候就看似平衡了。但是,如果祖父节点G的父节点也是红色,这时候又违背规则了,怎么办,方法是:将GPUN这一组看成一个新的节点,按照前面的方案递归;又但是根节点为红就违反规则了,怎么办,方法是直接将根节点设置为黑色(两个连续黑色是没问题的)。

1010cc时时彩标准版 27image.png

②新插入节点N的父节点P是红色,叔叔节点U是黑色或者缺少,且新节点N是P的右孩子。

方法是:左旋父节点P。左旋后N和P角色互换,但是P和N还是连续的两个红色节点,还没有平衡,怎么办,看第三种情况。

1010cc时时彩标准版 28image.png

③新插入节点N的父节点P是红色,叔叔节点U是黑色或者缺少,且新节点N是P的左孩子。

方法是:右旋祖父节点G,然后将P设置为黑色,G设置为红色,达到平衡。此时父节点P是黑色,所有不用担心P的父节点是红色。

当然上面说的三种情况都是基于一个前提:新插入节点N的父节点P是祖父节点G的左孩子,如果P是G的右孩子又是什么情况呢?其实情况和上面是相似的,只需要调整左旋还是右旋,这里就不细讲了。

TreeMap的实现:

public V put(K key, V value) { // 根节点 Entry<K,V> t = root; // 如果根节点为空,则直接创建一个根节点,返回 if (t == null) { compare; // type check root = new Entry<K,V>(key, value, null); size = 1; modCount  ; return null; } // 记录比较结果 int cmp; Entry<K,V> parent; // split comparator and comparable paths // 当前使用的比较器 Comparator<? super K> cpr = comparator ; // 如果比较器不为空,就是用指定的比较器来维护TreeMap的元素顺序 if (cpr != null) { // do while循环,查找key要插入的位置(也就是新节点的父节点是谁) do { // 记录上次循环的节点t parent = t; // 比较当前节点的key和新插入的key的大小 cmp = cpr.compare(key, t. key); // 新插入的key小的话,则以当前节点的左孩子节点为新的比较节点 if (cmp < 0) t = t. left; // 新插入的key大的话,则以当前节点的右孩子节点为新的比较节点 else if (cmp > 0) t = t. right; else // 如果当前节点的key和新插入的key相等的话,则覆盖map的value,返回 return t.setValue; // 只有当t为null,也就是没有要比较节点的时候,代表已经找到新节点要插入的位置 } while (t != null); } else { // 如果比较器为空,则使用key作为比较器进行比较 // 这里要求key不能为空,并且必须实现Comparable接口 if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; // 和上面一样,喜欢查找新节点要插入的位置 do { parent = t; cmp = k.compareTo; if (cmp < 0) t = t. left; else if (cmp > 0) t = t. right; else return t.setValue; } while (t != null); } // 找到新节点的父节点后,创建节点对象 Entry<K,V> e = new Entry<K,V>(key, value, parent); // 如果新节点key的值小于父节点key的值,则插在父节点的左侧 if (cmp < 0) parent. left = e; // 如果新节点key的值大于父节点key的值,则插在父节点的右侧 else parent. right = e; // 插入新的节点后,为了保持红黑树平衡,对红黑树进行调整 fixAfterInsertion; // map元素个数 1 size  ; modCount  ; return null;} /** 新增节点后对红黑树的调整方法 */private void fixAfterInsertion(Entry<K,V> x) { // 将新插入节点的颜色设置为红色 x. color = RED; // while循环,保证新插入节点x不是根节点或者新插入节点x的父节点不是红色(这两种情况不需要调整) while (x != null && x != root && x. parent.color == RED) { // 如果新插入节点x的父节点是祖父节点的左孩子 if (parentOf == leftOf(parentOf (parentOf { // 取得新插入节点x的叔叔节点 Entry<K,V> y = rightOf(parentOf (parentOf; // 如果新插入x的父节点是红色-------------------① if (colorOf == RED) { // 将x的父节点设置为黑色 setColor(parentOf , BLACK); // 将x的叔叔节点设置为黑色 setColor; // 将x的祖父节点设置为红色 setColor(parentOf (parentOf; // 将x指向祖父节点,如果x的祖父节点的父节点是红色,按照上面的步奏继续循环 x = parentOf(parentOf ; } else { // 如果新插入x的叔叔节点是黑色或缺少,且x的父节点是祖父节点的右孩子-------------------② if (x == rightOf( parentOf { // 左旋父节点 x = parentOf; rotateLeft; } // 如果新插入x的叔叔节点是黑色或缺少,且x的父节点是祖父节点的左孩子-------------------③ // 将x的父节点设置为黑色 setColor(parentOf , BLACK); // 将x的祖父节点设置为红色 setColor(parentOf (parentOf; // 右旋x的祖父节点 rotateRight( parentOf(parentOf ; } } else { // 如果新插入节点x的父节点是祖父节点的右孩子,下面的步奏和上面的相似,只不过左旋右旋的区分,不在细讲 Entry<K,V> y = leftOf(parentOf (parentOf; if (colorOf == RED) { setColor(parentOf , BLACK); setColor; setColor(parentOf (parentOf; x = parentOf(parentOf ; } else { if (x == leftOf( parentOf { x = parentOf; rotateRight; } setColor(parentOf , BLACK); setColor(parentOf (parentOf; rotateLeft( parentOf(parentOf ; } } } // 最后将根节点设置为黑色,不管当前是不是红色,反正根节点必须是黑色 root.color = BLACK;}/** * 对红黑树的节点进行左旋转 * * 左旋示意图: * px px * / / * x y * /  ---- /  * lx y x ry * /  /  * ly ry lx ly * */private void rotateLeft(Entry<K,V> p) { if (p != null) { // 取得要选择节点p的右孩子 Entry<K,V> r = p. right; // "p"和"r的左孩子"的相互指向... // 将"r的左孩子"设为"p的右孩子" p. right = r.left ; // 如果r的左孩子非空,将"p"设为"r的左孩子的父亲" if (r.left != null) r. left.parent = p; // "p的父亲"和"r"的相互指向... // 将"p的父亲"设为"y的父亲" r. parent = p.parent ; // 如果"p的父亲"是空节点,则将r设为根节点 if (p.parent == null) root = r; // 如果p是它父节点的左孩子,则将r设为"p的父节点的左孩子" else if (p.parent. left == p) p. parent.left = r; else // 如果p是它父节点的左孩子,则将r设为"p的父节点的左孩子" p. parent.right = r; // "p"和"r"的相互指向... // 将"p"设为"r的左孩子" r. left = p; // 将"p的父节点"设为"r" p. parent = r; }}/** * 对红黑树的节点进行右旋转 * * 右旋示意图: * py py * / / * y x * /  ---- /  * x ry lx y * /  /  * lx rx rx ry * */private void rotateRight(Entry<K,V> p) { if (p != null) { // 取得要选择节点p的左孩子 Entry<K,V> l = p. left; // 将"l的右孩子"设为"p的左孩子" p. left = l.right ; // 如果"l的右孩子"不为空的话,将"p"设为"l的右孩子的父亲" if (l.right != null) l. right.parent = p; // 将"p的父亲"设为"l的父亲" l. parent = p.parent ; // 如果"p的父亲"是空节点,则将l设为根节点 if (p.parent == null) root = l; // 如果p是它父节点的右孩子,则将l设为"p的父节点的右孩子" else if (p.parent. right == p) p. parent.right = l; //如果p是它父节点的左孩子,将l设为"p的父节点的左孩子" else p.parent .left = l; // 将"p"设为"l的右孩子" l. right = p; // 将"l"设为"p父节点" p. parent = l; }}

单纯的看代码和注释,绝对会发出,cha这是什么乱七八糟的,任谁也看不懂,所以一定要结合上面的图解,不懂了就看看图,然后动手画一下。如果你告诉我,还是没有懂,没问题可以理解,这里有一位大神录制的红黑树增加元素视频动画,来吧,

我是天王盖地虎的分割线                                                             

 

 

 

参考:

4.8 平衡二叉树

前几节中,笔者说过:可以将二叉树简单地理解为一个链表结构。当时,是为了能让各位能对二叉树有一个最直观的理解。

其实,在具体的实现中二叉树确实会形成一个链表结构。

试想下,如果一个二叉树的左子树为空,只有右子树,且右子树中又只有右节点,那么这个二叉树就形成了一个不折不扣的链表。对于二叉查找树来说,二分查找也就失去了原有的性能,变成了顺序查找。即元素的插入顺序是1、2、3、4、5、6的话,即可实现。

为了针对这一情况,平衡二叉树出现了,它要求左右子树的高度差的绝对值不能大于1,也就是说左右子树的高度差只能为-1、0、1。

1010cc时时彩标准版 29

put

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{

    public V put(K key, V value) {
            //找到根节点
            TreeMapEntry<K,V> t = root;
            //如果根节点为空,则设置该元素为
            if (t == null) {
                if (comparator != null) {
                    if (key == null) {
                        comparator.compare(key, key);
                    }
                } else {
                    if (key == null) {
                        throw new NullPointerException("key == null");
                    } else if (!(key instanceof Comparable)) {
                        throw new ClassCastException(
                                "Cannot cast"   key.getClass().getName()   " to Comparable.");
                    }
                }

                root = new TreeMapEntry<>(key, value, null);
                //集合大小为1
                size = 1;
                //修改次数自增
                modCount  ;
                return null;
            }
            int cmp;
            TreeMapEntry<K,V> parent;
            //获取比较器
            Comparator<? super K> cpr = comparator;
            //如果比较器不空,则用指定的比较器进行比较
            if (cpr != null) {
                //循环递归,从根节点开始查找插入的位置,即查找的它的父节点,查找方式和我们上面讲的二叉排序树的查找方式相同
                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);
            }
            //如果比较器为坤宁宫,则使用默认的比较器
            else {
                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);
            }
            //根据查找到的父节点,构造节点,并根据比结果将其插入到对应的位置
            TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            //给插入的节点染色
            fixAfterInsertion(e);
            size  ;
            modCount  ;
            return null;
        }
}

插入操作采用了二叉排序树的查找算法,整个流程如下:

  1. 如果当前TreeMap没有根节点,将当前节点作为根节点插入,否则,
  2. 根据提供的比较器(如果没有提供则使用默认的比较器)进行查找比较,查找该节点的插入位置,即它的父节点的位置。
  3. 查找到父节点后,根据比较结果插入到对应位置,并进行染色处理。

TreeMap签名

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable

相比HashMap来说,TreeMap多实现了一个接口NavigableMap,也就是这个接口,决定了TreeMap与HashMap的不同:HashMap的key是无序的,TreeMap的key是有序的。

public interface NavigableMap<K,V> extends SortedMap<K,V>

发现NavigableMap继承了SortedMap,再看SortedMap的签名

public interface SortedMap<K,V> extends Map<K,V>

SortedMap就像其名字那样,说明这个Map是有序的。这个顺序一般是指由Comparable接口提供的keys的自然序(natural ordering),或者也可以在创建SortedMap实例时,指定一个Comparator来决定。 当我们在用集合视角(collection views,与HashMap一样,也是由entrySet、keySet与values方法提供)来迭代一个SortedMap实例时会体现出key的顺序。

  • Comparable一般表示类的自然序,比如定义一个Student类,学号为默认排序
  • Comparator一般表示类在某种场合下的特殊分类,需要定制化排序。比如现在想按照Student类的age来排序

插入SortedMap中的key的类都必须实现Comparable接口(或指定一个comparator),这样才能确定如何比较(通过k1.compareTo或comparator.compare两个key,否则,在插入时,会报ClassCastException的异常。 此外,SortedMap中key的顺序性应该与equals方法保持一致。也就是说k1.compareTo或comparator.compare为true时,k1.equals也应该为true。 介绍完了SortedMap,再来回到我们的NavigableMap上面来。 NavigableMap是JDK1.6新增的,在SortedMap的基础上,增加了一些“导航方法”(navigation methods)来返回与搜索目标最近的元素。例如下面这些方法:

  • lowerEntry,返回所有比给定Map.Entry小的元素
  • floorEntry,返回所有比给定Map.Entry小或相等的元素
  • ceilingEntry,返回所有比给定Map.Entry大或相等的元素
  • higherEntry,返回所有比给定Map.Entry大的元素

红黑树                                                                                 

红黑树顾名思义就是节点是红色或者黑色的平衡二叉树,它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则:

1、每个节点都只能是红色或者黑色

2、根节点是黑色

3、每个叶节点(NIL节点,空节点)是黑色的。

4、如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。所以红黑树它是复杂而高效的,其检索效率O(log n)。

4.1 TreeMap

在Map集合框架中,除了HashMap以外,TreeMap也是我们工作中常用到的集合对象之一。

与HashMap相比,TreeMap是一个能比较元素大小的Map集合,会对传入的key进行了大小排序。其中,可以使用元素的自然顺序,也可以使用集合中自定义的比较器来进行排序;

不同于HashMap的哈希映射,TreeMap底层实现了树形结构,至于具体形态,你可以简单的理解为一颗倒过来的树---根在上--叶在下。如果用计算机术语来说的话,TreeMap实现了红黑树的结构,形成了一颗二叉树。

至于什么是二叉树,什么是红黑树,我们后面再谈,你现在只需要记住它是一颗倒过来的树,就OK了。

1010cc时时彩标准版 30

TreeMap继承于AbstractMap,实现了Map, Cloneable, NavigableMap, Serializable接口。

TreeMap 继承于AbstractMap,而AbstractMap实现了Map接口,并实现了Map接口中定义的方法,减少了其子类继承的复杂度;

TreeMap 实现了Map接口,成为Map框架中的一员,可以包含着key--value形式的元素;

TreeMap 实现了NavigableMap接口,意味着拥有了更强的元素搜索能力;

TreeMap 实现了Cloneable接口,实现了clone()方法,可以被克隆;

TreeMap 实现了Java.io.Serializable接口,支持序列化操作,可通过Hessian协议进行传输;

对于Cloneable, Serializable来说,我们再熟悉不过,基本上Java集合框架中的每一个类都会实现这2个接口,而NavigableMap接口是干什么的,它定义了什么样的功能?接下来,我们就通过NavigableMap的源码来看下!

1010cc时时彩标准版 31

根据上面的截图,我们首先介绍下NavigableMap体系中的SortedMap接口:

对于SortedMap来说,该类是TreeMap体系中的父接口,也是区别于HashMap体系最关键的一个接口。

主要原因就是SortedMap接口中定义的第一个方法---Comparator<? super K> comparator();

该方法决定了TreeMap体系的走向,有了比较器,就可以对插入的元素进行排序了;

public interface SortedMap<K,V> extends Map<K,V> { //返回元素比较器。如果是自然顺序,则返回null; Comparator<? super K> comparator(); //返回从fromKey到toKey的集合:含头不含尾 java.util.SortedMap<K,V> subMap(K fromKey, K toKey); //返回从头到toKey的集合:不包含toKey java.util.SortedMap<K,V> headMap; //返回从fromKey到结尾的集合:包含fromKey java.util.SortedMap<K,V> tailMap(K fromKey); //返回集合中的第一个元素: K firstKey(); //返回集合中的最后一个元素: K lastKey(); //返回集合中所有key的集合: Set<K> keySet(); //返回集合中所有value的集合: Collection<V> values(); //返回集合中的元素映射: Set<Map.Entry<K, V>> entrySet();}

上面介绍了SortedMap接口,而NavigableMap接口又是对SortedMap进一步的扩展:主要增加了对集合内元素的搜索获取操作,例如:返回集合中某一区间内的元素、返回小于大于某一值的元素等类似操作。

public interface NavigableMap<K,V> extends SortedMap<K,V> { //返回小于key的第一个元素: Map.Entry<K,V> lowerEntry; //返回小于key的第一个键: K lowerKey; //返回小于等于key的第一个元素: Map.Entry<K,V> floorEntry; //返回小于等于key的第一个键: K floorKey; //返回大于或者等于key的第一个元素: Map.Entry<K,V> ceilingEntry; //返回大于或者等于key的第一个键: K ceilingKey; //返回大于key的第一个元素: Map.Entry<K,V> higherEntry; //返回大于key的第一个键: K higherKey; //返回集合中第一个元素: Map.Entry<K,V> firstEntry(); //返回集合中最后一个元素: Map.Entry<K,V> lastEntry(); //返回集合中第一个元素,并从集合中删除: Map.Entry<K,V> pollFirstEntry(); //返回集合中最后一个元素,并从集合中删除: Map.Entry<K,V> pollLastEntry(); //返回倒序的Map集合: java.util.NavigableMap<K,V> descendingMap(); NavigableSet<K> navigableKeySet(); //返回Map集合中倒序的Key组成的Set集合: NavigableSet<K> descendingKeySet(); java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive); java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive); java.util.NavigableMap<K,V> tailMap(K fromKey, boolean inclusive); SortedMap<K,V> subMap(K fromKey, K toKey); SortedMap<K,V> headMap; SortedMap<K,V> tailMap(K fromKey);}

其实,NavigableMap的目的很简单、很直接,就是增强了对集合内元素的搜索、获取的功能,当子类TreeMap实现时,自然获取以上的功能;

TreeMap具有如下特点:

  • 不允许出现重复的key;

  • 1010cc时时彩标准版,可以插入null键,null值;

  • 可以对元素进行排序;

  • 无序集合(插入和遍历顺序不一致);

2.1 TreeMap/TreeSet实现原理

TreeSet实际上是基于TreeMap的NavigableSet的实现,它在功能上完全依赖于TreeMap,TreeMap是一个基于红黑树实现的Map,它在存储时对元素进行排序。

因此只要理解了TreeMap实现即可,TreeSet在功能上完全依赖于TreeMap。

TreeMap具有以下特点:

  • TreeMap是一个有序的key-value集合,基于红黑树实现。
  • 没有实现同步

TreeMap实现以下接口:

  • NavigableMap:支持一系列导航方法,比如返回有序的key集合。
  • Cloneable:可以被克隆。
  • Serializable:支持序列化。

TreeMap属性

// 比较器private final Comparator<? super K> comparator;// 红黑树根节点private transient Entry<K,V> root = null;// 集合元素数量private transient int size = 0;// "fail-fast"集合修改记录private transient int modCount = 0;

Entry是树的节点类,我们来看一下Entry的定义:

static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; // 左孩子节点 Entry<K,V> left = null; // 右孩子节点 Entry<K,V> right = null; // 父节点 Entry<K,V> parent; // 红黑树用来表示节点颜色的属性,默认为黑色 boolean color = BLACK; /** * 用key,value和父节点构造一个Entry,默认为黑色 */ Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } public K getKey() { return key ; } public V getValue() { return value ; } public V setValue { V oldValue = this.value ; this.value = value; return oldValue; } public boolean equals { 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; }} 

Entry类理解起来比较简单(因为我们前面看过很多的Entry类了),主要是定义了树的孩子和父亲节点引用,和红黑颜色属性,并对equals和hashCode进行重写,以利于比较是否相等。

TreeMap数据结构                                                                    

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap继承AbstractMap,实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合, NavigableMap则意味着它支持一系列的导航方法,具备针对给定搜索目标返回最接近匹配项的导航方法 。

TreeMap中同时也包含了如下几个重要的属性:

        //比较器,因为TreeMap是有序的,通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
        private final Comparator<? super K> comparator;
        //TreeMap红-黑节点,为TreeMap的内部类
        private transient Entry<K,V> root = null;
        //容器大小
        private transient int size = 0;
        //TreeMap修改次数
        private transient int modCount = 0;
        //红黑树的节点颜色--红色
        private static final boolean RED = false;
        //红黑树的节点颜色--黑色
        private static final boolean BLACK = true;

对于叶子节点Entry是TreeMap的内部类,它有几个重要的属性:

//键
        K key;
        //值
        V value;
        //左孩子
        Entry<K,V> left = null;
        //右孩子
        Entry<K,V> right = null;
        //父亲
        Entry<K,V> parent;
        //颜色
        boolean color = BLACK;

上一篇,介绍了集合框架中的HashMap对象,主要讲述了HashMap的底层实现和基本操作。本篇,让我们继续来学习Map集合,今天的主角是TreeMap。

成员变量

//比较器
private final Comparator<? super K> comparator;
//根节点
private transient TreeMapEntry<K,V> root = null;
//集合大小
private transient int size = 0;
//修改次数
private transient int modCount = 0;

红黑树TreeMap的查询

public V get(Object key) { Entry<K,V> p = getEntry; return (p==null ? null : p. value);}final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) // 如果比较器为空,只是用key作为比较器查询 return getEntryUsingComparator; if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; // 取得root节点 Entry<K,V> p = root; // 从root节点开始查找,根据比较器判断是在左子树还是右子树 while (p != null) { int cmp = k.compareTo; if (cmp < 0) p = p. left; else if (cmp > 0) p = p. right; else return p; } return null;}final Entry<K,V> getEntryUsingComparator(Object key) { K k =  key; Comparator<? super K> cpr = comparator ; if (cpr != null) { Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key ); if (cmp < 0) p = p. left; else if (cmp > 0) p = p. right; else return p; } } return null;}

到此TreeMap就分析完了,其实大部分时间都在整理红黑树,在数据结构中树是比较难懂的一个,其算法也比较复杂,对于树的理解一定要多看图画图,要明白这么做是为了解决什么问题,这么做又有什么好处,当然看一遍看不懂就要多看几遍了。

红黑树演示:

本文由1010cc时时彩标准版发布于三分时时彩1010CC,转载请注明出处:TreeMap源码分析,TreeMap完全剖判

关键词:

上一篇:1010cc时时彩标准版绝对路径与相对路线难点,w

下一篇:没有了