算法导论ch13红黑树笔记与相应数据结构算法c++实现（下）

算法导论ch13红黑树笔记与相应数据结构算法c++实现（上）主要讲红黑树的概念，性质，旋转和插入操作，其链接为：https://blog.csdn.net/Yunhandu/article/details/142849395?spm=1001.2014.3001.5501
本章主要讲解红黑树的删除操作，如有错误，欢迎大家在评论区指出，如果觉得本文不错，也请各位点赞，收藏和评论！

13.4 删除（遵循第4版英文版）

与插入操作相比，删除操作要复杂不少，而不是原文中的稍微复杂一点, 尤其是后面出现的双色节点的操作，简直阴间，阅读时请保持平和心态。

从一棵红黑树中删除节点的过程是基于12.3节的TreeDeletion过程而来的。首先和之前BST一样，来个红黑树定制版的RBTransplant:

template <typename T>
void RBTree<T>::RBTransplant(RBNode<T>* toBeSubstituted, RBNode<T>* vertex) {
   
    if (toBeSubstituted->parent_ == tNil) root_ = vertex;
    else if (toBeSubstituted == toBeSubstituted->parent_->lc_) toBeSubstituted->parent_->lc_ = vertex;
    else toBeSubstituted->parent_->rc_ = vertex;
    // yes, the assignment to v.p happens unconditionally
    vertex->parent_ = toBeSubstituted->parent_;
}

过程RBTransplant和12.3节的Transplant有2点不同：

1. 第3行引用哨兵tNil而不是nullptr。
2. 第7行对vertex.parent的赋值是无条件执行：即使vertex指向哨兵（vertex = tNil），也对 vertex.parent_赋值。

过程RBDelete与12.3节的TreeDeletion类似，但多了几行代码。新增的代码用于记录节点y的踪迹，y有可能导致红黑性质的破坏。当想要删除节点z, 且此时z的子节点少于2个时，z从树中删除，并让y成为z。当z有两个子节点时，y应该是z的后继，并且y将移至树中的z位置。在节点被移除或者在树中移动前，必须记住y的颜色，并记录节点x的踪迹，将x移至树中y的原来位置，因为节点x也可能引起红黑性质的破坏。删除节点z之后，RBDelete调用辅助过程RBDeleteFixUp通过改变颜色和执行旋转来恢复红黑性质。

RBDeletion的c++实现与RBDeletion中的TreeMinimum如下:

template <typename T>
void RBTree<T>::RBDeletion(RBNode<T>* z) {
   
    RBNode<T>* y = z;
    RBColor yOriginalColor = y->color_;
    RBNode<T>* x = tNil;
    if (z->lc_ == tNil) {
   
        x = z->rc_;
        RBTransplant(z, z->rc_); // replace z by its right child
    } else if (z->rc_ == tNil) {
   
        x = z->lc_;
        RBTransplant(z, z->lc_); // replace z by its left child
    } else {
   
        y = TreeMinimum(z->rc_); // y is z's successor
        yOriginalColor = y->color_;
        x = y->rc_;
        if (y != z->rc_) {
   
            RBTransplant(y, y->rc_); // replace y by its right child
            y->rc_ = z->rc_; // z's right child becomes y's right child
            y->rc_->parent_ = y;
        } else x->parent_ = y; // in case x is tNil
        RBTransplant(z, y); // replace z by its successor y
        y->lc_ = z->lc_; // and give z's left child to y
        y->lc_->parent_ = y; // which had no left child
        y->color_ = z->color_;
    }
    if (yOriginalColor == RB_BLACK) RBDeleteFixUp(x); // if any red-back violations occured, correct them
}
template <typename T>
RBNode<T>* RBTree<T>::TreeMinimum(RBNode<T>* cur) const {
   
    while (cur->lc_ != tNil) {
   
        cur = cur->lc_;       
    }
    return cur;
}

即使RBDelete包含的代码行数几乎是TreeDelete的2倍，但这2个过程具有相同的结构。

下面为两个过程的区别：

1. RBDelete用tNil代替TreeDelete的nullptr。

2. 始终维持节点y为从树中删除的节点, 当第3行y指向z,且后续未发生变化，则z至多有1个节点，第12行的情形里z有2个孩子节点，y将指向z的后继，这与TreeDelete相同，y将移至树中z的位置。

3. 由于y的颜色可能改变，变量yOriginalColor存储了y的变化前颜色，第3行和第13行在给y赋值之后，立即设置该变量。当z有两个节点时，则$y\ne z$ 且第21行将y移动到z的位置，第23行将y的颜色着为z的颜色，当y为黑色时，移动y会违反红黑性质。

4. RBDelete保持对x的跟踪，使其移动到y的初始位置上，第7,10,15行令x指向y的唯一孩子或哨兵tNil。

5. 由于x移动到y的原始位置上，属性x.parent总是被设置指向树中y.parent的原始位置，甚至当x是哨兵tNil也是这样（对x.parent的赋值在RBTransplant第7行）。除非z是y的原始parent（此时由于z要被删除且y将占据z的位置，第20行将x.parent设置成y）。我曾认为第20行x.parent指向y是多此一举，由于x已经是y的孩子了，但RBDeleteFixUp依赖x.parent有明确指向，即使x是tNil，所以第20行代码是有必要的。

