数据结构_红黑树

╰半夏微凉° 2022-05-22 13:18 334阅读 0赞

## 红黑树 ##

红黑树也是属于一种BBST。在之前介绍的[伸展树][Link 1]中，虽然实现简单，分摊复杂度低，但是最坏情况下的操作需要O(n)时间，无法适用于对单次效率敏感的场合。相反的，之前介绍的[AVL树][AVL]尽管可以保证最坏情况下的单次操作，但是要在节点中嵌入平衡因子等标识；更重要的是，删除操作之后可能需要多达O(logn)次旋转。红黑树是针对后一不足的改进。通过为节点指定颜色，合理动态调整。它可以保证：在每一次插入或删除操作之后的重平衡过程中，全树的拓扑结构更新只涉及常数个。虽然最坏情况下要涉及多达O(logn)个节点染色，但是分摊意义仅为O(1)。红黑树的“适度平衡”的标准为：**任一节点左、右子树的高度相差不过两倍。**（相比于AVL树放宽了平衡条件）

**红黑树结构与定义**  
![这里写图片描述][70]  
由红、黑两类节点组成的BST，统一的增设外部节点NULL，使之成为真二叉树（预处理），即统一的引入n+1个外部节点。  
由红、黑两色节点组成的二叉搜索树若满足以下条件，即为红黑树。  
**1、树根始终为黑色。**  
**2、外部节点均为黑色。**  
**3、其余节点若为红色，则孩子节点必为黑色。（红之子、之父必黑）**  
**4、从任一外部节点到根节点的沿途，黑节点的数目相等。（黑深度）**  
说明：根据上面的条件1和条件2可以得知，红节点均为内部节点，且其父节点及左、右孩子必然存在。条件3意味着红节点之父必为黑色，因此树中任一通路都不含相邻的红节点。从根节点通往任一节点的沿途，黑节点都不少于红节点。除去根节点本身，沿途所经过黑节点的总数称为该节点的黑深度（根节点的黑深度为0）。由条件4可进一步得知，在从任一节点通往其任一后代外部节点的沿途，黑节点总数相等。除去外部节点，沿途所经过黑节点的总数为该节点的黑高度，根节点的黑高度为全树的黑高度，在数值上与外部节点的黑深度相等。

*  (2,4)-树  
    红黑树与4阶B-树之间，存在密切的联系，经过适当的转换之后，二者相互等价。即：每一颗红黑树，都对应于一颗(2,4)树。  
    具体的变换：自顶而下逐层考察红黑树各个节点。每遇到一个红节点，都将对应的子树整体提升一层，从而与其父节点(必黑)水平对齐，二者之间的连边相应的调整问横向，将黑节点与其红孩子关键码合并为超级节点。下面根据四种情况给出了具体的转换过程。  
    ![这里写图片描述][70 1]  
    由上图可见，每一颗红黑树都等价于一颗(2,4)-树；前者的每一个节点都对应于后者的一个关键码。通往黑节点的边，对黑高度有贡献，在(2,4)-树中得以保留；通往红节点的边对黑高度没有贡献，在(2,4)-树中对应于节点内部一对相邻的关键码。

--------------------

红黑树的平衡性  
与二叉搜索树一样，红黑树的性能首先取决于其平衡性。定理：N个（含扩充的外部）节点组成的红黑树T，高度h=O(logN)，更严格地，有：  
log2(N+1)<=h<=2log2(N+1)  
证明：  
![这里写图片描述][70 2]  
左侧得到“<=”显然成立，这里证明右侧的“<=”。  
若将T的黑高度记为H，则H也是T所对应(2,4)-树的高度，因此有：  
H<=log2(N+1)  
另一方面有任一个通路不含相邻的红节点则：  
h<=2H<=log2(N+1)=O(logN)  
也就是说，尽管红黑树（任一节点左、右子树的高度相差不过两倍。）不能像AVL树那样平衡，但是其高度可以保证在最小高度的两倍以内，保持了适度平衡。

--------------------

**红黑树接口定义**  
为了方便红黑树算法的描述，这里使用了相关的宏定义：

#define IsBlack(p) ( ! (p) || ( RB_BLACK == (p)->color ) ) //外部节点也视作黑节点
     #define IsRed(p) ( ! IsBlack(p) ) //非黑即红
     #define BlackHeightUpdated(x) ( /*RedBlack高度更新条件*/ \
        ( stature( (x).lc ) == stature( (x).rc ) ) && \
        ( (x).height == ( IsRed(& x) ? stature( (x).lc ) : stature( (x).lc ) + 1 ) ) \
     )

可以根据BST模板类，派生出RedBlack模板类如下：

