/** 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)));
//colorOf(y) 方法如果y==null 是null 返回黑色 if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else {
//rightOf(parentOf(x)) 得到当前节点父节点 的右子节点 if (x == rightOf(parentOf(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; }
//右旋
// 什么时候需要 右旋：
// 1: 当前插入节点的父节点 是 祖先节点的左子节点
// 2: 当前插入节点的 右叔父节点 为nil 或黑色
//或者
1: 当前插入节点的父节点 是 祖先节点的右子节点
/** From CLR */ private void rotateRight(Entry<K,V> p) { if (p != null) { Entry<K,V> l = p.left; p.left = l.right; if (l.right != null) l.right.parent = p; l.parent = p.parent; if (p.parent == null) root = l; else if (p.parent.right == p) p.parent.right = l; else p.parent.left = l; l.right = p; p.parent = l; } }
//左旋
/** From CLR */ private void rotateLeft(Entry<K,V> p) { if (p != null) { Entry<K,V> r = p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent = p.parent; if (p.parent == null) root = r; else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; } }
原文：https://www.cnblogs.com/softxiaohui/p/11072119.html