右右节点旋转（插入节点的父节点是右节点，插入节点也是右节点）
还是来上面的图来举例，我们在这颗红黑树上插入节点 70 。
我们可以这样操作围绕祖父节点 66 左旋，再把旋转后的根节点 69 设置为黑色，把 66 这个节点设置为红色。具体可以参看下图：
红黑树在 Java 中的实现
Java 中的红黑树实现类是 TreeMap ，接下来我们尝试从源码角度来逐行解释 TreeMap 这一套机制是如何运作的。
// TreeMap中使用Entry来描述每个节点
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
...
}
TreeMap 的put方法。
public V put(K key, V value) {
//先以t保存链表的root节点
Entry<K,V> t = root;
//如果t=null,表明是一个空链表，即该TreeMap里没有任何Entry作为root
if (t == null) {
compare(key, key); // type (and possibly null) check
//将新的key-value创建一个Entry，并将该Entry作为root
root = new Entry<>(key, value, null);
size = 1;
//记录修改次数加1
modCount ;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果比较器cpr不为null，即表明采用定制排序
if (cpr != null) {
do {
//使用parent上次循环后的t所引用的Entry
parent = t;
//将新插入的key和t的key进行比较
cmp = cpr.compare(key, t.key);
//如果新插入的key小于t的key，t等于t的左边节点
if (cmp < 0)
t = t.left;
//如果新插入的key大于t的key，t等于t的右边节点
else if (cmp > 0)
t = t.right;
else
//如果两个key相等，新value覆盖原有的value，并返回原有的value
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);
}
//将新插入的节点作为parent节点的子节点
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新插入key小于parent的key,则e作为parent的左子节点
if (cmp < 0)
parent.left = e;
//如果新插入key小于parent的key，则e作为parent的右子节点
else
parent.right = e;
//修复红黑树
fixAfterInsertion(e);
size ;
modCount ;
return null;
}
//插入节点后修复红黑树
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
//直到x节点的父节点不是根，且x的父节点是红色
while (x != null && x != root && x.parent.color == RED) {
//如果x的父节点是其父节点的左子节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取x的父节点的兄弟节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果x的父节点的兄弟节点是红色
if (colorOf(y) == RED) {
//将x的父节点设置为黑色
setColor(parentOf(x), BLACK);
//将x的父节点的兄弟节点设置为黑色
setColor(y, BLACK);
//将x的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果x的父节点的兄弟节点是黑色
else {
//TODO 对应情况第二种，左右节点旋转
//如果x是其父节点的右子节点
if (x == rightOf(parentOf(x))) {
//将x的父节点设为x
x = parentOf(x);
//右旋转
rotateLeft(x);
}
//把x的父节点设置为黑色
setColor(parentOf(x), BLACK);
//把x的父节点父节点设为红色
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
}
//如果x的父节点是其父节点的右子节点
else {
//获取x的父节点的兄弟节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//只着色的情况对应的是最开始例子，没有旋转操作，但是要对应多次变换
//如果x的父节点的兄弟节点是红色
if (colorOf(y) == RED) {
//将x的父节点设置为黑色
setColor(parentOf(x), BLACK);
//将x的父节点的兄弟节点设为黑色
setColor(y, BLACK);
//将X的父节点的父节点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
//将x设为x的父节点的节点
x = parentOf(parentOf(x));
}
//如果x的父节点的兄弟节点是黑色
else {
//如果x是其父节点的左子节点
if (x == leftOf(parentOf(x))) {
//将x的父节点设为x
x = parentOf(x);
//右旋转
rotateRight(x);
}
//将x的父节点设为黑色
setColor(parentOf(x), BLACK);
//把x的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//将根节点强制设置为黑色
root.color = BLACK;
}
TreeMap的插入节点和普通的排序二叉树没啥区别，唯一不同的是，在TreeMap 插入节点后会调用方法fixAfterInsertion(e)来重新调整红黑树的结构来让红黑树保持平衡。
我们重点关注下红黑树的fixAfterInsertion(e)方法，接下来我们来分别介绍两种场景来演示fixAfterInsertion(e)方法的执行流程。
第一种场景：只需变色即可平衡
同样是拿这颗红黑树举例，现在我们插入节点 51。
当我们需要插入节点51的时候，这个时候TreeMap 的 put 方法执行后会得到下面这张图。