#include "BST/BST.h" //基于BST实现RedBlack
     template <typename T> class RedBlack : public BST<T> { //RedBlack树模板类
     protected:
        void solveDoubleRed ( BinNodePosi(T) x ); //双红修正
        void solveDoubleBlack ( BinNodePosi(T) x ); //双黑修正
        int updateHeight ( BinNodePosi(T) x ); //更新节点x的高度，黑高度
     public:
        BinNodePosi(T) insert ( const T& e ); //插入（重写）
        bool remove ( const T& e ); //删除（重写）
     // BST::search()等其余接口可直接沿用
     };

这里直接使用常规[二叉搜索树][Link 2]的search()操作，并且根据红黑树的重平衡规则与算法，重写了insert()和remove()接口。  
此外，此处的height不再是值常规的树高，而是红黑树的黑高度，节点的黑高度更新有三种情况：1、左、右孩子的黑高度不想等；2、作为红节点，黑高度与其孩子不想等；3、作为黑节点，黑高度不等于孩子的黑高度加1。实现如下：

template <typename T> int RedBlack<T>::updateHeight ( BinNodePosi(T) x ) { //更新节点高度
        x->height = max ( stature ( x->lc ), stature ( x->rc ) ); //孩子一般黑高度相等，除非出现双黑
        return IsBlack ( x ) ? x->height++ : x->height; //若当前节点为黑，则计入黑深度
     } //因统一定义stature(NULL) = -1，故height比黑高度少一，好在不致影响到各种算法中的比较判断

**红黑树节点插入算法实现**  
为了更好的理解红黑树，一定要时刻想象其影子(2,4)-树，这样可以更好的理解。  
插入接口的实现如下：

template <typename T> BinNodePosi(T) RedBlack<T>::insert ( const T& e ) { //将e插入红黑树
        BinNodePosi(T) & x = search ( e ); if ( x ) return x; //确认目标不存在（留意对_hot的设置）
        x = new BinNode<T> ( e, _hot, NULL, NULL, -1 ); _size++; //创建红节点x：以_hot为父，黑高度-1
        solveDoubleRed ( x ); return x ? x : _hot->parent; //经双红修正后，即可返回
     } //无论e是否存在于原树中，返回时总有x->data == e

很容易知道，当插入一个节点之后会引起树的结构变化，可能会使的其不再满足红黑树的条件，这里为了说明将上述条件列出：  
**1、树根始终为黑色。**  
**2、外部节点均为黑色。**  
**3、其余节点若为红色，则孩子节点必为黑色。（红之子、之父必黑）**  
**4、从任一外部节点到根节点的沿途，黑节点的数目相等。（黑深度）**  
为了说明失衡的情况，举一个实例：

--------------------

现拟插入关键码e（假定目标节点不存在），按照BST的常规算法，将其插入。  
![这里写图片描述][70 3]  
此时x=insert(e)必为末端节点，假设x的父亲p=x->parent存在。下面将x染红（除非他是根），这样条件1、条件2以及条件4都可以满足，但是条件3不一定满足。（圆形红色节点，方形黑色节点，八角形不确定）例如当p为红色时就不满足，如下图所示：  
![这里写图片描述][70 4]  
此时就会出现非法的情况，将其称为双红缺陷（double\_red,p->color==x->color==R）。

--------------------

**双红缺陷修复**  
还是对应于上图，为了修复双红缺陷，我们要考虑几个节点：  
![这里写图片描述][70 5]  
要根据**u**的颜色，分为两种情况处理：

1、RR-1：u->color==B  
对应于这种情况如下图所示：  
![这里写图片描述][70 6]  
此时，x、p和g的四个孩子（可能为外部节点）全为黑，且黑高度相同。（还有对称的另两种情况）  
参照[AVL树][AVL]中“3+4”重构，将节点x、p、g以及四颗子树按中序组合为：T0 < a < T1 < b < T2 < c < T3。  
![这里写图片描述][70 7]  
然后在进行重染色，b转黑，a或c转红。  
从B-树的角度来看，调整之前之所以是非法的，是因为在某个三叉节点中插入红关键码，使得原黑关键码不在居中（RRB或BRR，出现相邻的红关键码）。调整之后的效果相当于在新的四叉节点中，三个关键码的颜色改为RBR。  
![这里写图片描述][70 8]

2、RR-2:u->color==R  
此时等同于超级节点发生上溢，如下所示（还有对称的两种情况）：  
![这里写图片描述][70 9]  
此时，可以说是在四阶B-树中修复上溢。  
从红黑树的角度看，就是进行一次染色，p与u转黑，g转红，如下图所示：  
![这里写图片描述][70 10]

