TreeMap实现了SortedMap接口，可以根据k的大小顺序，对map中的元素进行排序，可以根据key的自然顺序，也可以通过构造函数传入比较器comparator
TreeMap 底层是红黑树实现的，意味着put get remove 都是log(n)复杂度
前言
先学红黑树再来，我啊，学得很累，哎！！！！！，下面的源码，我写了很多我得见解，如果你没有耐心看，那可以离开了，太啰嗦了，哈哈
构造器
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
get
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
//如果comparator不是空的
if (comparator != null)
return getEntryUsingComparator(key);
//key是空，抛异常哦，不能传null
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//key是需要实现Comparable接口的，所以这里可以强转
Comparable<? super K> k = (Comparable<? super K>) key;
//没有comparator的情况
//root等于树的根节点
// p= root
Entry<K,V> p = root;
//如果根节点不是null的
while (p != null) {
//从根节点，开始一个一个的通过compareTo比较key的值
int cmp = k.compareTo(p.key);
//k<p 小于就是在左边
if (cmp < 0)
p = p.left;
//k>p 大于就是在右边
else if (cmp > 0)
p = p.right;
//就是这个值，返回
else
return p;
}
//返回null
return null;
}
//使用构造函数传进来的Comparator
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
//构造函数传进来的
Comparator<? super K> cpr = comparator;
//cpr不能是空
if (cpr != null) {
//root等于树的根节点
// p= root
Entry<K,V> p = root;
/从根节点，开始一个一个的通过compareTo比较key的值
while (p != null) {
int cmp = cpr.compare(k, p.key);
//k<p 小于就是在左边
if (cmp < 0)
p = p.left;
//k>p 大于就是在右边
else if (cmp > 0)
p = p.right;
//就是这个值，返回
else
return p;
}
}
return null;
}
put
public V put(K key, V value) {
//root等于树的根节点
// t= root
Entry<K,V> t = root;
//根节点为空，说明第一次put
if (t == null) {
//用来检查。是否有特定的comparator,或者key实现了comparator
compare(key, key); // type (and possibly null) check
//创建一个Entry赋值给root
root = new Entry<>(key, value, null);
//元素容量加1
size = 1;
//修改次数+1
modCount++;
return null;
}
int cmp; //记录最后一次比较
Entry<K,V> parent; //记录最后的t节点
// split comparator and comparable paths
//是否有特定的comparator
Comparator<? super K> cpr = comparator;
//有特定的comparator
if (cpr != null) {
do {
//用于记录最后的t
parent = t;
//特定的comparator比较key
cmp = cpr.compare(key, t.key);
// key < t.key 小于在左边
if (cmp < 0)
t = t.left;
// key > t.key 大于在右边
else if (cmp > 0)
t = t.right;
//已经存在这个key了，覆盖旧的值完事
else
return t.setValue(value);//修改才返回
} while (t != null);
}
//没有特定的comparator
else {
//key是空，完犊子啊
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//key必须实现Comparable接口，所以这里可以强转
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//用于记录最后的t
parent = t;
cmp = k.compareTo(t.key);
// key < t.key 小于在左边
if (cmp < 0)
t = t.left;
// key > t.key 大于在右边
else if (cmp > 0)
t = t.right;
//已经存在这个key了，覆盖旧的值完事
else
return t.setValue(value);//修改才返回
} 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++; //元素+1
modCount++;//次数+1
return null;
}
final int compare(Object k1, Object k2) {
//如果没有设置特定comparator，就根据key实现的comparator来比较，否则用特定的comparator
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
//调整红黑树
//先把需要插入的节点设置为红色节点
//情况1 如果节点的父节点是红色，叔叔的节点也是红色，则把父节点和叔叔节点设置为黑色，祖父节点设置为红色，把祖父节点设置为当前节点
//情况2 如果节点x的父节点y是红色，叔叔的节点是黑色，如果x节点是父节点的右节点，把父节点设置为当前节点，以父节点为中心，逆时针旋转（左旋），
//使得x节点成为y节点的父节点，y节点成为x节点的左节点，x节点的左节点成为y的右节点
//情况3 如果节点x的父节点y是红色，叔叔的节点是黑色，如果x节点是父节点y的左节点，把父节点设置为黑色，祖父节z点为红色，以祖父节点z为中心，顺时针旋转（右旋）
//使得祖父节点的左节点c成为祖父节点z的父节点，祖父节点z成为节点c的右节点，节点c的原右节点成为祖父节点左节点
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
//条件 x当然不能是null
//x当然也不能是root x.parent.color等于红色，才能和 x.color = RED 违反一个节点红色，子节点肯定是黑色
while (x != null && x != root && x.parent.color == RED) {
//x的父节点是祖父节点的左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x))); //叔叔节点
//x 是红色，x.parent也是红色 x的叔叔节点也是红色
//那么爷爷节点肯定是个黑色节点
//最好的处理是，x.parent，x的叔叔节点都变成黑色，爷爷节点变成红色
//那么问题就变成了爷爷的红色，可能跟祖父的颜色冲突（祖父可能是红色）
//那么把当前的节点变成爷爷，继续调整，让树正确，或者结束祖父是黑色
if (colorOf(y) == RED) { //叔叔节点为红色
setColor(parentOf(x), BLACK); //父节点设置为黑色
setColor(y, BLACK);//叔叔节点设置为黑色
setColor(parentOf(parentOf(x)), RED);//祖父节点设置为红色
x = parentOf(parentOf(x));//把祖父节点设置为当前节点
} else {
//叔叔节点是黑色，x的父亲节点是红色，x是红色，爷爷肯定是黑色的
//此处是为了变成情况三，而进行调整的，让x,x的父节点成都为左节点
//把父节点设置为当前节点，为了替换掉爷爷节点，变成黑色，父节点变成黑色，那么就符合了红色下面不是红色了
if (x == rightOf(parentOf(x))) { //当前节点是父节点的右节点
x = parentOf(x); //把父节点设置为当前节点
rotateLeft(x);//左旋 以当前节点为中心，使得x节点逆时针旋转，让x节点成为父节点的父节点，父节点成为x节点的左节点
}
//情况二出现，会导致情况三出现
//当x右旋替换父节点，变了成黑色，那原来的父节点必须是红色节点了
setColor(parentOf(x), BLACK); //设置父节点为黑色
setColor(parentOf(parentOf(x)), RED);//祖父节点设置为红色
//以祖父节点为中心，进行右旋（顺时针旋转），
//让祖父节点的左节点成为祖父节点的父节点，祖父节点成为右节点
rotateRight(parentOf(parentOf(x)));
}
//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;//根节点设置为root
}
//右旋 p的左节点顺时针旋转 p的左节点成为p的父节点 p成为右节点，
private void rotateRight(Entry<K,V> p) {
if (p != null) { //节点不是空的，要不然完犊子
Entry<K,V> l = p.left; //取出p的左节点
p.left = l.right; //p的左节点的右节点成为p的左节点
if (l.right != null) l.right.parent = p;//设置p的左节点的右节点的父节点是p
l.parent = p.parent;//l的父节点=p的父节点，
if (p.parent == null)//如果p的父节点==null，那说明p就是根节点
root = l;//因为右旋就是把p的左节点设置为p的父节点，所以l就是根节点
else if (p.parent.right == p) //p是父节点的右节点
p.parent.right = l;//p的父节点的右节点设置成为l
else p.parent.left = l; //p的父节点的左节点设置成为l
l.right = p; //l的右节点是p
p.parent = l;//p的父节点就是l
}
}
//左旋 p的右节点逆时针旋转 p的右节点成为p的父节点，p成为p的右节点的左节点，p的右节点的左接节点成为p的右节点
private void rotateLeft(Entry<K,V> p) {
if (p != null) { //节点不是空的，要不然完犊子
Entry<K,V> r = p.right;//获取p的右节点
p.right = r.left;//p的右节点的 左接节点 成为p的右节点
if (r.left != null)
r.left.parent = p; //设置p的右节点的左节点的父节点是p
r.parent = p.parent; //r的父节点=p的父节点，
if (p.parent == null) )//如果p的父节点==null，那说明p就是根节点
root = r;////因为左旋就是把p的右节点设置为p的父节点，所以l就是根节点
else if (p.parent.left == p) //p是父节点的左节点
p.parent.left = r;//p的父节点的左节点设置成为r
else
p.parent.right = r;//p的父节点的右节点设置成为r
r.left = p; //r的右节点是p
p.parent = r;//p的父节点就是r
}
}
remove()
public V remove(Object key) {
//先获取对于的节点
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
//取出旧的值，用于返回
V oldValue = p.value;
deleteEntry(p);
//返回旧的值
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;//修改次数+1
size--;//元素数量减1
// If strictly internal, copy successor's element to p and then make p
// point to successor.
//这里是说p节点有两个节点
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);//查找p的后继节点，返回后继节点
p.key = s.key; //把后继节点的key赋值给key
p.value = s.value; //把后继节点的value赋值给value
p = s; //p重新指向s
} // p has 2 children
// Start fixup at replacement node, if it exists.
//如果存在左节点就去左节点，没有左节点就取右节点
//其实啊，尽管p节点有两个节点，经过successor之后，p就等于p的后继节点s了，而这个s的特点就是:要么没有子节点，要么只有一个右节点(可以看下面successor的分析)，
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//只有一个元素
if (replacement != null) {
// Link replacement to parent
//这里是想把replacement替换掉p
//想替换，只需要以下步骤
//第一步 (p.parent.right = replacement or p.parent.left = replacement) and (replacement.parent = p.parent);
//第二步 释放p p.left = p.right = p.parent = null
//replacement 是p的唯一节点
replacement.parent = p.parent; //replacement.parent = p.parent
if (p.parent == null) //是根节点
root = replacement;//则替换后，replacement为新的root
else if (p == p.parent.left) //这里是说p是个左节点
p.parent.left = replacement; //p.parent.left = replacement
else //这里是说p是个右节点
p.parent.right = replacement; // p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
////如果p的颜色是黑色，说明会违反规则，从一个节点到尾端节点的任何路径都包含相同的黑节点
//replacement 可能是红色，也有可能是黑色
//p.color 是红色，那replacement必定为黑色，在没删p时的路径的黑色数量 红 + 黑 = 1 个 删掉只有一个黑色 所以改变黑色节点的数量
//只有p.color 是黑色时，如果replacement 也是黑色 则是2个黑色 删掉p 之后就是1个黑了
if (p.color == BLACK)
//调整红黑树，看下面分析
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node. //p是根节点
root = null;//p是根节点，删除p之后，树一个节点都没有了，所以把根节点设置为null
} else { // No children. Use self as phantom replacement and unlink.
//p没有子节点的情况
if (p.color == BLACK) //如果p的颜色是黑色，说明会违反规则，从一个节点到尾端节点的任何路径都包含相同的黑节点
//调整红黑树，看下面分析
//这里为什么是先调整啊？mmp的，太坑了，搞蒙了我啊，为啥啊？？？？？？？？？？？？？？？？？？？？？？？？？？？？
//网上一顿百度，百度不出来，哎！！！！！！！！，想要谷歌，不会英文，不知怎么正确描述，哎！！！！！！
//哎，慢慢看了，烦死了
//再看一下这些文字，这只是我分析出来的一点观点，可能很啰嗦，也可能是错误的，还望大佬多多指教
//先了解红黑树这个规则 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
//我们现在是删除，那么p是黑色，删了他，我们就少了一个黑色的了，违反了红黑树的规则
//假设，p之前还有一个父节点(黑色的)，只是现在p占了他的位置，那么这个场景下不就是跟上面的
//fixAfterDeletion(replacement) 场景一样了？
//你再看看源码里的那句注释英文 No children. Use self as phantom replacement and unlink.
//phantom replacement 虚幻的replacement,这不就是符合我上面的假设吗？
//假设，p之前还有一个父节点(黑色的)的，只是现在p占了他的位置
//当我们把p传进去，不就是补多了一个黑色吗？
//所以下面删除了p也不会影响树的黑节点 ，可以看我下面的图（拷贝“图1-1”搜本页），
//至于为什么是先调整，可以下面的图分析（拷贝“图1-2”搜本页），这个图只是我的一点分析，
//我也不知真正原因，求大佬告知
fixAfterDeletion(p);
if (p.parent != null) {//如果p不是根节点
if (p == p.parent.left) //如果p是父节点的左节点
p.parent.left = null; //删除p父节点的左节点引用
else if (p == p.parent.right) //如果p是父节点的右节点
p.parent.right = null;//删除p父节点的右节点引用
p.parent = null; //p的父节点的引用设置为null
}
}
}
//获取t的后续节点
//------------------------------二叉查询树获取后续节点的规格--------------------------
//后续节点获方式
//第一步 判断t节点是否存在右节点
//情况1： 如果存在右节点，那么后续节点就是t的右子树的最小值
//如果不存在右节点，就需要判断t节点和父节点的关系了
//情况2： 如果t是父节点的左节点，则t的后续节点就是父节点
//情况3： 如果t是父节点的右节点，则需要顺着t的祖先一直寻找，直到找到一个祖先，而这个祖先是个左节点，则这个祖先就是t的后续节点
//------------------------------二叉查询树获取后续节点的规格--------------------------
//分析，在删除元素时，调用这个函数的条件是 p.left != null && p.right != null ==》两个节点都在的情况下
//其实在这里，t肯定是有右元素的，所以在删除里调用本函数只满足情况1
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null) //t不能为空啊，不然完犊子
return null; //直接返回null
else if (t.right != null) { //第一步 判断t是否有右节点？
//存在右子节点
Entry<K,V> p = t.right; //获取t的右子节点
while (p.left != null) //循环t的右子节点的左节点直到最后一个左节点,那么最后一个左节点就是t的后续节点
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent; //p = t的父节点
Entry<K,V> ch = t;//ch = t
//p != null 当前节点是整个树的最右节点时，p最后会等于null,整个树的最右节点是没有后继节点的，直接返回null
//ch == p.right 如果ch 是个左节点那么p就是后续节点了啊！！！
//好妙的循环啊，不管ch是p的左还是右节点，
//情况2 ：如果t是父节点的左节点（如果t一开始就是左节点），不执行循环，p就是t的后续节点 成立啊！
//情况3： 如果t是父节点的右节点，则需要顺着t的祖先一直寻找（顺着不就是说ch一直是右节点吗），直到找到一个祖先，而这个祖先是个左节点（那不就是ch等于左节点了吗） 成立啊
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p; //返回后续
}
}
//删除红黑树
//如果x是红色节点，直接设置为黑色即可
//如果x是根节点，直接设置为黑色即可
//如果上面的条件不符合，那么就有4种情况，对称的还有4种情况
//情况1： 如果x的兄弟节点sib 是 红色
// 兄弟节点sib 设置为黑色，
// 设置x的父节点为红色，
// 以x的父节点为中心，进行左旋
//sib = 左旋后x的兄弟节点
//情况2 x的兄弟节点sib 的左右子节点都是黑色
//设置 x的兄弟节点sib为红色
//以x的父节点为x节点 x = parentOf(x);
//情况3 x的兄弟节点sib是黑色; x的兄弟节点sib的右子节点都是黑色，左节点是红色
//情况4 x的兄弟节点sib是黑色; x的兄弟节点sib的右子节点都是红色，左节点是任意颜色
//经过我一天的分析，我稍稍领悟了一点这个函数
//只有变成情况4才能通过右节点平衡左节点，要不然就只能循环，让整一棵树都少一个黑色节点（根节点的左右节点都少一个黑色节点）
//情况1，是为了让sib变成黑色，好执行情况2,，3,4
//情况2，是一个无法变成情况4的情况，只能循环，如果一直变不了情况3或者4，一直循坏x = parentOf(x)到达根节点，
//那么整一棵树都少一个黑色节点（根节点的左右节点都少一个黑色节点）
//情况3，为了转变成情况4
//情况4，可以让右节点平衡左节点，为什么可以
//因为sib的右子节点是红色+n个黑色，左边是n个黑色，这样才能符合对于每个节点，从该点至null(树尾端)的任何路径，都含有相同个数的黑色节点
//可以推导出，p的右节点的黑色树是 n+1(sib是黑色的) ，左节点是n（因为删了一个）
//所以通过左旋，会把p（x的父节点，sib的父节点）变成sib的左节点，那么左节点就多出了一个节点p
//还记得之前 sib右子节点是红色+n个黑色，左边是n个黑色，经过左旋后
//sib的右节点还是跟着sib，因为sib肯定是个黑色，所以右节点是n+1个黑色。但sib的左节点已经移到p的右节点了，
//所以是p(可能是红也可能是黑)+(n+1（1当然是来自sib）)黑色节点 p + n + sib
//那么总结 左是 sib+p+n 右是sib+红色节点+n 不平衡
//如果让 sib变成p的颜色(可能是红也可能是黑)，那么就变成 p+n 和 红色节点+n
//那就让 p=红色节点 = 黑色,最终变成 sib的左，右都是n+1
//因为sib 替代了p的位置，那么计算sib的左右节点数
//sib左节点的黑色节点数是 n+1，右边节点是 n+1 ,和之前的比较
//p的左节点是n（因为删了一个），右节点的黑色树是 n+1(sib是黑色的)
//得出结论树已经修复
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) { //如果x的颜色是黑色，x不是根节点
if (x == leftOf(parentOf(x))) { //x是左子节点
Entry<K,V> sib = rightOf(parentOf(x));//获取x的兄弟节点slib
//情况1： 如果兄弟节点sib 是 红色
//首先为什么这么干
//x是个黑色节点，x的兄弟节点是个红色
//为什么这么设置，其实很好理解的
//举例子，p是父节点，sib是p的右节点，x是p的左节点
//因为是删除的缘故，x之前的父节点已经被x给替换掉了，所以现在经过x的这条线路少了一个黑色节点
//那怎么才能在x的这条线路多出一个节点，然后染黑他就可以搞定了
//好说啊，我以p为中心，进行左旋，sib就逆时针跑到p的位置了，而p就成为sib的左儿子了
// p 左旋 sib
// / \ ===> /
// x sib p
// /
// x
//在x的这条线路是多了一个p，但是这不会影响黑色节点个数吗？肯定会影响的啊！所以就有判断了
//如果sib是个红色的节点，p一定是个黑色的节点（规则，不能出现连续的红色节点），那么左旋会发生什么呢？
// p(黑) 左旋 sib(红) 改色 sib(黑)
// / \ ===> / \ ===> / \
// x sib(红) p(黑) b(黑) p(红) b(黑)
// / \ / \ / \
// c(黑) b(黑) x c(黑) x c(黑)
//未左旋时 p->sib->c 经过了2个黑色 p->sib->c 经过了2个黑色
//左旋后 sib->p->c 经过了2个黑色 sib->c 经过了1个黑色，违反了规则啊
//改色后 sib->p->c经过了2个黑色， sib->c 经过了2个黑色，不违反了
//其实就是让sib占了p的位置，因为p一定是个黑色，所以sib也要变黑，
//但这样x的路径就多出了一个黑色p，为了不违反规则，p要设置为红色
//左旋之后，x的兄弟节点就发生了改变，所以重新获取新的兄弟节点，这里的例子是c
if (colorOf(sib) == RED) {
setColor(sib, BLACK);// 兄弟节点sib 设置为黑色，
setColor(parentOf(x), RED);//设置x的父节点为红色
rotateLeft(parentOf(x)); //以x的父节点为中心，进行左旋
sib = rightOf(parentOf(x));//sib = 左旋后x的兄弟节点
}
//情况2 x的兄弟节点sib 的左右子节点都是黑色
//为什这么设置呢？
//继续使用上面情况1的例子
// j(黑)
// / \
// p(红) b(黑)
// / \ / \
// x sib(黑) g(黑色) h(黑色)
// / \
// e(黑色) f(黑色)
//如果sib节点的两个子节点都是个黑色,sib肯定也是黑色，不然就执行上面那个if了
//为什么是setColor(sib, RED); x = parentOf(x);
//因为p的左节点少了一个黑色（已被删除了），而p的右节点sib和sib的左右子节点都是黑色
//那说明无法进行任何操作，就算天王老子来了也没法让p的左节点多一个黑色节点
//那么就只能让sib变成红色，让p的左右节点的黑色节点变得平衡
//虽然p的左右节点的黑色节点已经平衡，但是问题就会转到p节点的父节点t，
//因为t的左节点p少了一个黑色节点，那么需要继续循环调整，
//最坏的情况是，一直循环到达根节点，那么整一棵树都会少一个黑色节点，达到了最终的平衡
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED); //设置 x的兄弟节点sib为红色
x = parentOf(x); //以x的父节点为x节点
} else {
//情况3 x的兄弟节点sib是黑色; x的兄弟节点sib的右子节点都是黑色，左节点是红色
// j(黑)
// / \
// p(红) b(黑)
// / \ / \
// x sib(黑) g(黑) h(黑)
// / \
// e(红) f(黑)
// / \
// i(黑) j(黑)
// \
// k(黑)
//为什么这么设置呢
// setColor(leftOf(sib), BLACK); //设置x的兄弟节点sib的左节点为黑色
// setColor(sib, RED);//设置x的兄弟节点sib为红色
// rotateRight(sib);//以x的兄弟节点sib为中心，进行右旋，sib左节点顺时针旋转，让sib左节点成为sib的父节点，sib为右节点
//这里的操作就是为了变成情况四的
//情况4 x的兄弟节点sib是黑色; x的兄弟节点sib的右子节点都是红色，左节点是任意颜色
// j(黑)
// / \
// p(红) b(黑)
// / \ / \
// x sib(黑) g(黑) h(黑)
// / \
// e(黑) f(红)
// / \
// i(黑) j(黑)
// \
// k(黑)
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK); //设置x的兄弟节点sib的左节点为黑色
setColor(sib, RED);//设置x的兄弟节点sib为红色
rotateRight(sib);//以x的兄弟节点sib为中心，进行右旋，sib左节点顺时针旋转，让sib左节点成为sib的父节点，sib为右节点
sib = rightOf(parentOf(x)); //sib = 右旋后x的兄弟节点
}
//情况4 x的兄弟节点sib是黑色; x的兄弟节点sib的右子节点都是红色，左节点是任意颜色
// j(黑)
// / \
// p(红) b(黑)
// / \ / \
// x sib(黑) g(黑) h(黑)
// / \
// e(黑) f(红)
// / \
// i(黑) j(黑)
// \
// k(黑)
//怎样做可以让p的左节点多出一个节点 rotateLeft(parentOf(x));//对x的父节点进行左旋
// j(黑)
// / \
// sib(红) b(黑)
// / \ / \
// p(红) f(红) g(黑) h(黑)
// / \ \
// x e(黑) j(黑)
// / \
// i(黑) k(黑)
//
// 现在x的父节点已经成为sib的左节点，那么p就是多出的哪一个节点了，但是黑色节点数量就改变了
// 为了让sib真正的成为p的替代品，则setColor(sib, colorOf(parentOf(x)));
// j(黑)
// / \
// sib(红) b(黑)
// / \ / \
// p(红) f(红) g(黑) h(黑)
// / \ \
// x e(黑) j(黑)
// / \
// i(黑) k(黑)
//
//一开始 sib-f-j-k 有3个黑色，现在只2个，那怎办办setColor(rightOf(sib), BLACK);直接变黑色
// j(黑)
// / \
// sib(红) b(黑)
// / \ / \
// p(红) f(黑) g(黑) h(黑)
// / \ \
// x e(黑) j(黑)
// / \
// i(黑) k(黑)
// 一开始sib->e->i 有三个黑色 现在 sib->p->e->i 只有两个黑色
// sib 是替代p位置的，不能改颜色，所以只能是p 改setColor(parentOf(x), BLACK);// 将x父节点设为黑色
// j(黑)
// / \
// sib(红) b(黑)
// / \ / \
// p(黑) f(黑) g(黑) h(黑)
// / \ \
// x e(黑) j(黑)
// / \
// i(黑) k(黑)
//到现在，所有的调整都完成了，x路径也多出了一个黑色节点p，
//所以这个树就平衡了，所以需要退出循环 x = root;//设置x为根节点 调整完毕退出循环
setColor(sib, colorOf(parentOf(x)));//将x父节点颜色 赋值给 x的兄弟节点sib
setColor(parentOf(x), BLACK);// 将x父节点设为黑色
setColor(rightOf(sib), BLACK);// 将x兄弟节点sib的右子节设为黑色
rotateLeft(parentOf(x));//对x的父节点进行左旋
x = root;//设置x为根节点 调整完毕退出循环
}
} else { // symmetric //x是右子节点，这里是对称，所以跟情况1,2,3,4是一样的
Entry<K,V> sib = leftOf(parentOf(x));//sib = x的兄弟节点
//情况5： 如果兄弟节点sib 是 红色
if (colorOf(sib) == RED) {
setColor(sib, BLACK);//设置x的兄弟节点为黑色
setColor(parentOf(x), RED);//设置x的父节点为红色
rotateRight(parentOf(x)); //以x的父节点为中心，进行右旋
sib = leftOf(parentOf(x));//sib = 右旋后x的兄弟节点
}
//情况6 x的兄弟节点sib 的左右子节点都是黑色
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED); //设置 x的兄弟节点sib为红色
x = parentOf(x); //以x的父节点为x节点
} else {
//情景7 x是黑色，x的兄弟节点的左节点是黑色
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);//设置x的兄弟节点为的右节点为黑色
setColor(sib, RED);//设置x的兄弟节点为红色
//以x的兄弟节点为中心进行左旋，x的兄弟节点的右节点逆时针旋转，成为x的兄弟节点的父节点
//x的兄弟节点成为左节点
rotateLeft(sib);
sib = leftOf(parentOf(x));//sib = 左旋后x的兄弟节点
}
//情景8 x是黑色，x的兄弟节点的左节点是红色，右节点是任意颜色
setColor(sib, colorOf(parentOf(x)));//把x的父节点的颜色拷到x的兄弟节点sib
setColor(parentOf(x), BLACK);//把x的父节点的颜色改成黑色
setColor(leftOf(sib), BLACK);//把x的兄弟节点sib的左节点设置为黑色
rotateRight(parentOf(x));//以x的父节点为中心，进行右旋
x = root;//设置x为根节点 调整完毕退出循环
}
}
}
setColor(x, BLACK); //把x节点设置为黑色
}
}
图1-1
image.png
图1-2
image.png
网友评论