前面我们研究过二叉搜索树、AVL树、2-3树后，我们继续研究其变体—红黑树。
【1】红黑树的由来
2-3树的设计完全可以保证二叉树保持绝对平衡的状态，保持其性能良好。但是，将这种直白的表述写成代码实现起来并不方便，因为要处理的情况太多
因此，红黑树出现了，红黑树的背后逻辑就是2-3树的逻辑，但是由于用红黑作为标记这个小技巧，最后实现的代码量并不大。
我们来看看红黑树和2-3树的关联。
红黑树中，所有的节点都是标准的2-节点。为了体现出3-节点，这里将3-节点的两个元素用左斜红色的链接连接起来，即连接了两个2-节点来表示一个3-节点。这里红色节点标记就代表指向其的链接是红链接，黑色标记的节点就是普通的节点。
如下图所示，红链接均为左链接且没有任何一个结点同时和两条红链接相连(这样会出现4-节点)。
从上面看，把红色节点放到与父亲齐平，就是2-3树中的一个2-3节点。
从上图也能看出来，不可能有连续两个红色结点的。
所以才会有那样一条定义，叫“从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点”，因为红色节点是可以与其父节点合并为一个3-节点的。
红黑树实现的其实是一个完美的黑色平衡(所有路径上黑色结点的个数是相同的)，如果你将红黑树中所有的红色链接放平，那么它所有的叶子节点到根节点的距离都是相同的。其并没有试图保持绝对平衡或者平衡因子<=1。
【2】什么是红黑树
整体来看红黑树是一种自平衡二叉树，相对于AVL和23树(绝对平衡树)，其降低了平衡的标准，简化了为了平衡导致的调整。虽然在查找的时候性能略有下降，但是插入和删除性能得到了提升。故而综合性能优于AVL和23树。
红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。
平衡二叉树：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1
需要说明的是红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树。
如下所示，左右子树高度差为2，但其确实是一棵红黑树。
二叉查找树又名二叉搜索树，二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树： * 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。 * 左右子树均是二叉查找树 也就是二叉查找树是对左右子树结点值大小做了限制。
① 红黑树特点
红黑树首先是一棵二叉搜索树，然后区别于AVL树、23树，其并没有保证左右子树高度差小于等于1。其他特性总结如下：
红黑树首先是一棵二叉搜索树，然后区别于AVL树、23树，其并没有保证左右子树高度差小于等于1。其他特性总结如下：
根结点是黑色
节点是红色或黑色
每个叶节点（NIL或空节点）是黑色，父节点也可能是黑色结点（红黑树的叶子节点并非传统的叶子节点，红黑树的叶子节点是null节点（空节点））。
红色结点的儿子节点都是黑的
红色结点的parent一定是黑的(从每个叶子到根的所有路径上不能有两个连续的红色结点)
对于每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑色结点。如下图所示，就是一颗红黑树：
② 关于叶子结点的争论
有一种说法就是，每个叶子结点都带有两个空的黑色结点（被称为黑哨兵）。
如果一个结点只有一个左孩子，那么右孩子是一个黑哨兵。如果结点只有一个右孩子，那么左孩子是一个黑哨兵。
关于叶子结点究竟是什么，目前没有找到唯一权威说法。
上图与下图是等价的，如果以下图而言，那么叶子结点红色和黑色均有。如果以上图而言，那么叶子结点是虚结点也就是所谓的黑色哨兵。
不过网上查阅资料，大多数倾向于叶子结点是“黑色哨兵”。
③ 关于路径上相同数目的黑色结点
保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。
例如黑色结点数目为3的红黑树，其最短路径(路径指的是根节点到叶子节点)是2(黑节点-黑节点-黑节点)，其最长路径为4(黑节点-红节点-黑节点-红节点-黑节点)。
注意，这个性质是在叶子结点为“黑色哨兵”的 前提下总结的，如下图所示其是一棵红黑树，但是如果将末层结点作为叶子结点，那么最短路径为1，最长路径为3，不符合该性质。
但是如果把“黑色哨兵”作为叶子结点来看，如下图所示，其是满足于保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍该性质的。这也能证明红黑树的叶子结点是“黑色哨兵”而不是其他比如AVL树中的普通叶子结点。
④ 关于左旋和右旋
旋转大体无非就是左旋和右旋，细分又分为：LL、RR、LR、RL
我们下面举例最基本的两种左旋和右旋来回顾一下。
左旋
拎起左旋节点(27)的右子节点(35)，使左旋节点向左下沉，成为右子节点(35)的左子节点，右子节点(35)上升成为其父节点。修改原先右子节点(35)的左子节点(28)从属关系使其变成新父结点的左子节点的右结点。
假设如下结点是某棵红黑树的一部分，那么从左侧变为右侧形状，就是左旋的过程。
右旋
拎起目标结点(35)的左子节点(27)，使目标结点(35)向右下沉，成为左子节点(27)的右子节点(35)，左子节点上升成为其父节点。原先左子节点(27)的右子节点(28)变成新父节点(27)的右子节点(35)的左子结点(28)。
⑥ 每次添加新节点都默认为红色
为什么？如果插入的节点是黑色，那么一定会打破上述红黑树的特性–(对于每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑色结点)。
插入红色结点，不会打破这个特性，但是可能会引起结构调整。因为红黑树的特性决定了不能有连续的红色结点。
【3】红黑树的查找
红黑树的查找方式很简单，只要是树，查找的过程无非就是一个遍历比较过程。
如果查找的元素小于当前节点，那么查找其左子树；如果查找的元素大于当前元素，则查找其右子树。
如下所示，查找元素48。那么从根节点开始，路径为：50--35--45--48 。
【4】红黑树的插入
插入和删除会引起结构的调整，主要依据下面三个规则：
- 红色结点的儿子节点都是黑的
- 没有连续的两个红色结点(红色结点的父节点是黑色)
- 所有路径上黑色结点数目相同
插入一定是在叶子节点进行，所以我们只需要考虑叶子节点的情况。如果是空树，那么插入结点为根节点，是黑色。
① 不发生结构调整
如下所示步骤：
- 插入50，作为根节点，黑色；
- 插入45和78，红色，不涉及结构调整和颜色变化；
- 插入35，这时35和45都是红色结点，那么需要调整45结点颜色为黑色
- 为了保证
“所有路径上黑色结点数目是相同的”，需要调整78(也就是父结点的兄弟结点-uncle结点)颜色为黑色
需要注意的是，插入红色结点，除了可能引起父节点的颜色变化，还可能引起祖父结点的颜色变化。
② LL调整
父节点为黑色时，插入红色结点直接插入即可。但是父节点为红色时，继续插入红色结点，比如下图所示引起LL调整(右旋)，此时除了结构调整还需要考虑颜色变化(根据红黑树性质，不能有连续的两个红色结点)。
插入红色结点27,27与35形成连续的红色结点
LL调整，首先进行右旋，35作为新的父节点
两个连续的红色结点，那么修改父节点颜色为黑色，叶子结点45为红色。其实也就是结点交换颜色
③ LR调整
单纯的LR(先左旋后右旋)调整如下所示：
- 插入36结点红色，这时触发LR调整
- 先左旋，形成第三个图示
- 后右旋形成最后一个图示
此时可以看到，又发生了两个红色结点连续的情况。原本黑色父祖父结点45成为新的父节点(36)的右子节点。那么交换父节点(36)与右子节点(45)的颜色即可。
④ RR调整
RR调整如下所示，同LL调整一样，先旋转后改变颜色：
- 插入红色结点84
- 发生左旋，这时有两个连续的红色结点
- 交换旋转后父(80)子(78)结点颜色
⑤ RL调整
RL调整如下所示，先右旋后左旋然后调整叶子结点与父节点的颜色：
- 插入79，这时成为80的左孩子；
- 先右旋后左旋形成下图最右侧形式；
- 交换78/79结点颜色，满足红黑树的性质
其实不考虑颜色，上面这个调整就是基本的AVL树调整。可以看到此时79/80是连续的红色结点，那么需要进行颜色变换：
如果有其他情况，可以留言指出。
【5】红黑树的删除
相比于AVL树的删除，红黑树的删除麻烦在于颜色的改变。其要保证“任意路径上黑色结点的数量是相同的”，所以不仅仅只考虑旋转。再重申红黑树的旋转是为了保持一种弱平衡(相比较AVL树的平衡因子不大于1)，其主要目的是为了保证黑色结点的平衡。
下面我们分析的时候假设叶子结点是普通结点来分析。
结点删除分为四种情况：
- 删除的是红色叶子结点；
- 删除的是黑色叶子结点；
- 删除的是红色父结点；
- 删除的是黑色父结点
① 删除红色叶子结点
如下所示，删除红色叶子结点如44、76、78时，是不会引起任何变化的，直接删除即可。
红色结点的父节点必然是黑色，那么删除红色结点不会违背“任意路径黑色结点数目相同”这个性质。
那么是否会引起结构的调整呢(比如左旋和右旋)？
② 删除黑色叶子结点
删除黑色叶子结点，一定会引起结构调整！
如下所示，我们尝试删除黑色结点45。那么此时左右子树必然不满足“任意路径黑色结点数量相同”的性质。
其过程如下图所示：
删除结点45，这时根节点的左侧子树为空；
那么会导致左旋，也就是79作为新的根节点(父节点)-变成黑色；
左旋导致77这棵子树作为50的右孩子，如下图-2
对79、50、77而言，又是一个LR调整，那么继续左旋，如下图-3
下图-3显然不能保证“任意路径黑色结点数量相同”的性质，那么发生颜色调整，如下图-4
如果删除的不是45而是80呢？那么此时会发生右旋。此时对于50、79、77来讲就是RL调整。
③ 删除红色父结点
删除父节点，那么会找到其前驱结点，用前驱结点替代当前结点。这里分为两种情况：
- 前驱结点是红色；
- 前驱结点是黑色。
① 前驱结点是红色
这种情况是最简单的，直接用红色前驱结点(76)替代当前红色结点(77)即可，不会发生结构调整，不会引起颜色改变。
② 前驱结点是黑色
这里又分两种情况：前驱结点是叶子结点、前驱结点是子树结点的根结点
前驱结点是黑色叶子结点
此时不一定会引起结构调整，但是一定会导致颜色改变。比如下面这个实例，前驱结点50替代删除结点(76)，此时仍旧满足红黑树的性质，无需发生结构调整。
前驱结点非叶子结点
这种情况下，最简单就是将前驱结点整棵树向上提升一个位置。前驱结点替代删除结点(红色父节点)的位置。这时需要注意结点颜色的调整。
如下所示，删除红色父节点30，其前驱结点20非叶子结点，直接提升一位。
红黑树的性质：红色结点的子孩子一定是黑色。所以还需要调整结点10的颜色为黑色。
③ 红色父节点会不会没有前驱结点只有后继结点？
答案是不存在这种情况。
根据红黑树的性质，红色结点的子孩子必然是黑色。那么为了维持“任意路径黑色结点数目相同”这一性质，红色父节点必然有两个黑色子孩子结点。
④ 删除黑色父节点
这里总结三种情况：
- 有黑色前驱结点，如下图中的28
- 有红色前驱结点，如下图中的20
- 没有前驱结点，如下图中的30
① 前驱结点存在，且是红色
如删除上图中的20，有红色前驱结点11，这种情况很简单，直接将前驱结点替换上去并修改前驱结点的颜色为黑色即可。
最终结果如下图所示：
② 前驱结点存在，且是黑色
这种情况直接将前驱结点替换上去即可，因为颜色都是黑色，所以不会发生颜色改变。如删除上图中的根节点28，那么其有前驱结点27，直接替换作为新的根节点即可。
③ 没有前驱结点
那么也就是只有后继结点了，那么需要将后继结点作为祖父结点的孩子节点。
如删除上图中的30，那么55将作为祖父结点(60)的左孩子。由于删除结点(30)与后继结点(55)颜色不一致，所以修改55结点颜色为黑色以保持黑色结点的平衡。
最终结果如下图所示：
总结来看删除结点是主要是找前驱结点进行替换，如果不存在前驱结点，那么其后继结点(子树)上移一个位置。而无论插入还是删除，都要考虑颜色的变换。而旋转主要是为了保证“任意路径上黑色结点个数相同”这一性质的。