从B-树的角度看，修复一次上溢的过程为：节点分裂，关键码g上升一层，如下图所示：  
![这里写图片描述][70 11]

虽然上述过程可以修复这一局部，但是也有可能继续向上传递，即g与其parent再次构成双红。  
如果真的如此，可等效的将g视作新插入的节点区分上面两种情况，继续套用上述两种方法，知道所有条件满足或者抵达树根（最多迭代O(logn)次），如果真的达到树根，则应该将g恢复为黑色，整棵树的高度加1。

双红修正的复杂度分析：  
重构、染色等局部操作只需要常数时间，所以只需要考虑这些操作在修正过程中被调用的总次数，可以归纳为下图情况：  
![这里写图片描述][70 12]  
上述流程图的结果即是：  
![这里写图片描述][70 13]

因此，其中**至多做O(logn)次节点染色，一次“3+4”重构操作。红黑树的每一次插入操作，都可在O(logN)时间内完成**

双红修正算法实现如下：

/******************************************************************************************
      * RedBlack双红调整算法：解决节点x与其父均为红色的问题。分为两大类情况：
      *    RR-1：2次颜色翻转，2次黑高度更新，1~2次旋转，不再递归
      *    RR-2：3次颜色翻转，3次黑高度更新，0次旋转，需要递归
      ******************************************************************************************/
     template <typename T> void RedBlack<T>::solveDoubleRed ( BinNodePosi(T) x ) { //x当前必为红
        if ( IsRoot ( *x ) ) //若已（递归）转至树根，则将其转黑，整树黑高度也随之递增
           {  _root->color = RB_BLACK; _root->height++; return;  } //否则，x的父亲p必存在
        BinNodePosi(T) p = x->parent; if ( IsBlack ( p ) ) return; //若p为黑，则可终止调整。否则
        BinNodePosi(T) g = p->parent; //既然p为红，则x的祖父必存在，且必为黑色
        BinNodePosi(T) u = uncle ( x ); //以下，视x叔父u的颜色分别处理
        if ( IsBlack ( u ) ) { //u为黑色（含NULL）时
           if ( IsLChild ( *x ) == IsLChild ( *p ) ) //若x与p同侧（即zIg-zIg或zAg-zAg），则
              p->color = RB_BLACK; //p由红转黑，x保持红
           else //若x与p异侧（即zIg-zAg或zAg-zIg），则
              x->color = RB_BLACK; //x由红转黑，p保持红
           g->color = RB_RED; //g必定由黑转红
     / 以上虽保证总共两次染色，但因增加了判断而得不偿失
     / 在旋转后将根置黑、孩子置红，虽需三次染色但效率更高
           BinNodePosi(T) gg = g->parent; //曾祖父（great-grand parent）
           BinNodePosi(T) r = FromParentTo ( *g ) = rotateAt ( x ); //调整后的子树根节点
           r->parent = gg; //与原曾祖父联接
        } else { //若u为红色
           p->color = RB_BLACK; p->height++; //p由红转黑
           u->color = RB_BLACK; u->height++; //u由红转黑
           if ( !IsRoot ( *g ) ) g->color = RB_RED; //g若非根，则转红
           solveDoubleRed ( g ); //继续调整g（类似于尾递归，可优化为迭代形式）
        }
     }

**红黑树删除算法实现**  
删除算法的实现如下：

template <typename T> bool RedBlack<T>::remove ( const T& e ) { //从红黑树中删除关键码e
        BinNodePosi(T) & x = search ( e ); if ( !x ) return false; //确认目标存在（留意_hot的设置）
        BinNodePosi(T) r = removeAt ( x, _hot ); if ( ! ( --_size ) ) return true; //实施删除
     // assert: _hot某一孩子刚被删除，且被r所指节点（可能是NULL）接替。以下检查是否失衡，并做必要调整
        if ( ! _hot ) //若刚被删除的是根节点，则将其置黑，并更新黑高度
           { _root->color = RB_BLACK; updateHeight ( _root ); return true; }
     // assert: 以下，原x（现r）必非根，_hot必非空
        if ( BlackHeightUpdated ( *_hot ) ) return true; //若所有祖先的黑深度依然平衡，则无需调整
        if ( IsRed ( r ) ) //否则，若r为红，则只需令其转黑
           { r->color = RB_BLACK; r->height++; return true; }
     // assert: 以下，原x（现r）均为黑色
        solveDoubleBlack ( r ); return true; //经双黑调整后返回
     } //若目标节点存在且被删除，返回true；否则返回false

