左右旋转

定义

左旋
以某个节点的位置作为选择轴，该节点向左侧逆时针旋转，因此该节点的右节点被拉到该节点之前的位置，旋转结束；该节点的父节点为该节点的右孩子，该节点成为右节点的左子节点，右节点之前的左孩子成为该节点的右孩子。
右旋
以某个节点的位置作为旋转轴，该节点向右侧顺时针旋转，因此该节点的左节点被拉到该节点之前的位置，旋转结束；该节点的父节点为该节点的左孩子，该节点成为左节点的右子节点，左节点之前的右孩子成为该节点的左孩子。

左右旋源码

    private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            // 当前节点的右节点旋转到当前节点的位置
            Entry<K,V> right = p.right;
            // 右节点的左节点作为当前节点的右节点
            // 这步得先做，如果放在最后right.left已经是当前节点,会产生错误
            p.right = right.left;
            if(right.left != null) {
                right.left.parent = p;
            }
            // 当前节点的父节点作为右节点的父节点
            right.parent = p.parent;
            // 根节点为null,右节点作为根节点
            if (right.parent == null) {
                root = right;
            } else {
                // 根据当前节点在父节点的位置,确定当前节点的右节点是父节点的那个孩子
                if (p.parent.left == p) {
                    p.parent.left = right;
                } else {
                    p.parent.right = right;
                }
            }
            // 当前节点作为右节点的左节点
            p.parent = right;
            right.left = p;
        }
    }

    private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            // 当前节点的左节点旋转到当前节点的位置
            Entry<K,V> left = p.left;
            // 左节点的右节点作为当前节点的左节点
            p.left = left.right;
            if(left.right != null) {
                left.right.parent = p;
            }
            // 当前节点的父节点作为左节点的父节点
            left.parent = p.parent;
            // 根节点为null,左节点作为根节点
            if (left.parent == null) {
                root = left;
            } else {
                // 根据当前节点在父节点的位置,确定当前节点的右节点是父节点的那个孩子
                if (p.parent.left == p) {
                    p.parent.left = left;
                } else {
                    p.parent.right = left;
                }
            }
            // 当前节点作为左节点的右节点
            p.parent = left;
            left.right = p;
        }
    }

节点添加

节点插入，一定是在叶子节点插入，且颜色一定是红色。

注释：红黑树本质上上234树，因此需要满足234树的特征，234树的插入一定是在叶子节点插入（平衡查找树的插入都是在叶子节点，因为插入的节点一定是某个节点的前驱或者后继节点，前驱或者后继节点在平衡查找树上一定是在叶子节点上）；插入的节点一定是红色的是为了满足红黑树的特性，减少调整次数，如果插入的是黑色节点，直接就不满足任一节点到它的可达叶子节点拥有相同黑色节点的（黑平衡）的特性。

插入场景

根据234树的等价关系发现插入总体分三种场景。

父节点是单个黑色节点（234树的叶子节点是2节点），不需要调整。
父节点是红色节点，祖父节点是黑色，叔叔节点是黑色（234树的叶子节点是3节点，首次插入时叔叔是NIL节点，下层递归上来的是非NIL节点）。
父节点是红色节点，祖父节点是黑色，叔叔节点是红色节点（234树的叶子节点是4节点）。

场景1：黑父

最简单，无需调整。

场景2：红父黑叔（叶子节点插入时叔叔是空节点，由下层递归上来的节点插入时，叔叔不再是空节点）

这种场景，则存在插入节点是父亲节点的左孩子、右孩子，父亲节点是祖父节点的左孩子、右孩子4种情况，如下：

父节点为祖父节点的左孩子，插入节点为父节点的左孩子，如下图。
- 我们首先应该想到234树中4节点的最终状态上黑下两红，然后根据最终状态通过变色、旋转两种手段转换为最终状态。
- 很显然想到，只需对祖父节点右旋，然后将右旋后的父节点变黑，左右子节点变红即可。
父节点是祖父节点的左孩子，插入节点为父节点的右孩子，如下图；

我们先根据234树获取最终状态，上黑下两红
我们发现插入的节点变成了新的父节点，祖父节点变成了新的右节点。
需要多选择一次，先对父节点22左旋，再对祖父节点30右旋，然后变色成上黑下两红即可。

