Question

（转）红黑树

Answer 1

红黑树是平衡二叉树的一种，是目前使用最多的一种树结构。红黑树通过对节点的染色以及巧妙的动态调整，使得树保持适度平衡。

红黑树可以保证：在每次插入或删除操作之后的重平衡过程中，全树的拓扑结构的更新仅涉及常数个节点。尽管在最坏的情况下需要对O(logn)个节点冲染色，但是就分摊意义而言，仅为O(1)个。

红黑树的适度平衡标准：任一节点左、右子树的高度相差不得超过两倍。

红黑树的条件：
（1）树根为黑色
（2）外部节点均为黑色
（3）其余节点若为红色，则其孩子节点必为黑色
（4）从任一外部节点到根节点的沿途，黑节点的数目相等
满足上面四个条件的二叉搜索树，为红黑树。

红黑树与4阶B树之间存在密切的联系，经过适当的转换之后，两者是等价的。

红黑树的插入操作：
（1）在红黑树中查找要插入的节点X，若允许插入节点X，则在该位置插入节点X
（2）节点X染为红色
（3）判断此时红黑树是否满足条件（3），若满足则插入操作完成，否则进行调整

红黑树插入新节点导致的红黑树调整，称为双红修正，其中双红修正有两种情况：RR-1和RR-2。

RR-1 u为黑的情况：
1 ~ 2次旋转，2次染色，调整随之完成
RR-2 u为红的情况：
0次旋转，3次染色，可能导致上层节点的再次双红，需要继续调整，最多O(logn)次

红黑树的删除操作：
（1）找到需要删除的节点X，若有，则删除
（2）判断删除之后的红黑树是否满足条件（3）与（4），若不满足，则进行调整

红黑树删除操作导致的红黑树调整，为双黑调整，双黑调整有四种情况。

（1）BB-1，黑s有红子t：
1 ~ 2次旋转，3次染色，调整完成
（2）BB-2-R，黑s无红子，p红：
0次旋转，2次染色，调整完成
（3）BB-2-B，黑s无红子，p黑：
0次旋转，1次染色，必然会导致再次双黑，但上升一层，继续调整
（4）BB-3，红s：
1次旋转，2次染色，转化为BB-1或者BB-2-R，继续调整

红黑的删除操作的总共耗时不会超过O(logn)次。

参考：
https://www.jianshu.com/p/e136ec79235c
《数据结构第三版》