与插入算法类似，删除一个节点同样可能使得其不在满足红黑树的定义，例如考虑下面情况。

--------------------

为了删除关键码e，首先调用标准接口BST::search(e)查找。（这里假设查找成功）  
首先按照BST常规算法，执行：

r=removeAT（x,_hot）;//

x由孩子r接替，另一孩子记作w(即是黑的NULL)如（此时，条件1和条件2依然满足，但是条件3和条件4不一定满足。）：  
![这里写图片描述][70 14]

此时，情况易于处理，如上图所示，若x与r颜色不同，即可按上图处理就可以解决，即：若x为红色，将x替换成r之后即可复原；若x为黑色，只要在删除后将r反转成黑色即可复原。但是，如果x与r都为黑，就会出现下面情况（双黑）：  
![这里写图片描述][70 15]  
此时，在删除操作之后，全树的黑深度不在统一，原B-树中x所属节点下溢，这种现象也被称为双黑现象。

--------------------

**双黑缺陷修复**  
为了修复双黑缺陷，我们要考察上图中的几个节点：  
![这里写图片描述][70 16]  
此时分为四种情况处理：

1、BB-1：s为黑，且至少有一个红色的孩子t（其余情况与下面类似）。  
![这里写图片描述][70 17]  
对t、s和p做“3+4”重构：重命名为：a、b、c。r保持黑色，a和c染黑；b继承p的原色。  
对应的B-树，以上的操作等效于（通过关键码的旋转，消除超级节点的下溢）：  
![这里写图片描述][70 18]  
如此，红黑树性质在全局得以恢复（删除完成）。

2、BB-2R：s为黑，且两个孩子均为黑；p为红  
首先将红黑树转换成对应的B-树：  
![这里写图片描述][70 19]  
此时会发生一次下溢，但是这个时候不能向左右兄弟借出，因此采用合并操作，如下：  
![这里写图片描述][70 20]  
最后反向变换成对应的红黑树：  
![这里写图片描述][70 21]

最后，从红黑树的角度来看，即是：r保持黑；s转红；p转黑。另外由于关键码p原为红色，所以在关键码所属的节点中，其做货有必然还有一个黑色关键码（不可能同时存在），这也就意味着，在关键码p从中取出之后不可能引发下溢。此时红黑树性质在全局得以恢复。

3、BB-2B：s为黑，且两个孩子均为黑；p为黑  
同样站在B树的角度来分析：  
![这里写图片描述][70 22]  
这种情况与情况2的不同的是，由于P是黑色的，它独自一个构成超级节点，在其被借出之后会使得下溢向上传递，好在高度必上升一层，最多O(logN)步。  
从红黑树的角度来看：s转红；r与p保持黑色（拓扑结构未改变）。

3、BB-3：s为红（其孩子均为黑）  
同样站在B-树的角度：  
![这里写图片描述][70 23]  
经过转换zag(p)或zig(p)；红s转黑，黑p转红。虽然转换之后黑高度异常，但是r有了一个新的黑兄弟s’，即转换成了上述的几种情况（由于p转红，所以只可能为，第一种和第二种情况）。于是，再只经过一轮调整就可以恢复。

复杂度分析：  
其中涉及的重构、染色等局部操作，都可以在常数时间内完成，所以只用统计操作次数。用下图表示上面四种情况：  
![这里写图片描述][70 24]  
对应可解释为下图：  
![这里写图片描述][70 25]  
综合以上可以概括：  
红黑树的每一删除操作都可以在O(logn)内完成，其中，至多作1、O(logn)次重染色；2、一次“3+4”重构；3、一次单旋。不难确认，一旦在某部迭代中做过节点的旋转调整，整个修复就会随即完成。与双红修正一样，双黑修正只涉及常数次的拓扑结构调整（**与AVL树最本质的一项差异**）。

双黑修正算法实现如下：