6. 最后，如果y原本是黑色的，应该有1条或多条红黑性质被破坏，所以在第26行调用RBDeleteFixUp来恢复红黑性质。如果y原本是红色， 有移动前后依然保持红黑性质，原因如下：

   1. 树中黑高没变。（第四版练习13.4-1，证明见附录【1】）
   2. 不存在两个相邻的红节点。因为y会占据原先z的位置，并着色为原先z的颜色，树中的y的新位置（原先z的位置）不存在相邻的红节点。另外，如果y不是z的孩子。y原先的右孩子节点x会占据y的位置，由于y为红色，所以x为黑色，这个替换操作不会导致出现两个红色相连的情况。
   3. y原本为红色，所以y不可能为根节点，根节点保持黑色。

   如果y原本为黑色，会产生三个问题，需要调用RBDeleteFixUp进行矫正：

   1. 如果y最初为根节点，被删除后，y的一个红色节点成为新的根节点，那么违反性质2。
   2. 如果x和x的新的父节点都是红色，那么违反了性质4。
   3. 如果在y所在的简单路径上移动y导致先前包含y的任何简单路径上黑节点个数减少1个，违反原来的性质5。这个问题可以通过把y的黑色传递给x解决，这样x多了一个额外的黑色，如果x原来为黑色，变成双重黑色。如果x原来为红色，变成了红黑双色，这样虽然维护了性质5，但违反了性质1。所以我们应该通过修改颜色来解决这个问题（性质1）。

   我追加条个人评论：

   ​ “这里的第三个问题的处理中有一个令人费解的地方，也就是x上添加一重额外的黑色，其实在代码中完全没有体现这一阴间操作，所以这里x所谓的双重颜色也并不真实存在。但是我们假设x节点就是双色的，即x有一重额外的黑色，这样的就能不违反相对难修复的性质5了，作为相应的代价，相对容易修复的性质1被破坏。这里我个人认为就像皇帝的新衣的故事里一样，我们先认为皇帝穿了衣服来避免被砍头。但最后的最后，真相还是得戳破的，就像RBDeleteFixUp代码里的第62行就是来戳破真相的。”

   现在看RBDeleteFixUp如何恢复搜索树的红黑性质的。

   其c++实现如下（建议一定要结合下面正文描述来看代码实现）：

   template <typename T>
   void RBTree<T>::RBDeleteFixUp(RBNode<T>* x) {
        
       while (x != root_ && x->color_ == RB_BLACK) {
        
           if (x == x->parent_->lc_) {
        
               RBNode<T>* w = x->parent_->rc_;
               if (w->color_ == RB_RED) {
        
                   // case 1
                   w->color_ = RB_BLACK;
                   x->parent_->color_ = RB_RED;
                   LeftRotate(x->parent_);
                   w = x->parent_->rc_;
               }
               if (w->lc_->color_ == RB_BLACK && w->rc_->color_ == RB_BLACK) {
        
                   // case 2
                   w->color_ = RB_RED;
                   x = x->parent_;
               } else {
        
                   if ( w->rc_->color_ == RB_BLACK) {
        
                       // case 3
                       w->lc_->color_ = RB_BLACK;
                       w->color_ = RB_RED;
                       RightRotate(w);
                       w = x->parent_->rc_;
                   }
                   // case 4
                   w->color_ = x->parent_->color_;
                   x->parent_->color_ = RB_BLACK;
                   w->rc_->color_ = RB_BLACK;
                   LeftRotate(x->parent_);
                   x = root_;
               }
           } else {
         // same as above cases, but with "right" and "left" exchanged
               RBNode<T>* w = x->parent_->lc_;
               if (w->color_ == RB_RED) {
        
                   // case 1
                   w->color_ = RB_BLACK;
                   x->parent_->color_ = RB_RED;
                   RightRotate(x->parent_);
                   w = x->parent_->lc_;
               }
               if (w->rc_->color_ == RB_BLACK && w->lc_->color_ == RB_BLACK) {
        
                   // case 2
                   w->color_ = RB_RED;
                   x = x->parent_;
               } else {
        
                   if ( w->lc_->color_ == RB_BLACK) {
        
                       // case 3
                       w->rc_->color_ = RB_BLACK;
                       w->color_ = RB_RED;
                       LeftRotate(w);
                       w = x->parent_->lc_;
                   }
                   // case 4
                   w->color_ = x->parent_->color_;
                   x->parent_->color_ = RB_BLACK;
                   w->lc_->color_ = RB_BLACK;
                   RightRotate(x->parent_);
                   x = root_;
               }
           }
       }
       x->color_ = RB_BLACK;
   }
   

   正文这里优先证明RBDeleteFixUp如何恢复性质1，至于恢复性质2和性质4的证明请看附录里Exercise13.4-2和13.4-3的解答【2】。

   RBDeleteFixUp中第4-61行，中while循环的作用就是在树中移动额外的黑色直到以下情况停止：

   1. x指向一个红黑双色节点，此时在第62行，将 x 着为黑色。
   2. x指向根节点，由于根节点已经为黑色，额外的黑色自动消失。
   3. 经过合适的旋转和着色操作，退出循环。

   和RBInsertFixUp类似，RBDeleteFixUp也处理了两种对称情形：第5~31行处理节点x为left child, 第33~60行处理x为right child情形。我们只关注第一种情况，即第4~31行。

   在while循环中，x总指向非根双重黑色的节点, 在第4行判断x是否是left child，用w指向x的兄弟，因为x是双重黑节点以及性质5的限制，所以w不可能指向tNil。

   重新想到RBDelete中第17行RBTransplant中或第20行进行了配置x.parent（即使x是哨兵也要配置x.parent)。这是因为RBDeleteFixUp要多次访问x.parent。

   下图13.7描绘了x是left child的四种情况，核心思路就是要维护性质5，从树或者子树的根到子树 $\alpha ,\beta ,\gamma ,ϵ,\epsilon ,\zeta$ 之间黑色（包含额外黑色）节点个数不变。

   

   图13.7(a)展现了情况1，从图中子树【】根节点到子树 $\alpha$ 或 β \beta