写在前面
最近在研究 java 底层，由于集合框架的 Treemap 是基于红黑树实现的，最近数据结构课程刚好讲到二叉查找树和平衡树的实现，决定写一篇博客记录，顺便把算法导论这一部分啃了
红黑树
大概
红黑树顾名思义是树形结构，属于平衡搜索树的一种，基于二叉查找树和平衡二叉树的结构实现的，但其并非为完全平衡二叉树，即它的平衡因子的绝对值并非严格小于 1，由于是平衡搜索树，可以保证在最坏情况下基本动态集合操作的时间复杂度为 O(lgn)
区别
既然一种数据结构存在，那肯定有它存在的理由，对于 AVL 树来说，它是一棵带有平衡条件的二叉查找树，基于不断旋转的操作进行维护平衡，这种旋转操作往往非常耗时，特别是当插入和删除的操作特别多时，为了维护平衡必须不断进行旋转，所以对于插入和删除操作多的情况下，AVL 树的表现不尽人意，AVL 树适合于插入和删除次数比较少，但查找多的情况
对于红黑树来说，便很好的解决了这个痛点，通过降低维护平衡的代价来换取更高的效率，红黑树确保没有一条路径比其他路径长出两倍，因此是近似平衡的，弱平衡的维护使得插入和删除节点的旋转次数大大减少，插入最多进行两次旋转，删除最多进行三次旋转，但由于弱平衡，在相同节点的情况下，AVL 树的高度低于红黑树，红黑树适用于插入和删除次数多的情况
性质
- 性质 1：每个结点是红色的或者黑色的
- 性质 2：根结点是黑色的
- 性质 3：每个叶结点 (NIL) 是黑色的
- 性质 4：如果一个结点是红色的，那么它的两个子结点均为黑色的（即两个红色结点不能连在一起）
- 性质 5：任意一结点到每个叶子结点的路径都包含相等数量的黑色结点（如果一个结点存在黑色子结点，那么一定具有两个子结点）
由于黑色结点数量相同，这种平衡也被称为黑色完美平衡，由于本身也是基于二叉查找树，所以二叉查找树具有的性质他都有
红黑树在二叉查找树的基础上增加了一个存储位来表示结点的颜色，可以为 RED 或者 BLACK，新增加的结点默认为红色，由于性质 5，一条路径上黑色结点数必然相等，而插入的如果是黑色的则破坏了平衡
每个叶结点是相同的，而对每个叶结点都开辟一块空间属实浪费，于是我们可以使用一个哨兵 T.nil 进行替代，如下
从某个结点 x 出发，到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高，记为 bh(x)
一棵有 n 个内部结点的红黑树的高度至多为 2lg(n + 1)
旋转
当 x 作左旋时，假设 x 的右孩子不为 NIL，令其为 y， y 的左孩子成为 x 的右孩子，并将 y 成为 x 的父结点
当 y 作右旋时，假设 y 的左孩子不为 NIL，令其为 x， x 的右孩子成为 y 的左孩子，并将 x 成为 y 的父结点
左旋和右旋操作都在 O(1) 时间内运行完成，在旋转操作中只有指针改变，其他都不改变
左旋和右旋操作代码对称
下面是两个操作的例子
左旋：
右旋：
左旋只影响旋转结点及其右子树的结构，把右子树的左子树往自身右子树移动了
右旋只影响旋转结点及其左子树的结构，把左子树的右子树往自身左子树移动了
所以旋转操作是局部的，如果要保持红黑树的性质，则必须还加一个变色的操作，红黑树通过旋转和变色达到自平衡
查找
本身红黑树就是一棵二叉搜索树，因此红黑树的查找和二叉搜索树相同
- 从根结点开始查找，把根结点设为当前结点
- 若当前结点为空，则返回 NULL
- 若当前结点不为空，则比较 Key 值，若相等则返回当前结点，查找成功
- 若当前结点的 Key 值不相等，比较大小，如果当前结点的值较大，则往左子树继续查找
- 若当前结点的 Key 值不相等，比较大小，如果当前结点的值较小，则往右子树继续查找
插入
要想插入结点，必须找到结点的所处位置，通过查找操作查找出该结点所属的正确位置，然后新建结点建立与原树的联系，插入的结点为红色，这样可以不需要做自平衡操作，如果插入的结点为黑色，则需要进行自平衡操作维护红黑树的性质 5
插入后应根据不同情况进行变色维持平衡
情况一
红黑树为空树
这是最简单的一种情况，直接将插入结点作为根节点，由于性质 2，根节点为黑色，则将新插入的结点变色成为黑色
情况二
插入结点的 Key 已存在
由于原树已经是一棵红黑树，已经保持平衡，所以直接更新当前插入结点的颜色为替代结点的颜色，然后更新结点的值完成插入
情况三
插入结点的父结点为黑色结点
插入的结点为红色，并不影响红黑树的平衡，所以可以直接插入
情况四
插入结点的父结点为红色结点
这种情况就需要分类讨论了，不过每种小情况都是左右对称的
叔结点存在且为红色结点
- F 和 U 设为黑色
- G 设为红色
- G 设为当前插入的结点，向上递归维持平衡
简单的两步修改成功维护了子树的平衡，每条路径上的黑色结点个数相等，而且两个红色结点也没有连在一起
如果为了整棵树都能平衡则必须不断往上递归，很容易知道，红黑树的生长是自底向上的
叔结点存在且为黑色结点或者叔结点不存在，插入结点的父结点是祖父结点的左结点，插入结点是父结点的左结点
- F 设为黑色
- G 设为红色
- 对 G 进行右旋
叔结点存在且为黑色结点或者叔结点不存在，插入结点的父结点是祖父结点的右结点，插入结点是父结点的右结点
- F 设为黑色
- G 设为红色
- 对 G 进行左旋
叔结点存在且为黑色结点或者叔结点不存在，插入结点的父结点是祖父结点的左结点，插入结点是父结点的右结点
- 对F进行左旋
- F设为插入结点
- M设为黑色
- G设为红色
- 对G进行右旋
叔结点存在且为黑色结点或者叔结点不存在，插入结点的父结点是祖父结点的右结点，插入结点是父结点的左结点
- 对F进行右旋
- F设为插入结点
- M设为黑色
- G设为红色
- 对G进行左旋
例子
插入自平衡处理过程
- F 设为红色
- P 和 M 设为黑色
- 插入结点变成 F
- R 设为红色
- G 设为黑色
- 对 R 进行右旋
删除
删除算是红黑树最复杂的操作了
对于红黑树的删除操作来说，需要两个步骤：一是查找，二是替代，查找如上所述，删除后则需要选择相应结点进行替代（除非删除结点没有子结点），同时还需要维护红黑树的平衡
大致可以分为三种情况：
- 被删除结点无子结点
- 被删除结点只有一个子结点
- 被删除结点有两个子结点
每种情况又根据被删结点细分
组合1
被删结点无子结点，且被删结点为红色
这种组合的被删结点很容易知道是叶结点，而且因为为红色，直接删就好了
组合2
被删结点无子结点，且被删结点为黑色
这种组合需要处理被删结点这条路径上的黑色结点数量，由于性质 5 的存在，需要维持红黑树的平衡，处理方法较为复杂，后文细说
组合3
被删结点只有一个子结点，且被删结点为红色
这种组合并不存在，若被删结点只有一个子结点，且被删结点为红色，根据性质 4，唯一的子结点必须为黑色，而根据性质 5，每条路径上黑色结点数相等，只有一个黑色子结点造成了红黑树的不平衡，delete 为 Null 的叶结点的黑色结点数少一，不符合性质 5，这种组合并不存在
组合4
被删结点只有一个子结点，且被删结点为黑色
这种组合的子结点一定为红色，只有红色结点才能保证红黑树的性质 5 成立，直接将 delete 结点删除，用 value 代替 delete 结点的位置，将 value 染黑即可
组合5 && 组合6
被删结点有两个子结点，且被删结点为黑色或红色
被删结点有两个结点，如果此时要删除的话，则必须有一个结点替代这个位置，由于红黑树是基于二叉查找树，而二叉查找树的中序遍历即为从小到大的排列，所以我们只需要找 delete 结点的后继结点 successor 即可，此时用 successor 结点代替 delete 结点的位置，同时进行染色，这也可以相当于看作 successor 结点被删
delete 结点的后继结点一定在右子树上，必为上图两种形态中的一种
两种形态的处理方法一样，用 successor 代替 delete 后，相当于 successor 被删
若 successor 为红色，则变成了组合 1 ；若 successor 为黑色，则变成了组合 2 或 组合4
细说组合2
因为被删结点为黑色，而删除黑色结点会破坏红黑树的性质 5，为了不让性质 5 被破坏，可以采取为替代结点额外增加一个黑色，即替代结点的颜色为双黑或红黑，这样维护了性质 5，但是违背了性质 1，所以在所有操作之后再将额外的黑色移除，完成删除操作
下面结合 father 和 bro 来分析，白色结点代表可为黑色也可为红色
情况一
bro 为黑色，且有一个与其方向相同的红色子结点 son
方向一致指的是 bro 和 son 要么都为左结点，要么都为右结点
将 father 左旋，重新给 bro 上色，和原来 father 一样，将 son 染黑，方形结点储存的额外的黑色转移给 father
左右颠倒的情况也是一样的操作
情况二
bro 为黑色，且有一个与其方向不同的红色子结点 son
将 bro 右旋，重新给 son 和 bro 上色，得到情况一
左右颠倒的情况也是一样的操作
情况三
bro 为黑色，且没有红色子结点
father 若为红色，则直接将 null 中储存的额外黑色染色 father，同时将 bro 染为红色
father 若为黑色，则将 null 中储存的额外黑色储存到 father 内，即 father 此时为双黑，同时将 bro 染为红色，将 father 作为新的判断结点，遇到情况一、二继续进行调整，不断向上传递，直到除了根节点储存了额外的黑色，别的结点并没有储存，此时将额外的黑色移除，完成删除操作
情况四
bro 为红色
由于 bro 为红色，则 father 必为黑色，由于性质 5，bro 也必有两个黑色的子结点
将 father 左旋，同时 father 和 bro 重新上色，黑色的 son 变为了新的 bro，再根据情况一、二、三进行下一步操作
左右颠倒的情况也是一样的操作
写在最后
红黑树的插入和操作情况很多，需要分类一步步进行讨论，耐心地分析
算法导论中的删除操作中最具技巧性的点便是采用存两个颜色的灵活方法，方便地维护红黑树的性质，而不是硬删结点再维护平衡
如果一条路走不通，不妨想想另一种方法，毕竟最后到达目的地即可