/******************************************************************************************
      * RedBlack双黑调整算法：解决节点x与被其替代的节点均为黑色的问题
      * 分为三大类共四种情况：
      *    BB-1 ：2次颜色翻转，2次黑高度更新，1~2次旋转，不再递归
      *    BB-2R：2次颜色翻转，2次黑高度更新，0次旋转，不再递归
     *    BB-2B：1次颜色翻转，1次黑高度更新，0次旋转，需要递归
      *    BB-3 ：2次颜色翻转，2次黑高度更新，1次旋转，转为BB-1或BB2R
      ******************************************************************************************/
     template <typename T> void RedBlack<T>::solveDoubleBlack ( BinNodePosi(T) r ) {
        BinNodePosi(T) p = r ? r->parent : _hot; if ( !p ) return; //r的父亲
        BinNodePosi(T) s = ( r == p->lc ) ? p->rc : p->lc; //r的兄弟
        if ( IsBlack ( s ) ) { //兄弟s为黑
           BinNodePosi(T) t = NULL; //s的红孩子（若左、右孩子皆红，左者优先；皆黑时为NULL）
           if ( IsRed ( s->rc ) ) t = s->rc; //右子
           if ( IsRed ( s->lc ) ) t = s->lc; //左子
           if ( t ) { //黑s有红孩子：BB-1
              RBColor oldColor = p->color; //备份原子树根节点p颜色，并对t及其父亲、祖父
           // 以下，通过旋转重平衡，并将新子树的左、右孩子染黑
              BinNodePosi(T) b = FromParentTo ( *p ) = rotateAt ( t ); //旋转
              if ( HasLChild ( *b ) ) { b->lc->color = RB_BLACK; updateHeight ( b->lc ); } //左子
              if ( HasRChild ( *b ) ) { b->rc->color = RB_BLACK; updateHeight ( b->rc ); } //右子
              b->color = oldColor; updateHeight ( b ); //新子树根节点继承原根节点的颜色
           } else { //黑s无红孩子
              s->color = RB_RED; s->height--; //s转红
              if ( IsRed ( p ) ) { //BB-2R
                 p->color = RB_BLACK; //p转黑，但黑高度不变
              } else { //BB-2B
                 p->height--; //p保持黑，但黑高度下降
                 solveDoubleBlack ( p ); //递归上溯
              }
           }
        } else { //兄弟s为红：BB-3
           s->color = RB_BLACK; p->color = RB_RED; //s转黑，p转红
           BinNodePosi(T) t = IsLChild ( *s ) ? s->lc : s->rc; //取t与其父s同侧
           _hot = p; FromParentTo ( *p ) = rotateAt ( t ); //对t及其父亲、祖父做平衡调整
           solveDoubleBlack ( r ); //继续修正r处双黑——此时的p已转红，故后续只能是BB-1或BB-2R
        }
     }

[Link 1]: https://blog.csdn.net/xc13212777631/article/details/80773918
[AVL]: https://blog.csdn.net/xc13212777631/article/details/80760427
[70]: /images/20220522/403f235fbf0b4e4f856e75720053ebd7.png
[70 1]: /images/20220522/1ac418ce85634c11a67a35981834d104.png
[70 2]: /images/20220522/f76d526e73554d0ea58e0cfb69d21bad.png
[Link 2]: https://blog.csdn.net/xc13212777631/article/details/80752323
[70 3]: /images/20220522/5436f1f97f2944a18c4f09918644e18d.png
[70 4]: /images/20220522/c14e02dff86c4e03b0c29858a560baa5.png
[70 5]: /images/20220522/b7aaa238041e47fc99c5510fb016d069.png
[70 6]: /images/20220522/eea27568cb80465cb67710eef97562fc.png
[70 7]: /images/20220522/ad11c9ddea31451982fed00de10d3fc4.png
[70 8]: /images/20220522/a11f970908834585bee2940cf31b02eb.png
[70 9]: /images/20220522/446fc3b99fd949c4b170ad74ba3958af.png
[70 10]: /images/20220522/82128b0da50542e39b92925ef57b0bba.png
[70 11]: /images/20220522/45594471296b4daaa2a7dd585ab8ac04.png
[70 12]: /images/20220522/867e2afeace14a44891b25b96a9b16fc.png
[70 13]: /images/20220522/0525e80621424752b235f28e842530e0.png
[70 14]: /images/20220522/7dc5b8e99d11418f92401841488b8901.png
[70 15]: /images/20220522/b103bffaab064f4d9ddd99bad62ef83c.png
[70 16]: /images/20220522/72e31d732639456e982d2277225eb69e.png
[70 17]: /images/20220522/167fe3790e5a4522a5c89e4b1a16ac87.png
[70 18]: /images/20220522/050a4a5423c44fa3923bd2e894486470.png
[70 19]: /images/20220522/cf33d90cb1524482b7e68e95a180b53b.png
[70 20]: /images/20220522/782a41a00e9d4386b9fb71a053935623.png
[70 21]: /images/20220522/b769749273be43e881e1d5b6acf0ab20.png
[70 22]: /images/20220522/545b8f42324147819e84a06c0672237e.png
[70 23]: /images/20220522/87a3f8fa36c54a13a0c089d5a84baff4.png
[70 24]: /images/20220522/5c3be28237a144c38f6ce1490ad9d564.png
[70 25]: /images/20220522/ce2d5d7e1b91448ebcc014b392a97d48.png