红黑树
动机
Q: 在已经有了AVL之类的BBST，为什么还需要引入红黑树？
A: 我们希望数据结构具有关联性，即相邻版本之间，比如说第一次插入，和第二次插入时，树的结构不能发生太大变化， 应该可以经过O（1）次数就可以变化完成。 对于AVL树来说，插入是满足这个条件的，删除却不满足这个条件。 红黑树就满足这一特性，插入和删除操作后的拓扑变化不会超过O(1)。定义
前提：给红黑树添加外部节点，保证为真二叉树
- 树根：必为黑色，即帽子是黑色
- 外部节点：必为黑色，即靴子为黑色
- 其余节点：若为红节点，则只能有黑色孩子
- 红之子，之父必须为黑色
- 外部节点到根：途中黑节点数目相等
- 所有外部节点到根经过的黑色节点数目相同，用来控制平衡
直观解释：
提升变换后(即每一个红色节点和它的父亲平齐) 所有底层节点处于同一水平高度。 红黑树就变换成一颗2-4树，我们将红黑树的每个黑色节点和提升后的红色节点（可能没有）看做B树的一个Super节点 红黑树就完全等价于一颗B树，而且可以看到的是，因为红黑树所有外部节点到根的经过的黑色数目相同，在B树中，则 更加能体现这一特征实现
比较重要的差别在于红黑树的高度叫做黑高度，即只计算黑色节点的高度
int updateHeight(BinNodePos(T)){ //原来的高度计算方法，但现在只计算黑色节点x->height = max(x->lc->height, x->rc->height) + 1 ; x->height = max(x->lc->height, x->rc->height); if(IsBlack(x)) ++x->height; return x->height;} 插入
tips 借助B树理解红黑树
理解：
在不失一般性的情况下插入一个新节点e，我们将其染为红色。目的是尽可能的满足红黑树的4条性质。可以看到 1，2，4都满足。但是3不一定。因此e的父亲可能是黑色可能是红色。如果是黑色，插入成功返回即可。如果是红色的话 此时我们就需要解决双红冲突的问题了。双红冲突--黑色叔父
前提：当新插入节点的e的父亲为红色时，其父亲必然不是根节点，且其祖父节点必然是黑色，否则其父节点也不可能是
红色。 此时我们观察其叔父节点 情形1： 当被删除节点的兄弟为黑色的时候{:.warning} 我们不难发现- B树变换：借助B树的影子进行理解，当叔父节点为黑色时，相当于发生了这样一种情况。整个Super节点变为了 RRB的情形，此时在B树中，我们只要将其重新染为RBR的颜色即可。
- RB树变换：直接利用3+4重构的方式，依照B树染色后的图进行构造就可以得到调整后的RB树变换
node g ┌───┐ ┌ ─ ─ ─│███│────┐ └───┘ │ node p ▼ ▼ ┌───┐ node p .─. node u┌───┐ ┌ ─ ─ ─│███│─ ─ ─ ─ ┐ ┌ ─ ─ ─(red)─────┐ │███│ └───┘ `─' │ ├───┤ ▼ ▼ ▼ ▼ │***│ node e .─. node g.─. node e .─. ┌───┐ │***│ ───▶ ┌────(red)────┐ ┌─(red)──┐ ┌────(red)────┐ │███│ │***│ │ `─' │ │ `─' │ │ `─' │ ├───┤ └───┘ ▼ ▼ ▼ node u ▼ ▼ ▼ │***│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │***│ │███│ │███│ │███│ │███│ │███│ │███│ │***│ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤ └───┘ │***│ │***│ │***│ │***│ │***│ │***│ ┌───────────────────┐ │***│ │***│ │***│ │***│ │***│ │***│ │ directRB change │ │***│ │***│ │***│ │***│ │***│ │***│ └───────────────────┘ └───┘ └───┘ └───┘ └───┘ └───┘ ║ └───┘ ▲ ║ ║ ║ ║ ▼ ║ node e node p node g node e node p node g .─. .─. ┌───┐ ┌─────────────────────┐ .─. ┌───┐ .─. ┌────(red│(red)││███│───┐ │ indirectBT change │ ┌────(red││███││(red)───┐ │ `─'│ `─' │└───┘ │ └─────────────────────┘ │ `─'│└───┘│ `─' │ │ │ │ │ ══════════════════▶ │ │ │ │ ▼ ▼ ▼ node u▼ ▼ ▼ ▼ node u▼┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐│███│ │███│ │███│ │███│ │███│ │███│ │███│ │███│├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤│***│ │***│ │***│ │***│ │***│ │***│ │***│ │***││***│ │***│ │***│ │***│ │***│ │***│ │***│ │***││***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│└───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
同理，对于zag-zig的情形处理类似依然使用简单的3+4重构方式处理就可以了，还有另外俩种对称形式类似。
node g ┌───┐ ┌───────────────────┐ ─ ─ ─ ─ ─ ─│███│────┐ │ directRB change │ │ └───┘ │ └───────────────────┘ node e ▼ ▼ ┌───┐ node p node u┌───┐ ┌ ─ ─ ─│███│─ ─ ─ ─ ┐ ┌───(red)─ ─ ─ │███│ └───┘ │ `─' │ ├───┤ ▼ ▼ │ ▼ │***│ node p .─. node g.─. │ node e─. │T3*│ ───▶ ┌────(red)───┐ ┌─ (red)────┐ ▼ ┌─(red)─┐ │***│ │ `─' │ │ `─' │ ┌───┐ │ `─' │ └───┘ ▼ ▼ ▼ node u ▼ │███│ ▼ ▼ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ├───┤ ┌───┐ ┌───┐ │███│ │███│ │███│ │███│ │***│ │███│ │███│ ├───┤ ├───┤ ├───┤ ├───┤ │T0*│ ├───┤ ├───┤ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │T0*│ │T1*│ │T2*│ │T3*│ └───┘ │T1*│ │T2*│ │***│ │***│ │***│ │***│ │***│ │***│ └───┘ └───┘ └───┘ └───┘ ║ └───┘ └───┘ ▲ ║ ║ ║ ║ ▼ ║ node p node e node g node p node e node g .─. .─. ┌───┐ ┌─────────────────────┐ .─. ┌───┐ .─. ┌────(red│(red)││███│───┐ │ indirectBT change │ ┌────(red││███││(red)───┐ │ `─'│ `─' │└───┘ │ └─────────────────────┘ │ `─'│└───┘│ `─' │ │ │ │ │ ══════════════════▶ │ │ │ │ ▼ ▼ ▼ node u▼ ▼ ▼ ▼ node u▼┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐│███│ │███│ │███│ │███│ │███│ │███│ │███│ │███│├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤│***│ │***│ │***│ │***│ │***│ │***│ │***│ │***││T0*│ │T1*│ │T2*│ │T3*│ │T0*│ │T1*│ │T2*│ │T3*││***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│└───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
双红冲突--红色叔父
此时我们观察其叔父节点
情形2：当叔父节点为红色的时候 就会变成RRBR的形式，此时节点发生上溢出。在B树中我们采取的方式是分裂。- B树变换：在B树中，我们要将中位节点上溢，从而保证B树的合理性。
- RB树变换：在RB树中，我们仅仅是做了提升变换将其变为B树，所以实际上只需要改变颜色，就可以对其B树的 影子完成分层，从而完成RB树变换
- 在红黑树种，只要将一个树的颜色染为红色，就相当于在B树的影子中让其向上一层
- 染为黑色，则代表这就是B树的影子中的某一层
- 简单结论就是：在B树中的影子处于同一层的红黑树节点，黑色的节点高度必须必红色的节点高
nodeG nodeG ┌───┐ .─. ┌ ─ ─ ─ ─ ─│███│─ ─ ─ ┌──────────(red)─────┐ └───┘ │ │ `─' │ ▼ ▼ ▼ ▼ nodeP .─. nodeU .─. nodeP┌───┐ nodeU┌───┐ ┌────(red)─ ─ ┌──(red)─┐ ┌────│███│─ ─ ┌──│███│─┐ │ `─' │ │ `─' │ │ └───┘ │ │ └───┘ │ │ ▼ ▼ ▼ ───────────▶ │ ▼ ▼ ▼ ▼ nodeE .─. ┌───┐ ┌───┐ ▼ nodeE .─. ┌───┐ ┌───┐ ┌───┐ ┌─(red)─┐ │███│ │███│ ┌───┐ ┌─(red)─┐ │███│ │███│ │███│ │ `─' │ ├───┤ ├───┤ │███│ │ `─' │ ├───┤ ├───┤ ├───┤ ▼ ▼ │***│ │***│ ├───┤ ▼ ▼ │***│ │***│ │***│ ┌───┐ ┌───┐ │***│ │***│ │***│ ┌───┐ ┌───┐ │***│ │***│ │***│ │███│ │███│ │***│ │***│ │***│ │███│ │███│ │***│ │***│ │***│ ├───┤ ├───┤ └───┘ └───┘ │***│ ├───┤ ├───┤ └───┘ └───┘ └───┘ │***│ │***│ └───┘ │***│ │***│ ▲ │***│ │***│ ┌───────────────────┐ │***│ │***│ ║ │***│ │***│ │ directRB change │ │***│ │***│ ║ ║ └───┘ └───┘ └───────────────────┘ └───┘ └───┘ ║ ║ ║ nodeG ▼ ┌───┐ .─. ┌───┐ ┌─────┤???├─(red)─┤???├──┐ │ └───┘ `─' └───┘ │ nodeP nodeE nodeG nodeU ▼ ▼ .─. .─. ┌───┐ .─. ┌─────────────────────┐ nodeP nodeE nodeU ┌────(red│(red)││███││(red)───┐ │ indirectBT change │ ┌───┐ .─. ┌───┐ │ `─'│ `─' │└───┘│ `─' │ └─────────────────────┘ ┌─│███│ │(red)──┐ ┌──│███│─┐ │ │ │ │ │ ══════════════════▶ │ └───┘ │ `─' │ │ └───┘ │ ▼ ▼ ▼ ▼ ▼ │ │ │ │ │ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ▼ ▼ ▼ ▼ ▼ │███│ │███│ │███│ │███│ │███│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐├───┤ ├───┤ ├───┤ ├───┤ ├───┤ │███│ │███│ │███│ │███│ │███││***│ │***│ │***│ │***│ │***│ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤│***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***││***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│└───┘ └───┘ └───┘ └───┘ └───┘ │***│ │***│ │***│ │***│ │***│ └───┘ └───┘ └───┘ └───┘ └───┘ 这里有个中间的染色步骤，此时P，E构成新节点，他们都是红色，但是P的高度要高于E，所以讲P染成黑色。 而U是红色，U要成为新的B树节点，所以必须保证这个节点里有一个黑色，所以将U染为黑色。
相应的zigzig变化过程
nodeG nodeG ┌───┐ .─. ┌ ─ ─ ─ ─ ─│███│─ ─ ─ ┌──────────(red)─────┐ └───┘ │ │ `─' │ ▼ ▼ ▼ ▼ nodeP .─. nodeU .─. ┌───┐ nodeP nodeU┌───┐ ┌ ─ ─(red)────┐ ┌──(red)─┐ ┌ ─│███│─────┐ ┌──│███│─┐ `─' │ │ `─' │ └───┘ │ │ └───┘ │ ▼ │ ▼ ▼ ───────────▶ ▼ │ ▼ ▼nodeE .─. ▼ ┌───┐ ┌───┐ nodeE .─. ▼ ┌───┐ ┌───┐ ┌─(red)──┐ ┌───┐ │███│ │███│ ┌─(red)─┐ ┌───┐ │███│ │███│ │ `─' │ │███│ ├───┤ ├───┤ │ `─' │ │███│ ├───┤ ├───┤ ▼ ▼ ├───┤ │***│ │***│ ▼ ▼ ├───┤ │***│ │***│ ┌───┐ ┌───┐ │***│ │***│ │***│ ┌───┐ ┌───┐ │***│ │***│ │***│ │███│ │███│ │***│ │***│ │***│ │███│ │███│ │***│ │***│ │***│ ├───┤ ├───┤ │***│ └───┘ └───┘ ├───┤ ├───┤ │***│ └───┘ └───┘ │***│ │***│ └───┘ │***│ │***│ └───┘ ▲ │***│ │***│ ┌───────────────────┤***│ │***│ ║ │***│ │***│ │ directRB change │***│ │***│ ║ └───┘ └╦──┘ └───────────────────┴───┘ └───┘ ║ ║ ║ nodeG ▼ ┌───┐ .─. ┌───┐ ┌─────┤???├─(red)─┤???├──┐ │ └───┘ `─' └───┘ │ nodeE nodeP nodeG nodeU ▼ ▼ .─. .─. ┌───┐ .─. ┌─────────────────────┐ nodeE nodeP nodeU┌────(red│(red)││███││(red)───┐ │ indirectBT change │ .─. ┌───┐ ┌───┐│ `─'│ `─' │└───┘│ `─' │ └─────────────────────┘ ┌─(red)─┬─┤███├─┐ ┌──│███│─┐│ │ │ │ │ ══════════════════▶ │ `─' │ └───┘ │ │ └───┘ │▼ ▼ ▼ ▼ ▼ │ │ │ │ │┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ▼ ▼ ▼ ▼ ▼│███│ │███│ │███│ │███│ │███│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐├───┤ ├───┤ ├───┤ ├───┤ ├───┤ │███│ │███│ │███│ │███│ │███││***│ │***│ │***│ │***│ │***│ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤│***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***││***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│└───┘ └───┘ └───┘ └───┘ └───┘ │***│ │***│ │***│ │***│ │***│ └───┘ └───┘ └───┘ └───┘ └───┘
总结
至此，红黑树的插入完毕，可以看到，插入总共需要进行俩种情况的处理。
- 第一种需要进行RB树的重构，但是，只需要一次就完成了红黑树的调整。
- 第二种虽然有可能递归logN次，但是，由于并不需要进行结构调整，仅仅是进行染色。所以依然认为其满足RB 树的特点
- 即在插入后，RB树的拓扑调整最多不超过O(1)次。
删除
平凡情况——删除节点或其后继有一个为红色
RB树的删除，我们依然先调用BST的removeAt算法。被删除节点会由其右孩子(有可能不存在)添补而上。
┌───┐ ┌───┐ p│███│ │███│ └─┬─┘ └─┬─┘ ┌────┐ │ │succ│┌──────────┐ │ ┌────┐ │ └────┘│deleteNode│─┐ ▼ │succ│ ▼ │ └──────────┘x└▶.─. └────┘ ──────────▶ ┌───┐◀──────┘ ┌────(red)──────┐│ ┌────│███│────┐ ▼ `─' ▼▼ ▼ └───┘ ▼ ┌───┐ r┌───┐ ┌───┐ ┌───┐ w│nul│ ┌─┤███│ ──┐ rl│nul│ rr│???│ └───┘ │ └───┘ │ └───┘ └───┘ ▼ ▼ ┌───┐ ┌───┐ rl│nul│ rr│???│ └───┘ └───┘
我们认为被删除节点为红色，那么其左右孩子节点，父亲节点则一定为黑色。根据性质3。
首先要明白removeAt的语义，x节点最多只有一个孩子。在这里我们不妨认为其是r(r也有可能不存在，即也是外部节点） 那么另外一个孩子w则是外部节点，同样依然可以是对称的情况 当x被删除后，条件3不会受到任何影响，r接替x，rl和rr上的外部节点高度不受任何影响。理解为删除虚边之后，RB树 的节点不受影响。 按照B树的观点来理解，删除红色节点，对于Super节点不会有任何影响，因为Super节点的主要承担者是黑色节点┌───┐ ┌───┐ │???│ │???│ └─┳─┘ └─┳─┘ ┌────┐ ┃ ┃ │succ│┌──────────┐ ┃ ┌────┐ ┃ └────┘│deleteNode│─┐ ▼ │succ│ ▼ │ └──────────┘ └▶┌───┐ └────┘ ──────────▶ ┌───┐◀──────┘ ┌────│███│─ ─ ─ ┐│ ┌────│███│────┐ ▼ └───┘ ▼▼ ▼ └───┘ ▼ ┌───┐ .─. ┌───┐ ┌───┐ │nul│ ─ ─(red) ─ ┐ │nul│ │???│ └───┘ │ `─' └───┘ └───┘ ▼ ▼ ┌───┐ ┌───┐ │nul│ │███│ └───┘ └───┘
同样依然理解为删除虚边之后，黑高度不受影响。
按照B树的观点来理解，删除黑色节点，B树的Super节点会少1，因此需要补充一个黑色节点。所以补充在原位置上的红色 节点被染黑。而消失一个红色节点却不影响这个B树的高度。DoubleBlack
当俩个节点都为黑色的时候，删除一个必定会导致B树高度减少，从而不稳定。此时就分为4种情况。
情形1： 被删除节点的兄弟节点为黑色，且其有一个红色孩子，意思就是被删除节点X有一个红色的侄子， 则按照B树的观点来看，兄弟比较富裕，因此可以通过旋转的方式调整 按照RB树的观点来看，直接3+4重构即可，然后染色nodeP ┌───┐ nodeS ┌ ─ ─ ─ ─ ─│???│─ ─ ─ ┌───┐ └───┘ │ ┌──────│???│──────┐ ▼ ▼ │ └───┘ │ nodeS┌───┐ nodeX┌───┐ │ │ ┌ ─ ─│███│────┐ │███│ │ │ └───┘ │ └─┬─┘ no▼eT no▼eP ▼ │ │ ───────────▶ ┌───┐ ┌───┐ nodeT .─. ▼ ▼ ┌───│███│───┐ ┌─│███│───┐ ┌─(red)──┐ ┌───┐ ┌───┐ │ └───┘ │ │ └───┘ │ │ `─' │ │???│ nodeR│███│ │ │ │ │ ▼ ▼ ├───┤ ├───┤ ▼ ▼ ▼ ▼ ┌───┐ ┌───┐ │***│ │***│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │███│ │███│ │***│ │***│ │███│ │███│ │???│ │███│ nodeR/X ├───┤ ├───┤ │***│ │***│ ├───┤ ├───┤ ├───┤ ├───┤ │***│ │***│ └───┘ └───┘ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ ┌───────────────────┐ │***│ │***│ │***│ │***│ └───┘ └───┘ │ directRB change │ └───┘ └───┘ └───┘ └───┘ ║ └───────────────────┘ ▲ ║ ║ ▼ ║ nodeP nodeS ┌───┐ ┌───┐ ┌─────│???│────┐ ┌──────│???│──────┐ │ └───┘ │ │ └───┘ │ │ │ │ │ │ │ ┌─────────────────────┐ │ │ ▼ │ │ indirectBT change │ no▼eT no▼eP nodeT nodeS nodeX └─────────────────────┘ ┌───┐ ┌───┐ .─. ┌───┐ ┌┐ ══════════════════▶ ┌───│███│───┐ ┌─│███│───┐ ┌────(red││███││ ││ │ └───┘ │ │ └───┘ │ │ `─'│└───┘│ ├┘ │ │ │ │ │ │ │ │ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ┌───┐ ┌───┐ ┌───┐ ┌───┐┌───┐ ┌───┐ ┌───┐ ┌───┐ │███│ │███│ │???│ │███│ nodeR/X│███│ │███│ │???│ │███│nodeR ├───┤ ├───┤ ├───┤ ├───┤├───┤ ├───┤ ├───┤ ├───┤ │***│ │***│ │***│ │***││***│ │***│ │***│ │***│ │***│ │***│ │***│ │***││***│ │***│ │***│ │***│ │***│ │***│ │***│ │***││***│ │***│ │***│ │***│ └───┘ └───┘ └───┘ └───┘└───┘ └───┘ └───┘ └───┘
BB-2R
情形2
被删除节点的父亲是红色，兄弟节点和侄子全部都是黑色。{:.warning}- 此时按照B树的观点来看，兄弟节点很瘦，不足以借出关键码，因此需要合并。而又因为P节点是红色，所以从上面节点下来 也不会有影响，所以直接调整完毕
- 按照RB树的观点来看。对于含有R节点的这条通路，少了一个黑色的节点X，多了个黑色节点P，因此第4条性质保持不变。 对于含有S节点的通路来说，互换了通路上的一个红色和黑色节点。所以不会发生任何变化。
nodeP nodeP .─. ┌───┐ ┌ ─ ─ ─ ─ ─(red)─ ─ ─ ┌ ─ ─ ─ ─ ─│███│─────┐ `─' │ └───┘ │ ▼ ▼ ▼ ▼ nodeS┌───┐ nodeX┌───┐ nodeS .─. nodeR/X┌───┐ ┌────│███│────┐ │███│ ┌──── (red)───┐ │███│ │ └───┘ │ └─┬─┘ │ `─' │ ├───┤ ▼ ▼ ▼ ───────────▶ ▼ ▼ │***│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │***│ │███│ │███│ nodeR│███│ │███│ │███│ │***│ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤ └───┘ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ ║ │***│ │***│ │***│ │***│ └───┘ ║ └───┘ └───┘ └───┘ └───┘ ║ ┌───────────────────┐ ▼ │ directRB change │ ▲ └───────────────────┘ ║ ║ nodeP ║ .─. ┌ ─(red)─ ─ ┐ nodeS nodeP `─' .─. ┌───┐┌┐ nodeX nodeS ▼ ▼nodeX ┌───(red)│███│││──┐ ┌───┐ ┌┐ ┌─────────────────────┐ │ `─' └───┘└┘ │ ┌───│███│──┐ ││ │ indirectBT change │ │ │ │ │ └───┘ │ ├┘ └─────────────────────┘ │ │ │ ▼ ▼ ▼ ══════════════════▶ ▼ ▼ ▼ ┌───┐ ┌───┐ ┌───┐ ┌───────────┐ ┌───┐ ┌───┐ ┌───┐ │███│ │███│ │███│nodeR │ merge │ │███│ │███│ │███│nodeR ├───┤ ├───┤ ├───┤ └───────────┘ ├───┤ ├───┤ ├───┤ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
BB-2B
情形3
当被删除节点的父亲为黑色时，且兄弟节点，侄子节点均为黑色，此时{:.warning}- 按照B树的观点来看，依然需要合并，但是这次将上一节点的唯一节点P拉了下来，因此将导致上层节点发生下溢。
- 按照RB树的观点来看，无论是R通路还是S通路均少了一个黑色节点，因此需要继续向上调整。保证第4条性质不变。
nodeP nodeP ┌───┐ ┌───┐ ┌─────────┤███├──────┐ ┌ ─ ─ ─ ─ ─│███│─────┐ │ └───┘ │ └───┘ │ ▼ ▼ ▼ ▼ nodeS┌───┐ nodeX┌───┐ nodeS .─. nodeR/X┌───┐ ┌────│███│────┐ │███│ ┌──── (red)───┐ │███│ │ └───┘ │ └─┬─┘ │ `─' │ ├───┤ ▼ ▼ ▼ ───────────▶ ▼ ▼ │***│┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │***││███│ │███│ nodeR│███│ │███│ │███│ │***│├───┤ ├───┤ ├───┤ ├───┤ ├───┤ └───┘│***│ │***│ │***│ │***│ │***││***│ │***│ │***│ │***│ │***││***│ ║ │***│ │***│ │***│ │***│└───┘ ║ └───┘ └───┘ └───┘ └───┘ ▲ ║ ┌───────────────────┐ ║ ▼ │ directRB change │ ║ nodeP └───────────────────┘ ║ ┌───┐ ┌───│███│───┐ nodeS nodeP │ └───┘ │ .─. ┌───┐┌┐ nodeX nodeS ▼ ▼nodeX ┌───(red)│███│││──┐ ┌───┐ ┌┐ ┌─────────────────────┐ │ `─' └───┘└┘ │ ┌───│███│──┐ ││ │ indirectBT change │ │ │ │ │ └───┘ │ ├┘ └─────────────────────┘ │ │ │ ▼ ▼ ▼ ══════════════════▶ ▼ ▼ ▼ ┌───┐ ┌───┐ ┌───┐ ┌───────────┐ ┌───┐ ┌───┐ ┌───┐ │███│ │███│ │███│nodeR │ merge │ │███│ │███│ │███│nodeR ├───┤ ├───┤ ├───┤ └───────────┘ ├───┤ ├───┤ ├───┤ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ │***│ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
BB-3
情形4：
被删除节点的父亲为黑色，兄弟节点为红色{:.warning} 这是唯一一个有点，怎么说，不直接的情形- 按照B树的观点来看，并没有进行下溢操作，仅仅是简单的互换了Super节点的颜色。
- 按照RB树的观点来看，将未知问题转化成为了我们之前遇到过的已知问题。此时被删除节点的父亲为红色，其 兄弟节点为黑色，如果这个兄弟节点有红色儿子，将进入BB-1情形，如果没有，则进入BB-2R情形。幸运的是， 无论哪种情况，都比较简单。
nodeP nodeS ┌───┐ ┌───┐ ┌─────────┤███├──────┐ ┌──── │███│─────────┐ │ └───┘ │ │ └───┘ │ ▼ ▼ ▼ ▼ nodeS .─. nodeX┌───┐ ┌───┐ .─.nodeP ┌ ─ ─(red)─ ─ ┐ │███│ │███│ ┌────(red)────┐ `─' └─┬─┘ ├───┤ │ `─' │ ▼ ▼ ▼ ───────────▶ │***│ ▼ ▼ ┌───┐ ┌───┐ ┌───┐ │***│ ┌───┐ ┌───┐│███│ │███│ nodeR│███│ │***│ │███│ nodeX│███│├───┤ ├───┤ ├───┤ └───┘ ├───┤ └─┬─┘│***│ │***│ │***│ │***│ ▼ │***│ │***│ │***│ │***│ ┌───┐│***│ │***│ │***│ │***│ nodeR│███│└───┘ ║ └───┘ └───┘ └───┘ ├───┤ ║ ┌───────────────────┐ │***│ ║ │ directRB change │ ▲ │***│ ▼ └───────────────────┘ ║ │***│ ║ └───┘ nodeS nodeP nodeS nodeP ║ .─. ┌───┐ ┌───┐ .─. ┌───(red)││███│────┐ ┌───│███││(red)────┐ │ `─' │└───┘ │ ┌─────────────────────┐ │ └───┘│ `─' │ ▼ ▼ ▼ │ indirectBT change │ ▼ ▼ ▼ ┌───┐ ┌───┐ ┌┐ └─────────────────────┘ ┌───┐ ┌───┐ ┌┐ │███│ │███│ nodeX││─┐ ══════════════════▶ │███│ │███│ nodeX││─┐ ├───┤ ├───┤ └┘ │ ┌───────────┐ ├───┤ ├───┤ └┘ │ │***│ │***│ ▼ │ merge │ │***│ │***│ ▼ │***│ │***│ ┌───┐ └───────────┘ │***│ │***│ ┌───┐ │***│ │***│ nodeR│███│ │***│ │***│ nodeR│███│ └───┘ └───┘ ├───┤ └───┘ └───┘ ├───┤ │***│ │***│ │***│ │***│ │***│ │***│ └───┘ └───┘
结论
上面无论哪种情形，被删除节点的拓扑变换都不会超过O(1)的时间复杂度。
平凡情形：- 被删除节点x和其后继r不是DoubleBlack，只要将r染成黑色添补x的空位即可。
BB-1 : 被删除节点的父亲节点颜色随意。兄弟节点为黑色，有不少于一个红色侄子节点
- 重染色+旋转完成
- B树意义上的旋转
BB-2R : 被删除节点的父亲节点为红色，兄弟节点，侄子节点皆为黑色
- 重染色
- B树意义上的合并
BB-2B : 被删除节点的父亲节点为黑色，兄弟节点，侄子节点皆为黑色
- 重染色
- B树意义上的合并，DoubleBlack冲突会向上传递
BB-3 : 被删除节点的父亲为黑色，兄弟节点为红色，侄子节点自然为黑色
- 重染色
- B树意义上的无任何变换
- 情形转化为BB-1或者BB-2R
红黑树总结
学习红黑树的插入和删除，主要是明白为什么其只需要常数次拓扑变换就可以调整回来，即其到底比AVL树优秀在哪里。
并不是说去背诵它到底怎么插入，怎么删除。不难发现凡是可能造成连锁反应的操作，只会涉及染色这种操作。而 一旦涉及拓扑调整，最多俩次就调整完毕。