红黑树定义

红黑树是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

每个节点要么是黑色，要么是红色。
根节点是黑色。
每个叶子节点（NIL）是黑色，叶子节点是为NULL的节点。
每个红色节点的两个子节点一定都是黑色。
任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
如果一个结点存在黑子节点，那么该节点肯定有两个子节点，因为需要满足性质5

需要注意的是，红黑树并不是一个完美平衡二叉查找树，即左右子树的高度会大于1，但左子树和右子树的黑节点的层数是相等的，称为黑色完美平衡。
如下是一个红黑树，并且图中给出一些节点定义：

红黑树自平衡操作

左旋

以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，旋转节点变为其右子节点的左子节点，右子节点的左子节点变为旋转节点的右子节点，旋转节点的左子结点保持不变。
左旋只影响了 旋转节点和其右子树的结构 ，其他保持不变，并且不会影响父节以上的结构，属于 局部调整。

右旋

以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，旋转节点变为其左子节点的右子节点，左子节点的右子节点变为旋转节点的左子节点，旋转节点的右子结点保持不变。
右旋只影响了 旋转节点和其左子树的结构，其他保持不变，并且不会影响父节以上的结构，属于 局部调整。

变色

节点从黑变为红，红变为黑。

红黑树查找

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异。查找时间复杂度O(log N)。

红黑树插入

红黑树插入包括两部分：1. 插入位置查找；2. 插入节点之后的自平衡。

插入位置查找

查找位置查找操作和普通查找类似，流程图如下：

插入节点后的自平衡

插入自平衡所面临以下几种情况：

插入的节点应为 红色节点。红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。
以下统一将上图中的叔叔节点描述为兄弟节点。

情景1 - 红黑树为空树

红黑树为空树的情况下，直接把插入节点作为根节点，并把节点颜色变为黑色。

情景2 - 插入节点的Key已经存在

插入节点的Key已经存在，此时红黑树已经是平衡的，那么只需要更新当前值为插入节点的值，并把插入节点的颜色改为当前节点的颜色。

情景3 - 插入节点的父节点为黑色节点

插入节点的父节点为黑色节点时，将插入节点的颜色变为红色，直接插入即可，因为红色的节点并不会影响黑色完美平衡。

情景4 - 插入节点的父节点为红色节点

插入节点的父亲节点是红色节点时，需要分多次情况讨论。
需要注意的是：当插入节点的父亲节点是红色节点时，则一定有祖父节点，因为红黑树的根节点规定为黑色节点。

情景4.1：父节点的兄弟节点存在并且为红色节点

父节点为红色且兄弟节点也为红色，根据红黑树性质4可知，祖父节点一定为黑色节点。
自平衡操作：将P和S设置黑色；PP设置为红色；将PP设置为当前插入节点，继续自底向上进行自平衡（因为PP的父亲节点可能为红色节点，这样就违反了红黑树性质4）。

特殊情况：PP刚好为根结点时，那么根据性质2，必须把PP重新设为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。

情景4.2：父节点的兄弟节点不存在或为黑色节点，并且插入节点的父亲节点是祖父节点的左子节点

上述情况又可以分为下述两种情况：

情景4.2.1：插入节点是父节点的左子节点

自平衡操作：将P设为黑色；将PP设为红色；对PP进行右旋

情景4.2.2：插入节点是父节点的右子节点

自平衡操作：对P进行左旋；将P设置为插入节点；得到情景4.2.1

情景4.3：父节点的兄弟节点不存在或为黑色节点，并且插入节点的父亲节点是祖父节点的右子节点

情景4.3.1：插入节点是父节点的右子节点

自平衡操作：将P设为黑色；将PP设置为红色；对PP进行左旋

情景4.3.2：插入节点是父节点的左子节点

自平衡操作：对P进行右旋；将P设置为插入节点；得到情景4.3.1

示例：

画出插入自平衡流程图：

红黑树删除

删除位置查找

查找位置查找操作和普通查找类似，可以复用。

删除之后自平衡

完成删除后，需要找到一个替代节点去替代删除之后的节点位置。主要存在以下三种替代情况：

删除结点无子节点，直接删除；
若删除节点只有一个子节点，用子节点替换删除节点；
若删除节点有两个子节点，用后继节点（大于删除节点的最小节点）替换删除节点。

下面提供一个找节点的前驱节点和后继节点方法（中序遍历的前序节点和后继节点）：

根据上面所描述的替换思路，可得到一个重要的删除思路：要删除某个节点，可以和它的替换节点交换（元素值的交换），从而将删除节点操作变为删除替换节点的操作，而替换节点总是在二叉树末端，达到简化删除效果。也即上述所描述的情况都可以转为情况1进行删除操作。
例如：要删除P节点，P节点的替换节点为R节点（将替换节点R放置在P处，也是符合二叉查找树定义的），那么可以通过删除替换节点R来完成删除操作。当红黑树达到平衡之后，将替换节点R与删除节点P的元素值相互交换，再删除替换节点R，即可完成最后的删除操作。

删除自平衡所面临以下几种情况：

为了更好理解，做如下约定：

灰色节点表示它可以是红色也可以是黑色。
R是替代节点，在删除前，它还在原来所在位置参与树的子平衡，平衡后再与删除节点的元素值进行交换，最后将R节点删除，删除完成。

情景1 - 替换节点是红色节点

替换节点和删除节点的元素值相互交换后，由于替换结点时红色，删除也了不会影响红黑树的平衡，所以直接删除。
自平衡操作：交换替换节点和删除节点的值即可完成自平衡

情景2 - 替换节点为黑色节点

情景2.1：替换节点是其父节点的左节点

情景2.1.1：替换节点的兄弟节点是红色节点

根据性质4，兄弟结点的父结点和子结点肯定为黑色。
自平衡操作：将S设为黑色；将P设为红色；对P进行左旋得到情景2.1.2.3

情景2.1.2：替换节点的兄弟节点是黑色

当兄弟节点为黑时，其父节点和子节点的具体颜色也无法确定，又分为多种情况：

情景2.1.2.1：替换节点的兄弟节点的右子节点是红色，左子节点为任意颜色

即将删除的左子树的一个黑色节点，显然左子树的黑色节点少1，然而右子树又有红色节点，那么我们直接向右子树"借"个红色个点来补充黑色节点。
自平衡操作：将S设置为P的颜色；将P设为黑色；SR设置为黑色；对P进行左旋

平衡后的红黑树怎么不满足红黑树的性质？R是即将替换的，它还参与树的自平衡，平衡后再交换到删除结点的位置，所以R最终可以看作是删除的。另外可以分别是考虑到第一次替换和自底向上处理的情况，如果只考虑第一次替换的情况，根据红黑树性质，SL肯定是红色或为Nil，所以最终结果树是平衡的。如果是自底向上处理的情况，同样，每棵子树都保持平衡状态，最终整棵树肯定是平衡的。