前言：
在上一篇文章： Java 集合框架—LinkedHashMap—源码研读 中，我们深入学习了LinkedHashMap，现在，让我们开始学习更进阶一点的内容——TreeMap。学习TreeMap前，最好需要先了解一下比较器Comparat、二叉排序树、 红黑树 据结构的知识。
所以此篇文章，分为3个部分：
1.比较器Comparator和Comparable接口
2.红黑树和二叉排序树
3.红黑树的左旋和右旋
4.TreeMap的源码分析-put()方法、fixAfterInsertion()解读
1.比较器Comparator和Comparable接口
首先，HashMap中的键值对是无序的，LinkedHashMap的出现使得键值对可以按照插入顺序被遍历，但是有很多场景下，我需要根据插入其中的键值对中的key来进行排序，而不是简单的根据插入顺序。那么此时LinkedHashMap便无能为力了！这时，TreeMap就派上了用场，因为TreeMap天生就实现了SortedMap接口，而SortedMap是为了排序而存在的。
让我们先看一下Map接口的关系图和TreeMap的类关系图：
可见：TreeMap继承自AbstractMap，实现了NavigableMap、Cloneable和Serializable接口。
其中有一点需要注意，NavigableMap继承自SortedMap，而SortedMap接口就是TreeMap中对象有序的核心。
SortedMap接口是干嘛的？简单来说SortedMap接口中包含 Comparator比较器 ，可以自定义比较方法用于实现key的比较。即实现SortedMap的类，其中的对象即可根据比较器中定义的方法，对key进行排序从而达到类中对象有序的目的。
目前java中SortedMap接口的实现类只有TreeMap。如果对Comparable和Comparator还不太熟悉，可以看看下面的内容，否则可以pass掉。
Comparable 和 Comparator的区别：
首先，Comparable和Comparator都是用于比较的接口，全名：java.lang.Comparable 和 java.util.Comparator
Comparable接口主要用于自然比较 ，里面只有一个方法：public int compareTo(T o);
Integer、String都实现了Comparable接口并实现了接口中的compareTo方法，Integer中的compareTo方法如下：
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
} Comparator主要用于外部定义的比较器 ，譬如自定义的某个bean对象需要进行比较，那么比较的规则就可以通过Comparator来实现。
详细可以参考:Java 解惑：Comparable 和 Comparator 的区别
说了前面的Comparator其实是为了给今天的主角TreeMap做铺垫，因为TreeMap正是通过比较器Comparator中的方法来实现的排序，从而达到有序的目的。现在让我们看看TreeMap的类定义：
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;
类变量中第一位就是Comparator类的变量comparator，这个comparator即treeMap用于制定排序规则的比较器。root，即treeMap中的根节点；size和modCount我们都已经见过很多次，就不说了。除了类变量外，我们也注意到TreeMap的初始化有4种方式，分别是：
空构造器、定义了comparator的构造方法、初始Map作为参数的构造方法、初始SortedMap作为参数的构造方法。现在，想一下如果初始化时未定义比较器comparator，那么TreeMap还可以正常排序么？如果可以是怎样排序的？
答案是：YES
如果初始未定义比较器，则如果key是Integer、Double、String等已经实现了Comparable接口的类，否则会默认调用其compareTo方法来比较key的大小。
如果key没有实现Comparable接口，则会报ClassCastException异常。
2.红黑树和二叉排序树
红黑树，是一种近似平衡的二叉排序树。
二叉排序树(二叉搜索树)或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
红黑树，顾名思义，通过给树节点增加一位，颜色属性，来标记节点的颜色。颜色只能为红或者黑色。这些颜色位用于确保树在插入和删除期间保持近似平衡。
让我们看一下维基百科中对【 红黑树 】规则的讲解：
除了对二叉搜索树施加的要求之外，红黑树还必须满足以下要求：[16]
- 每个节点都是红色或黑色。
- 根是黑色的。有时会省略此规则。由于根始终可以从红色变为黑色，但不一定相反，因此该规则对分析几乎没有影响。
- 所有叶子（NIL）都是黑色的。
- 如果节点为红色，则其子节点均为黑色。
- 从给定节点到其任何后代NIL节点的每条路径都包含相同数量的黑色节点。
一些定义：从根到节点的 黑色 节点数是节点的 黑色深度 ; 从根到叶子的所有路径中的黑色节点的统一数量被称为红黑树的 黑色高度 。[17]
这些约束强制执行红黑树的关键属性： 从根到最远叶子的路径不超过从根到最近叶子的路径的两倍。 结果是树大致高度平衡。由于诸如插入，删除和查找值之类的操作需要与树的高度成比例的最坏情况时间，因此与最普通的二叉搜索树不同，这种高度的理论上限允许红黑树在最坏的情况下是有效的。
要了解为什么这是有保证的，只需考虑属性4和5的影响就足够了。对于红黑树T，设B为属性5中的黑色节点数。让从T的根到任何叶子的最短可能路径由B个黑色节点组成。可以通过插入红色节点来构造更长的可能路径。但是，属性4使得无法插入多个连续的红色节点。因此，忽略任何黑色NIL叶，最长可能路径包括2 * B节点，交替黑色和红色（这是最坏的情况）。计算黑色NIL叶，最长可能路径由2 * B-1个节点组成。
最短路径具有所有黑色节点，并且最长路径在红色和黑色节点之间交替。由于所有最大路径具有相同数量的黑色节点，因此通过属性5，这表明没有路径是任何其他路径的两倍多。
红黑树，除了定义中规定的要求以外，在Java实现中还增加了如下要求：
1..新插入的节点必须为红色。
2.任意节点其左右子树最多相差2层红节点。
3.插入过程（仅限于插入点那条路径上）中不允许任一节点有2个红色儿子节点。
这些规定使得红黑树的实际表现近似平衡的二叉排序树，即一个n个节点的红黑树，其平均高度为logN,最差情况高度为2log(N+1) . 故其查找效率为O(logN)。综合查找、插入和删除节点所引起的时间开销，其实际表现通常优于平衡二叉树。
3.红黑树的左旋和右旋
为什么要介绍红黑树的左旋和右旋操作呢？因为，这是红黑树中最核心的操作，在 TreeMap源码中插入或删除红黑树中节点时，可能会引发红黑树结构的变化，那为了重新调整结构变化过的树，使之成为符合红黑树5项要求的树，最重要的操作就是1.改变某些节点的颜色；2.左旋rotateLeft和右旋rotateRight。
改变颜色比较容易，关键在于左旋和右旋操作，下面还是借用一下图片来举例说明，关于红黑树的左旋、右旋等详细过程的图文讲解，部分引用于一篇github上不错的文章：
TreeSet and TreeMap
A.左旋
如上图所示，以3号节点为中心的左旋操作，实际上是逆时针旋转，对应的右旋即顺时针旋转。可以想象下，3在左旋逆时针向下的过程中必然会和10号节点左下角的6发生碰撞，结果是3号节点成功上位，成为了10号节点新的左孩子，那么被【碰撞出去】的6号节点只能顺势成为了3号节点的孩子(右孩子)
B.右旋
10号节点右旋，即顺时针旋转。旋转到3号节点右下角成为其右孩子。3号节点原本的右孩子6号节点被挤掉，成为了10号节点的左孩子。
4.TreeMap的源码分析-put()方法
在进入put方法前，我们先看一下TreeMap中红黑树Entry节点的定义：
如图所示，Entry类的成员变量除了key-value外还有leftt、right用于标记左、右孩子节点；
parent用于标记父节点。boolean类型的color变量用于记录红黑树的颜色BLACK或RED。
OK，现在让我们看一下TreeMap中的put()方法：
首先，判断红黑树的root节点，若为空则new一个root节点，将key、value值放置进去。
不空则进入下面：
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator; 创建一个Comparator比较器变量cpr，这个comparator可以由外部传入，如果不传则为null。
然后：
if (cpr != null) {
...
}
else {...} 如果cpr！=null则进入第一个分支，若cpr==null则进入else分支，由于分支内操作类似，我们以else分支为例看一下操作：
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);
} else分支下首先会进行判断：if (key == null)，如果成立则throw new NullPointerException();
否则创建一个Comparable比较器变量k，值为key。这一步需要注意的是， 如果初始没有设置比较器，而且key的类型并没有实现Comparable接口，则会抛出ClassCastException，表示类型转换异常。 当然，如果key是Integer,String等实现了Comparable接口，且覆写了compareTo方法的类型，则不会抛异常。
下一步，进入do…while循环中去，循环从根节点开始遍历，直到遍历到叶子节点t = null时跳出，或者找到key值相等的节点t.key= k,则将新value值覆盖原value值后跳出循环。
最后：
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null; 新建一个红黑树节点e，根据cmp<0或>0来决定将其插入至parent节点的左边或者右边。
插入完成后，调用fixAfterInsertion()方法来判断是否需要对整个红黑树进行结构调整。
为什么需要结构调整？因为红黑树存在是要符合如下要求的：
- 每个节点都是红色或黑色。
- 根是黑色的。有时会省略此规则。由于根始终可以从红色变为黑色，但不一定相反，因此该规则对分析几乎没有影响。
- 所有叶子（NIL）都是黑色的。
- 如果节点为红色，则其子节点均为黑色。
- 从给定节点到其任何后代NIL节点的每条路径都包含相同数量的黑色节点。
新插入的节点默认是黑色的，这样必然会违反第5条原则，故必须通过fixAfterInsertion()来调整。让我们看一下TreeMap中的精髓之一操作红黑树的 fixAfterInsertion() 方法：
直接看代码肯定不容易理解，特别是结合了红黑树的左旋、右旋操作更是容易看晕，所以此处我们还是对着图片讲解，以图(a)中新插入了一个6号节点为例，对着代码看一下红黑树调整的过程。
通过代码我们能够看到，情况2其实是落在情况3内的。情况4～情况6跟前三种情况是对称的，因此图解中并没有画出后三种情况，读者可以参考代码自行理解。
到此，我们TreeMap中put()方法的源码就已经分析完成了，红黑树的部分关键在于看图理解，之后再看代码就很清楚了~看完文章觉得不错亲盆好友们，麻烦动动小手，点个哦，谢谢~
