前序： 在用TreeMap的时候，发现其非常有特点，故结合网上的资料整合写了此篇。 红黑树：红黑树并不是一个完美平衡二叉查找树，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点。所以我们叫红黑树这种平衡为黑色完美平衡。 再来解析源码之前，先来看看TreeMap的类继承结构
它实现了SortMap的方法，所以，它具有SortMap的方法（SortMap是一种根据key来进行排序的集合数据结构），故而，它可以根据需求可以查询map的第一个key，最后一个key（因为它是有序的）
那么就有疑惑了？为什么会有序呢？来看看它的典型实现类TreeMap的put方法，源码开始调试…
看到这里，就更有点紧张刺激了，感觉一脸懵逼 现在开始正式读源码了！！ 前面两句
代码语言：javascript复制//将根节点赋值给当前的Entry对象
Entry<K,V> t = root;
if (t == null) {
//如果根节点是空的，让传入的key自己做比较，显然没什么意思，再怎么比都是相等的
compare(key, key); // type (and possibly null) check
//这个时候root还是空的，表示当前树还没有根节点，当然要先new一个根节点咯，
root = new Entry<>(key, value, null);
//size 1
size = 1;
//添加修改次数
modCount ;
return null;
}上面这段代码只是再第一次put的时候执行的，然而这段代码显然难度很低，不要慌，继续往下看！！
代码语言：javascript复制//
int cmp;
Entry<K,V> parent;
// 这块的代码相信有点懵逼，在哪里初始化的呢？显然还没有初始化，所以会走下面的else流程
Comparator<? super K> cpr = comparator;
//这一步同下步，因为刚刚先分析else下面的代码，故而不注释这里了
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 {
//判断了一下key是否为空，否则NPE，为什么呢？看下句
if (key == null)
throw new NullPointerException();
//拿到key之后，将key强转为Comparable
@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)
//如果新加的key比根节点大，显然在右子树并返回当前的节点
t = t.right;
else
//相等的话，替换掉原来的key
return t.setValue(value);
//循环递归，将新的key排好自己的位置之后，此时parent即为新key的根节
} while (t != null);
}
//此时，parent在上一步会循环到新节点的父节点上
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;看不懂可以来结合这张图
======================================这是分割线==========================================
下面就是紧张刺激的连环杀——红黑树 前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。 变色：结点的颜色由红变黑或由黑变红。
先截图这个方法，别慌，一点一点解读
** 在解读这里之前，先来了解一下红黑树的4个特性： 1、根节点始终是黑色 2、所有的叶子节点下的虚拟节点都是黑色的 3、一条路径下不能出现相邻的两个红色节点 4、任何从根节点到下面的节点，相同数目的黑色节点都要相同。**
结构如下：
备注：本文中所有关于红黑树中的示意图采用白色代表红色。黑色节点还是采用了黑色表示。
代码语言：javascript复制 /** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
//默认节点颜色都是红色的，根节点都始终是黑色的
x.color = RED;
//新节点是根节点 或者父节点是红色
//插入红色节点不会破坏红黑树的性质<>
while (x != null && x != root && x.parent.color == RED) {
//如果父节点是父节点的父节点的左子树，也就是说 爷爷节点的左子节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//拿到右叔节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果右叔节点是红色，父亲节点变黑，右叔变黑，爷爷变红
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//如果新节点是父亲节点的右节点
if (x == rightOf(parentOf(x))) {
//对父亲节点左旋，转化父亲节点为x
x = parentOf(x);
rotateLeft(x);
}
//重新着色对爷爷节点变红，然后右旋，
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
//下方同理
//先拿到左叔
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//假如左叔是红色
if (colorOf(y) == RED) {
//父亲节点变黑，左叔变黑，爷爷节点变红，然后将新节点转化为爷爷节点左旋
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//新节点是父亲节点的左子树
if (x == leftOf(parentOf(x))) {
//转换父节点，然后右旋 变色左旋
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//根节点始终是黑色
root.color = BLACK;
}这里，就对TreeMap的红黑树进行解读完毕，下面开始针对上面的旋转变色进行整理。 本文参照简书一位大神的文章：彻底理解红黑树