父节点为祖父节点的右孩子，插入节点为父节点的右孩子，如下图，实际上情况 3与情况 1互为镜像，调整只需对祖父节点左旋，然后将左旋后的父节点涂黑，左右子节点涂红即可，此时满足红黑树。
父节点为祖父节点的右孩子，插入节点为父节点的左孩子，如下图，调整比上面的 3多一步，即将先对父节点右旋，变成 3的情况，然后后面跟 3 一样，对祖父节点进行左旋，然后将左旋后的父节点涂黑，左右子节点涂红，此时满足红黑树。实际上情况 4 与情况 2 互为镜像。

场景3：红父红叔

若插入节点的叔叔节点是红色，则对应234树中的裂变状态，上红下两黑。

此时需要对红黑树进行调整，将祖父节点改为红色，然后将父节点和叔叔节点改成黑色即可。最后将祖父节点看做向上层新插入的当前节点，重复场景1,2,3，直到满足红黑树为止。实际上这种场景无论新插入的节点为父节点的左孩子还是右孩子，父亲节点是祖父节点的左孩子还是右孩子，都是这样调整，即只需要修改颜色即可，无需旋转，如下图：

插入场景类比总结

红黑树	234树
黑父，直接插入，无需调整	2节点，直接插入无需调整
红父黑哨兵叔，则根据父节点与插入节点位置的情况进行调整，最终形成1个黑色的父节点与两个红色的子节点	3节点，直接插入，无需调整
红父红叔，则将父节点与叔叔节点变黑，再将祖父节点变红，最后将祖父节点看做向上插入的当前节点，不断向上回溯直到满足红黑树	4节点，将待插入的节点进行分裂，然后将分裂的父节点看做向上插入的当前节点，不断向上回溯直到满足234树

节点删除

概述

删除整体上来说就两种情况，删除叶子节点和非叶子节点。
如果删除的非叶子节点，我们通过中序遍历先找的要删除节点的后继或者前驱节点，然后做互换值处理，不改变颜色，
然后将删除非叶子节点的问题转换成删除后继或前驱节点。
这个后继或前驱节点也存在两种情况：
1. 叶子节点；
2. 只有右孩子或者只有左孩子的父节点（父节点黑色，孩子节点红色；因为对于234树中3节点所有父节点一定是黑色，孩子节点一定是红色）。
– 若后继或前驱节点为叶子节点，问题转换成删除叶子节点；
– 若后继或前驱节点只有右孩子或左孩子，此时只需将孩子节点的值与父节点的值互换，然后删除孩子节点即可。
综上所述，最终删除节点全部转换为了删除叶子节点，如下图：

节点”50“与后继节点”70“互换位置之后，如下图，

最后，红黑树调整完成，如下图。

删除叶子节点

红色节点

直接删除，不影响黑平衡。

黑色节点

可以类比234树理解代码，与234树一致也分为下面几种情况：

