红黑树 结构内部算法解析

 /** From CLR */
    private void fixAfterInsertion(Entry x) {
        x.color = RED;

while (x != null && x != root && x.parent.color == RED) {
//当前插入节点的父节点是 当前节点祖先节点的 左子节点 进入
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//得到当前节点祖先节点的右子节点
                Entry 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 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 p) {
        if (p != null) {
            Entry 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 p) {
        if (p != null) {
            Entry 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;
        }
    }