兄弟节点有的借，通过变色和选择操作获得234中等价的最终状态。
兄弟节点没得借，父节点和兄弟节点合并(红黑树中就是兄弟节点变成红色)
- 兄弟节点没得借其实分为，兄弟节点和父亲节点都没得借，需要合并节点后当成当前节点继续循环
- 兄弟节点没得借父亲节点有的借，只需要兄弟节点的颜色变成红色即可
  具体的删除细节看源码应该是最后的理解方式，下面是在源码的基础上增加了自己的理解。

    private void deleteEntry(Entry<K, V> p) {
        // 通过234树看,删除的节点无非是叶子节点和非叶子节点
        /** 对应234树中的非叶子节点,叶子节点转换成删除后继节点,
         * 后继节点在234树中就是叶子节点。
         * 判断是否是叶子节点,如果是非叶子节点需要找到后继节点
         * p 有两个孩子,表示是分支节点而非叶子节点
         **/
        if (p.left != null && p.right != null) {
            // 查找到p的后继节点s
            Entry<K, V> s = successor(p);
            // 后继节点的值覆盖当前节点p,p指向后继节点,将删除p的操作转换成删除s
            p.key = s.key;
            p.value = s.value;
            p = s;
        }

        // 删除叶子节点,234树中的叶子节点在红黑树中可能有左孩子或者右孩子
        Entry<K, V> replacement = (p.left != null ? p.left : p.right);
        // 如果存在左孩子或者右孩子
        if (replacement != null) {
            // 直接将孩子节点与p节点替换,如果p是黑色调整孩子节点的颜色为黑色
            replacement.parent = p.parent;
            if (p.parent == null) {
                root = replacement;
            } else if (p == p.parent.left) {
                p.parent.left = replacement;
            } else {
                p.parent.right = replacement;
            }
            // 将p关联的节点统统设为Null,即这一步操作实际上就是将p节点删除
            p.left = p.right = p.parent = null;

            if (p.color == BLACK) {
                // 实际上,如果非叶子节点p只有左孩子或者右孩子,那么肯定只可能有一种情况;
                // p是黑色,replacement是红色的
                fixAfterDeletion(replacement);
            }
        } else if (p.parent == null) {
            // 不存在孩子节点且是root节点
            root = null;
        } else {
            // 没有孩子节点且不是root节点
            if (p.color == BLACK) {
                // 当叶子节点p为黑色,则调用调整方法,并且p是待删除的节点
                fixAfterDeletion(p);
            }
            // 调整完成后,下面的逻辑就是将节点p的关联关系设为null,即从树上删除p节点
            if (p.parent != null) {
                if (p == p.parent.left) {
                    p.parent.left = null;
                } else if (p == p.parent.right) {
                    p.parent.right = null;
                }
                p.parent = null;
            }
        }
    }
    //  删除节点为黑色叶子节点时，调整红黑树的逻辑
    private void fixAfterDeletion(Entry<K,V> x) {
        // 因为删除黑色叶子节点,破坏了红黑树的性质,可能需要不断的回溯到root去调整。
        // 但是实际上并不需要从叶子节点开始一直做旋转调整到根,在删除节点调整红黑树中,
        // 调整不超过三次
        // 首先,当x不为根且x为黑色时，才进入循环
        while (x != root && colorOf(x) == BLACK) {
            // 当前节点是父节点的左节点
            if ( x == leftOf(parentOf(x))) {
                // 找到真正的兄弟节点,并根据兄弟节点的颜色进行调整
                Entry<K, V> sib = rightOf(x);
                // 根据234树的等价关系,如果兄弟节点是红色,红色节点向上收缩,
                // 其实sib是在234树中是当前节点的父节点,需要通过旋转找到真正的兄弟节点
                if (colorOf(sib) == RED) {
                    // 互换父节点和兄弟节点的颜色,然后对x的父节点进行左旋,
                    // sib指向真正的兄弟节点,左旋后父节点的右节点
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }

                // 找到234树上的兄弟节点后,兄弟节点没得借
                // 兄弟节点是2节点,即兄弟节点是黑色
                // 与234树删除一致,兄弟节点上移与父节点合并成一个节点,合成后的节点当做当前节点
                // 红黑树中就是黑色节点变成红色,把当前节点的父亲节点当做当前节点,重新进入while判断
                if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
                    // 如果父节点是黑色的根据while条件进行循环,相当于234树中当前节点兄弟节点没得借,父亲节点也没得借,继续循环
                    // 父节点是红色,根据while条件停止循环,调整完成,相当于234树中兄弟节点没的借,父亲节点有的借,父亲节点下来和兄弟节点合并
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    // 234树上兄弟节点有的借,兄弟的孩子至少有一个红色节点
                    // 234树上父亲节点的直接父key下移,兄弟节点中最小的key上移
                    // 先找到兄弟节点中需要上移的key
                    // 如果兄弟节点左孩子是红色,则说明最小的key是左孩子,需要右旋和变色操作
                    if (colorOf(rightOf(sib)) == BLACK) {
                        // 右孩子为空或者黑色,左孩子是红色,表示兄弟节点在234树上是3节点
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }

                    // 234树中兄弟节点中最小的key上移,父亲节点下移
                    // 当兄弟节点的右节点为红色时(可能经过上面的调整),
                    // 兄弟节点与父节点互换颜色(因为该处逻辑兄弟节点的颜色肯定为黑色)
                    // 通过下面的选择变色达到234树的等价状态
                    // 修改兄弟节点的右孩子的颜色为为BLACK,然后对当前节点x的父节点进行左旋,
                    // 然后设置当前当前节点为root,这一步主要是为了退出循环,因为调整已经结束,x=root后就不满足选好条件了
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else {
                //下面的逻辑是判断当前节点是其父节点的右孩子的情况，与上面的逻辑是互为镜像的，所以下面就的代码就不分析了
                Entry<K,V> sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                        colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }
        setColor(x, BLACK);
    }