此文章为从二叉树到红黑树系列文章的第六节，主要介绍介绍红黑树，相信，有了之前BST，AVL和B树的铺垫，你会很快地理解红黑树。但红黑树的情况也十分复杂，因此，推荐分两天来看红黑树。一天看插入，一天看删除。

文章目录

• 一、所有文章链接~（点击右边波浪线可以返回目录）
• • 理解红黑树之前，需要了解的知识点：~
• 二、引入红黑树~
• 三、红黑树的性质~
• • 1.红黑树的外部节点~
  • 2.红黑树的性质~
  • • 红黑树性质解读~
  • 3.红黑树的适度平衡~
  • 4.红黑树与B树（2,4）树的关系（提升变换）~
  • • 提升变换的四种组合~
• 四、红黑树类~
• • （一）定义变量和接口~
  • • 1.利用已有的变量~
    • 2.需要的接口~
    • 3.重要辅助函数~
    • • （1）重写高度更新算法~
      • （2）双红，双黑缺陷~
    • 4.类内辅助静态函数~
    • 5.RedBlack.h~
  • （二）高度更新~
  • • 高度更新代码~
  • （三）红黑树的插入代码~
  • （四）双红修复~
  • • 1) u为黑色~
    • • a) LL型~
      • b) RR型~
      • c) LR型~
      • d) RL型~
    • 2) u为红色~
    • • a) LL型~
      • b) RR型~
      • c) LR型~
      • d) RL型~
    • 3) 求当前节点的叔叔代码~
    • 4) 双红修复代码递归版~
    • 5) 双红修复代码迭代版~
    • 6) 双红修复的复杂度~
  • （五）红黑树的删除~
  • • 1.再探removeAt语义~
    • • （1）removeAt的第一种和第二种情况~
      • （2）removeAt的第三种情况~
      • （3）结论~
      • （4）removeAt其他细节~
    • 2.红黑树的删除~
    • • （1）删除情况分析~
      • （2）删除代码~
      • （3）判断黑高度是否平衡代码~
  • （六）双黑缺陷~
  • • （1）s为黑，其至少有一个红孩子~
    • （2）s为黑，s的两个孩子为黑，p为红~
    • （3）s为黑，s的两个孩子为黑，p为黑~
    • （4）s为红，s的两个孩子必然为黑，p必然为黑~
    • （5）双黑修复递归版~
    • （6）双黑修复迭代版~
    • （7）双黑修复复杂度~
• 五、完整RedBlack.h~
• 六、红黑树测试~
• • 1.插入测试代码~
  • 2.插入测试图示~
  • 3.删除测试代码~
  • 4.删除测试图示~
• 七、结语~

一、所有文章链接~（点击右边波浪线可以返回目录）

  在阅读本文前，强烈建议你看下前面的文章的目录、前言以及基本介绍，否则你无法理解后面的内容。链接如下：

基本二叉树节点，通用函数 二叉树节点

基本二叉树类的定义和实现 二叉树基类

BST（二叉搜索树的实现） BST

AVL（二叉平衡搜索树的实现）AVL

B树的实现（如果你只想了解B树，可以跳过所有章节，直接看B树，B树的理解是红黑树的基础）B树

红黑树的实现 RedBlack

理解红黑树之前，需要了解的知识点：~

在本系列文章第三部分BST中的删除的基本原理

在本系列文章第四部分AVL中的connect34和rotateAt的基本原理

在本系列文章第五部分B树中的插入和删除，上溢和下溢的基本原理

如果你还不了解，那么看接下来的内容，你可能会有点吃力。

---

---

二、引入红黑树~

  AVL树尽管可以保证最坏情况下的单次操作速度，但需在节点中嵌入平衡因子等标识；更重要的是，删除操作之后的重平衡可能需做多达⌊log2n⌋次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。

  红黑树即是针对后一不足的改进。通过为节点指定颜色，并巧妙地动态调整，红黑树可保证：在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个节点。

---

---

三、红黑树的性质~

1.红黑树的外部节点~

  一棵树，所有叶节点都有空孩子指针，因此，为了方便理解，可以将这些空孩子指针全部视为外部节点。即假想地加入外部节点（实际并没有加入），使得树中任何节点都可以视为有左右孩子。

  下面是一颗红黑树

  若按1中给这颗树增加外部节点，就可以得到

2.红黑树的性质~

  提示：如果你看红黑树的算法，感到某些地方不好理解时，不妨来看看红黑树的性质，你就会明白算法为什么要这么设计。

由红、黑两色节点组成的二叉搜索树若满足以下条件，即为红黑树

(1) 树根始终为黑色
(2) 外部节点均为黑色（NULL LEAF）（假想，实际不存在）
(3) 其余节点若为红色，则其孩子节点必为黑色，反之，其父亲也必然为黑色。
(4) 从根节点到任一外部节点的沿途，黑节点的数目相等（黑深度相等）

红黑树性质解读~

由条件（1）（2）可知，红节点必然为内部节点。

由条件（3）可知红节点的孩子和父亲必然为黑色。即树中任何一条通路中绝对不可能有相邻的红节点。

由以上两个分析可知，在从根节点通往任一节点的沿途，黑节点都不少于红节点。

从根节点到任意节点所经的黑节点数目称为该节点的黑深度（由上往下）。（根节点黑深度为0）。由条件（4）可知，所有外部节点的黑深度必然相等。

从外部节点到内部任意节点，所经的黑节点的个数的最大值，称之为这个内部节点的黑高度（由下往上）。因此，外部节点的黑高度为0，根节点的黑高度等于外部节点的黑深度。

由以上可以得知，任意一个节点，其左右子树的黑高度都必然相等。

3.红黑树的适度平衡~

  由2中的红黑树的性质解读的第三条，可以得知

在从根节点通往任一节点的沿途，黑节点都不少于红节点。

  而一棵树，就是由红节点和黑节点组成，这样就代表，黑节点的数目，至少比全树所有节点的数目的一半大。而这一点，恰恰就是红黑树适度平衡的条件。

TB为黑高度（H），T为全树的高度（h）。

更严格的有log2(n + 1) <= h <=2∙log2(n + 1)（证明略）

  尽管红黑树不能如完全树那样可做到理想平衡，也不如AVL树那样可做到较严格的适度平衡，但其高度仍控制在最小高度的两倍以内，从渐进的角度看仍是O(logn)，依然保证了适度平衡—这正是红黑树可高效率支持各种操作的基础。

4.红黑树与B树（2,4）树的关系（提升变换）~

  往下看之前，建议你理解一下B树的上溢和下溢。不懂的就看看本系列文章的第五部分，我对B树进行了详解。

  在后面就可以得知，经适当转换之后，红黑树和（2,4）树相互等价！
  具体地，自顶而下逐层考查红黑树各节点。每遇到一个红节点，都将对应的子树整体提升一层，从而与其父节点（必黑）水平对齐，二者之间的联边则相应地调整为横向。
               
  由红黑树的性质（3）可得，对于有红孩子的黑节点而言，提升过程中，所涉及的节点至多不超过3个（可能为2个，当只有一个红孩子时），因为其最多只有两个红孩子，而对应的红孩子必然只有黑孙子，没有红孙子。

  因此由变换之后的结果可以观察到，可以把变换之后的3个节点（或2个节点）看做一个整体，其恰好可以构成4阶B树（3个关键码）中的一个节点。因此，变换之后，每一颗红黑树都对应一颗（2,4）树。

提升变换的四种组合~

1、 通往黑节点的边对红黑树的黑高度有贡献，以实线表示，保留下来。
2、 通往红节点的边对红黑树的黑高度没有贡献，以虚线表示，不予保留。

下图中，上方是红黑树，下方是对应的B树。

  从上图可以看出，对应的（2,4）B树。每个节点有且仅有一个黑色的关键码，同时红色的关键码不超过两个，若某个节点果真包含两个红关键码，则黑关键码的位置必然居中。

---

---

四、红黑树类~

（一）定义变量和接口~

1.利用已有的变量~

在第一部分定义二叉树节点的时候，我们定义了一个

RBColor _color;//红黑树专用

这个枚举类，主要是用于表示红黑树的颜色信息。具体为

namespace {enum class RBColor { RED, BLACK }; }

并且同样，我们会用到在BST定义的_hot节点

BinNodePtr _hot;//"命中节点"的"父亲"

2.需要的接口~

  由于在BST中，我们已经定义了查找search算法，因此，不需要给RedBlack重新写查找算法，只需要对插入和删除算法进行重写既可（并且在后面可以发现，其插入和删除的本质，跟BST和AVL一模一样！）。并且在BinTree中，我们也定义了遍历算法，因此，也沿用即可。

在树中插入一个节点insert 在树中删除一个节点remove

3.重要辅助函数~

（1）重写高度更新算法~

  由于红黑树的高度的表示方式为黑高度，所以其高度更新的算法也需要进行重写

更新高度updateHeight

（2）双红，双黑缺陷~

  这两个辅助函数，正是红黑树得以保持平衡的最主要原因。在接下来介绍插入时，会解释双红缺陷，在介绍删除时，会解释双黑缺陷。

solveDoubleRed解决双红缺陷 solveDoubleBlack解决双黑缺陷

4.类内辅助静态函数~

  为了加快算法执行的效率，和方便理解，在红黑树类内定义了4个静态内联函数。前两个很好理解，后面两个在介绍插入和删除算法时会进行解释。

IsBlack//判黑//当然x为空，也为黑色 IsRed//非黑即红IsBlackHeightBalanced//判断是否需要更新黑高度 uncle//获取当前节点的叔叔

5.RedBlack.h~

template<typename T=int> class RedBlack :public BST<T> { protected:using BinNodePtr = BinNode<T>*;protected:void solveDoubleRed(BinNode<T>* x);//双红修正void solveDoubleBlack(BinNode<T>* replacer);//双黑修正constexpr int updateHeight(BinNode<T>* x)const override;//更新高度public:BinNode<T>* insert(const T& data)override;//插入重写bool remove(const T& data)override;//删除重写/*查找沿用BST的查找*//*遍历沿用BinTree的遍历*/protected:static constexpr bool IsBlack(const BinNodePtr& x) {//判黑//当然x为空，也为黑色return ((!x) || (RBColor::BLACK == x->_color));}static constexpr bool IsRed(const BinNodePtr& x) {//非黑即红return !IsBlack(x);}static constexpr bool IsBlackHeightBalanced(const BinNodePtr& x) {//判断是否需要更新黑高度bool is_L_C_Equal = (stature(x->_lchild) == stature(x->_rchild));int rbHeight = (IsRed(x) ? stature(x->_lchild) : stature(x->_lchild) + 1);//对于rbHeight的计算而言，取左孩子还是右孩子，均一样bool is_Height_Equal = (x->_height == rbHeight);return is_L_C_Equal && is_Height_Equal;//只要有一个为假，即为假//所以只要左孩子和右孩子高度相等，或者x没有高度变化，就黑高度平衡 }static inline BinNodePtr uncle(const BinNodePtr& x) {/*获取x的叔叔*/return IsLChild(x->_parent) ? x->_parent->_parent->_rchild : x->_parent->_parent->_lchild;}};//class RedBlack

---

---

（二）高度更新~

  下面是我们在本系列文章第一部分定义的获取当前节点高度的全局静态函数。并且我们规定当没有节点时，高度为-1，当有一个节点时，高度为0（见第一部分关于树的语义规定中树的高度的定义）。此规定依然适用于红黑树，也就是说，哪怕红黑树此时只有一个根节点（必然为黑），其高度为0而不是1。
  此规定，对于后序红黑树的平衡不造成任何影响，但若读者要获取红黑树的高度的话，就需要明白此时的黑高度，比实际的黑高度少1。

template<typename BinNodePtr> static constexpr int stature(const BinNodePtr& x) {//获取高度return x ? x->_height : -1;//空指针高度为-1 }

高度更新代码~

template<typename T> constexpr int RedBlack<T>::updateHeight(BinNode<T>* x) const//由于stature视空节点高度为-1，所以height会比黑高度少一 {x->_height = std::max(stature(x->_lchild), stature(x->_rchild));//孩子一般黑高度相等，除非出现双黑return IsBlack(x) ? x->_height++ : x->_height;//若当前节点为黑，则计入黑高度 }

由于重写了更新高度函数，所以此时x的高度，为黑高度。
要更新红黑树的高度（即黑高度），只有当：

（1）左右孩子黑高度不相等。 （2）x为黑节点时，其高度要加1。 （3）x为红节点时，其高度不需要额外更新。

---

---

（三）红黑树的插入代码~

  红黑树的插入算法，与BST，AVL的基本插入方式一模一样，唯一不同的是后续要进行双红修复。

  先用BST的search确定不存在这个节点，并且更新_hot的位置,并以_hot为父亲，创建一个新节点。并将其黑高度更新为-1，以及染色成红色（我们默认新加入的节点均为红色节点，除非新加的是根节点）。

  由BinNode节点的构造函数，默认新节点为红色。

template<typename T> BinNode<T>* RedBlack<T>::insert(const T& data) {BinNode<T>*& x = this->search(data);//沿用BST的查找//并更新_hot//用引用接收if (x)//如果节点存在，则返回return x;x = new BinNode<T>(data, this->_hot, nullptr, nullptr, -1);//设定黑高度-1，并默认节点为红色this->_size++;solveDoubleRed(x);//双红修正//x此时必为红return x; }

---

---

（四）双红修复~

  因新节点的引入，而导致父子节点同为红色的此类情况，称作“双红”（double red）。每引入一个关键码，双红修正函数都可能迭代地调用多次。在此过程中，当前节点x的兄弟及两个孩子（初始时都是外部节点），必然均为黑色。

因为x的父亲为红色，所以其只可能有黑孩子，所以x若有兄弟，则必为黑色。 由于x为新节点，其外部节点为空，即默认均为黑孩子。

  将x的父亲与祖父分别记作p和g。既然此前的红黑树合法，故作为红节点p的父亲，g必然存在且为黑色。

此时的g，必然存在，否则作为树根的节点p不可能为红色；并且g作为红色节点p的父亲，其必然为黑色的

在下面的过程中，仅仅有x p g这三个节点还不够，因此，还需要一个额外的节点，即p的兄弟（x的叔叔）u。

  以下，视节点u的颜色不同（若u不存在，其颜色也视为黑，这符合之前外部节点的颜色定义），分两类情况分别处置。

1) u为黑色~

  u为黑色时，具体来说，对应四种结构.

  此时x的兄弟和两个孩子的黑高度必然都与u的黑高度相等。

a) LL型~

在原来的树中，插入了新节点x。构成下图所示的结构。

此时，可以利用B树来理解，不妨先将红黑树，经过提升变换，提升为对应的（2,4）B树。

从B树的结构可以看出，其不满足先前提升变换的四种情况中的任何一种。
因此，要想其满足提升变换的四种情况，最简单的做法，就是将p与g互换颜色，让对应的（2,4）B树变成下图所示形式

再将对应的（2,4）B树还原成红黑树，即为

即原来的 x 变成 a，原来的 p 变成 b ，原来的 g 变成 c 。
但也注意到，相应的孩子节点的位置也发生了新的变化。

  因此，如何做到这样的变化呢？此时不妨想想在本系列文章第三部分定义的AVL中的connect34算法，其对应的形状也是这样的形状

  没错，只要我们将对应的x p g按照connect34的形式进行重构，就可以达到目的。

b) RR型~

  同LL型一样处理，不多赘述。

c) LR型~

  在原来的树中，插入了新节点x。构成下图所示的结构。此时仍然满足x的兄弟和两个孩子的黑高度必然都与u的黑高度相等这个条件。

此时，同样可以利用B树来理解，不妨先将红黑树，经过提升变换，提升为对应的（2,4）B树。

  情况总是惊人的相似，可以发现，现在的形状的调整方式，不正是同LL型的调整方式一模一样么？只是x p g的相对位置有所变化。因此，也是需要进行connect34重构。

d) RL型~

  同LR型一样处理，不多赘述。

2) u为红色~

  u为红色时，具体来说，对应四种结构

  此时，u的左、右孩子均为黑色（可能为空），其黑高度必与x的兄弟以及两个孩子相等。

a) LL型~

在原来的树中，插入了新节点x。构成下图所示的结构。

此时，同样可以利用B树来理解，不妨先将红黑树，经过提升变换，提升为对应的（2,4）B树。

在介绍LR型的时候，会展示怎么处理这种情况。

b) RR型~

  同LL型一样处理，不多赘述。

c) LR型~

  在原来的树中，插入了新节点x。构成下图所示的结构。此时仍然满足x的兄弟和两个孩子的黑高度必然都与u的黑高度相等这个条件。

此时，同样可以利用B树来理解，不妨先将红黑树，经过提升变换，提升为对应的（2,4）B树。

  可以看到，提升变换之后，其这个大节点的关键码数目，均必然为4个，超出了4阶B树的个数限制（4阶B树的一个大节点的关键码数最多只能有3个）。所以可以仿照B树的情况，进行一次上溢。同时进行染色以满足原来B树提升变换后的四种形态。（问号节点中必然有一个为黑，按照红黑树的提升变换，只有当g染成红时才可以进行提升变换）

从红黑树的角度来看，对比没有变换之前


  从宏观上来看，对于红黑树而言，只需要将p u的颜色由红色变成黑色，并且若g不为根节点的话，就将g染色成红色。当然，若g此时就是根节点，其强制变成黑色。

  同样，由于g变成了红色，所以还需要继续判断g的父亲是否是红色，因此要继续进行双红修复。最坏的情况，可能要持续到根节点。（由x到g，上升了两层）。累计最多迭代logn次。

d) RL型~

  同LR型一样处理，不多赘述。

3) 求当前节点的叔叔代码~

static inline BinNodePtr uncle(const BinNodePtr& x) {/*获取x的叔叔*/return IsLChild(x->_parent) ? x->_parent->_parent->_rchild : x->_parent->_parent->_lchild; }

4) 双红修复代码递归版~

  注意要是已经递归到树根，则树根强制转黑

template<typename T>void RedBlack<T>::solveDoubleRed(BinNode<T>* x){if (IsRoot(x)) {//若已递归到树根，则树根转黑，整树高度也随之递增this->_root->_color = RBColor::BLACK;this->_root->_height++;return;}//否则x的父亲必然存在BinNode<T>* p = x->_parent;//x的父亲if (IsBlack(p))//如果x的父亲为黑，则终止调整return;//否则x的父亲必然为红，则BinNode<T>* g = p->_parent;//x的祖父必然存在，并且，其颜色必然为黑色BinNode<T>* u = uncle(x);//x的叔叔，可能为空节点if (IsBlack(u)) {//当u为黑色时（u为空时，也为黑色）if (IsLChild(x) == IsLChild(p))p->_color = RBColor::BLACK;elsex->_color = RBColor::BLACK;g->_color = RBColor::RED;/// 以上虽保证总共两次染色，但因增加了判断而得不偿失/// 在旋转后将根置黑、孩子置红，虽需三次染色但效率更高BinNode<T>*& newNode = this->FromParentTo(g);//先记录祖父的父亲的孩子指针newNode = this->rotateAt(x);/*对x进行调整，调整之后的返回值必然为调整之后的局部子树的树根位置，此时，只需要将此树根作为原来祖父的父亲的孩子既可，当然，高度也随之更新*/return;//只要旋转了一次，就调整完整，退出循环}else {//若u为红色p->_color = RBColor::BLACK;//父亲此时必然为红色，将其转黑p->_height++;u->_color = RBColor::BLACK;//叔叔此时必然为红色，将其转黑u->_height++;if (!IsRoot(g))//如果祖父不为根节点，就转红g->_color = RBColor::RED;solveDoubleRed(g);//递归用}}

5) 双红修复代码迭代版~

  为了方便理解，我将递归的部分变成了注释，并未进行删除，方便读者比对，迭代版中，不仅将尾递归转换成了迭代，也将染色的效率进行了优化。

template<typename T> void RedBlack<T>::solveDoubleRed(BinNode<T>* x) {while (true) {if (IsRoot(x)) {//若已迭代到树根，则树根转黑，整树高度也随之递增this->_root->_color = RBColor::BLACK;this->_root->_height++;return;}//否则x的父亲必然存在BinNode<T>* p = x->_parent;//x的父亲if (IsBlack(p))//如果x的父亲为黑，则终止调整return;//否则x的父亲必然为红，则BinNode<T>* g = p->_parent;//x的祖父必然存在，并且，其颜色必然为黑色BinNode<T>* u = uncle(x);//x的叔叔，可能为空节点if (IsBlack(u)) {//当u为黑色时（u为空时，也为黑色）//if (IsLChild(x) == IsLChild(p))// p->_color = RBColor::BLACK;//else// x->_color = RBColor::BLACK;//g->_color = RBColor::RED;/// 以上虽保证总共两次染色，但因增加了判断而得不偿失/// 在旋转后将根置黑、孩子置红，虽需三次染色但效率更高BinNode<T>*& newNode = this->FromParentTo(g);//先记录祖父的父亲的孩子指针newNode = this->rotateAt(x);/*对x进行调整，调整之后的返回值必然为调整之后的局部子树的树根位置，此时，只需要将此树根作为原来祖父的父亲的孩子既可，当然，高度也随之更新*///重染色/*能省去之前的判断*/newNode->_color = RBColor::BLACK;newNode->_lchild->_color = RBColor::RED;newNode->_rchild->_color = RBColor::RED;return;//只要旋转了一次，就调整完整，退出循环}else {//若u为红色p->_color = RBColor::BLACK;//父亲此时必然为红色，将其转黑p->_height++;u->_color = RBColor::BLACK;//叔叔此时必然为红色，将其转黑u->_height++;if (!IsRoot(g))//如果祖父不为根节点，就转红g->_color = RBColor::RED;//solveDoubleRed(g);//递归用x = g;//将x变成其祖父，进入迭代循环。}} }

6) 双红修复的复杂度~

  邓老师已经用一个流程图和一个表格，帮助我们详细地分析了双红修复算法的复杂度。其中zag，zig是左右旋（也就是我们的connect34重构）

RR代表双红

  可见，对于u为黑的情况，只需做一轮修正；u为红的情况虽有可能需要反复修正，但由于修正位置的高度会严格单调上升，故总共也不过O(logn)轮。另外从该表也可看出，每一轮修正只涉及到常数次的节点旋转或染色操作。

  因此，节点插入之后的双红修正，累计耗时不会超过O(logn)。即便计入此前的关键码查找以及节点接入等操作，红黑树的每次节点插入操作，都可在O(logn)时间内完成。

（五）红黑树的删除~

  红黑树的删除算法，本质同BST，AVL的删除。在删除节点方面。两者没什么区别，唯一的区别即高度的更新方式不同。因此，可以调用在BST中设定的给AVL的删除接口removeAt全局函数。

现在我们继续来看看removeAt函数的作用

定义在BST中的removeAt函数

template<typename T>//适用于AVL Splay,RedBlack等，必须这么设计，才能做到完美删除，且保持BST的性质 static BinNode<T>* removeAt(BinNode<T>*& x, BinNode<T>*& hot) {//这里x必须用引用，才不会使指针乱指using BinNodePtr = BinNode<T>*; //记录x的地址里面保存的值，若删除temp里面的值，即删除x里面的值，但x的本身地址不会影响temp，反之亦然。BinNodePtr temp = x;//替代被删除节点的接替者，一般为被删除节点的左孩子或者右孩子，而不是x的左孩子或者右孩子BinNodePtr replacer = nullptr;if (!HasLChild(x)) {//如果x没有左孩子，或者x左右孩子均无，则将x的右孩子作为x，并将接替者设为x的右孩子x = x->_rchild;replacer = x;}else if (!HasRChild(x)) {//如果x没有右孩子，则将x的左孩子作为x，并将接替者设为x的左孩子x = x->_lchild;replacer = x;}else {temp = temp->succ();//取得中序遍历的后继//这个后继必将没有左孩子std::swap(x->_data, temp->_data);//交换对应的值if (temp->_parent == x) {//如果后继的父亲是原来的x，后继必然为x的右孩子replacer = temp->_rchild; //就将后继的右孩子作为父亲的右孩子temp->_parent->_rchild = replacer;}else {//如果后继的父亲不是原来的x，后继必然为某一节点的左孩子replacer = temp->_rchild;temp->_parent->_lchild=replacer;//就将后继的右孩子作为这个节点左孩子}}//hot即被删除节点的父亲。而temp正是要删除的节点。hot = temp->_parent;if (replacer)//若replacer存在，则必须将其父指针指向hot。不然如同x->_rchild的父亲指向的还是原来的replacer->_parent = hot;//释放原来x所指的堆区的数据，或者x的后继的堆区的数据release(temp->_data);release(temp);return replacer; }

1.再探removeAt语义~

  从removeAt的语义（3种删除的情况）来看，删除的节点可能是x，可能是x的后继。

（1）removeAt的第一种和第二种情况~

  从removeAt的第一种和第二种情况来看，删除的节点必然为x。即表明此时的x要么没有孩子，要么只有一个孩子。即此时x必然有一个空孩子（也一定是黑孩子）。

下面图的情况，全部是用来删除节点x    删除节点1，实际删除的也是1（removeAt的第一种情况）

删除节点1，实际删除的也是1（removeAt的第一种情况）

删除节点1，实际删除的也是1（removeAt的第二种情况）

  可以看到，此时x必然有一个空孩子（也一定是黑孩子）。

（2）removeAt的第三种情况~

  从removeAt的第三种情况来看，删除的节点为x的后继，由后继的定义可知，这个后继必然没有左孩子（这种后继的情况，必然属于在本系列文章第一节谈到的求后继的第一种情况，并且我用红字标明了这种后继一定没有左孩子），不然不可能删这个后继。

删除节点10，实际删除的是15（removeAt的第三种情况）

  可以看到，15必然没有左孩子，其左孩子为空节点（黑节点）。

因此，x的后继必然有一个空孩子（也是黑孩子）。

（3）结论~

综合（1）（2）可以得到一个非常重要的结论：

无论被删除的是x还是x的后继，被删除节点，都必然有一个空孩子（也是黑孩子）。

（4）removeAt其他细节~

  1. 在removeAt函数中，交换x与后继的值时，也只是交换了它们的data值，并非交换了它们的所有东西，因此，x的原来的颜色，和其后继的颜色均没变。

std::swap(x->_data, temp->_data);//交换对应的值

  2.在删除完成后_hot节点也指向了被删除节点的父亲节点。

//hot即被删除节点的父亲。而temp正是要删除的节点。 hot = temp->_parent;

  3.removeAt的返回值是replacer，即被删除节点的接替者。

BinNodePtr replacer//替代被删除节点的接替者，一般为被删除节点的左孩子或者右孩子，可能为空

2.红黑树的删除~

（1）删除情况分析~

  对于删除时节点（可能是x被删，也可能是其后继被删）的颜色进行分类讨论的话，无外乎就五种情况。

（1）被删除后，原树没有任何节点，删除即可完成。

（2）被删除的是根节点，只需要将其接替者replacer染成黑色，并更新高度既可，删除完成。

（3）实际被删除节点x为红色，其必然只有黑孩子和黑父亲，并且w必然为空（根据removeAt的结论），此时只需将r接替x的位置既可。（当然r也可能为空）

x代表被删除节点，w代表必然为空的那个节点，r代表replacer也就是被删除节点的接替者。p为x的父亲

  此时，毫无例外，删除x对原树的黑高度肯定没有影响，因此直接删除既可。删除完成后，即可结束。

（4）实际被删除节点为黑色，w同样也为空（根据removeAt的结论）。若r为红色，此时，只需要在r接替x的位置之后，将r转成黑色，那么原树的黑高度也必然恢复，删除完成。

（5）实际被删除节点为黑色，w同样也为空（根据removeAt的结论）。若r为黑，即出现双黑情况，则需要做进一步的调整变换。（当然，这种情况，也必然包含了r为空孩子的情况）

（2）删除代码~

template<typename T> bool RedBlack<T>::remove(const T& data) {BinNode<T>*& x = this->search(data);//找有没有这个节点，如果没有，则返回false,记住用引用if (!x)return false;BinNode<T>* replacer = removeAt(x, this->_hot);//调用在BST定义的全局静态函数removeAt,返回被删除节点的接替者，同时更新_hot--this->_size;//更新规模//1.如果这个被删除节点是树中唯一节点，则直接返回if (this->_size==0) {this->_root = nullptr;//将根节点置空return true;}//2.如果被删除节点为根节点，则_hot必然为空//但如果进行到此，说明此时_root必然不为空，不然上一就会退出if (this->_hot == nullptr) {this->_root->_color = RBColor::BLACK;//就将此时的根节点直接染成黑色updateHeight(this->_root);//并更新根节点的高度return true;}//如果进行到此，说明被删除节点必然存在，并且不为根节点。_hot也必然存在/*3.如果_hot的黑高度不变则返回*//*此时也必然包括了被删除节点为红色节点的情况，若为红色，则删除对高度没有影响*//*当然，也包括了双黑的可能情况*/if (IsBlackHeightBalanced(this->_hot))return true;/*4.如果_hot的黑高度变了，说明被删除节点必然为黑色*/if (IsRed(replacer)) {//就看x的接替者是不是红色，如果是红色，将其染成黑色，就必然可以使树的高度恢复。replacer->_color = RBColor::BLACK;replacer->_height++;return true;}/*5.如果进行到此，就必然说明被删除节点和replacer均为黑色节点（replacer可能为空），此时，就需要进行双黑缺陷判断*//*要进行到这里的条件即为被删除节点的父亲的黑高度变了，并且被删除节点的接替者也为黑色时。*/solveDoubleBlack(replacer);return true; }

（3）判断黑高度是否平衡代码~

在红黑树的删除过程中，我们需要判断黑高度是否平衡。

static constexpr bool IsBlackHeightBalanced(const BinNodePtr& x) {//判断是否需要更新黑高度bool is_L_C_Equal = (stature(x->_lchild) == stature(x->_rchild));int rbHeight = (IsRed(x) ? stature(x->_lchild) : stature(x->_lchild) + 1);//对于rbHeight的计算而言，取左孩子还是右孩子，均一样bool is_Height_Equal = (x->_height == rbHeight);return is_L_C_Equal && is_Height_Equal;//只要有一个为假，即为假//所以只要左孩子和右孩子高度相等，或者x没有高度变化，就黑高度平衡 }

（六）双黑缺陷~

  若被删除节点和其接替者（可能为空）均为黑。则显然，为了保持红黑树的平衡性，原来被删除节点必然有一个非空兄弟（其孩子可能均为空），不然黑高度就无法维持。

  不妨将被删除节点x的兄弟记作s。被删除节点的父亲记作p。无论哪一个，颜色都不确定。

  因此，分s和p的颜色情况，分四种情况来讨论。

（1）s为黑，其至少有一个红孩子~

  先以s为p的左孩子，x为p的右孩子来处理（对称情况处理方式完全相同）
  左为红黑树，右为对应的B树

  此时删除了节点x，类似于B树的处理方式，由于其左兄弟有一个多余的关键码，所以要从其左兄弟借一个关键码。调整后为（当然，调整之后，要满足提升变换的四种情况，因此需要重染色）

左侧是B树，右侧是红黑树

  并且图（b）的结构也是令人十分熟悉，没错，也就是connect34重构。
  因此，从红黑树的角度来看，此过程等效于对节点t，s，p进行3+4重构。

  位置调整好后，再进行重染色，即把t，p染成黑色，s继续沿用之前p的颜色。并且在此过程中，r的颜色没有发生变化。

  显然，调整完之后，红黑树的高度得以复原。因此调整完毕。

（2）s为黑，s的两个孩子为黑，p为红~

  先以s为p的左孩子，x为p的右孩子来处理（对称情况处理方式完全相同）
  左为红黑树，右为对应的B树

（p的位置不可能是中间，只可能是左边或者右边）   

  此时的B树，被删除的x无法从s中借关键码，所以只有父亲下溢。为保持红黑树的性质不变，因此下溢后，只需将s和p的颜色互换，就能保持性质。

（p的左右节点中有且仅有一个黑色关键码，因此p下溢，不会造成对应B树结构的破坏）   

  因此，从红黑树的角度来看，只需将s与p的颜色进行互换，就能使红黑树的高度得到复原。

（3）s为黑，s的两个孩子为黑，p为黑~

  先以s为p的左孩子，x为p的右孩子来处理（对称情况处理方式完全相同）
  左为红黑树，右为对应的B树

  由于删除了x，s也没有足够的关键码，因此，只能p下溢。并且由于p所在层次，必然只有p一个关键码，因此，p的下溢，必将导致上层下溢。

  下溢之后，将s置为红色，对应的红黑树为

  因此，从红黑树的角度来看，即把s由黑转红。

  由于p是下溢过来的，所以需要做进一步的检查，此时等效于原树中p的黑父亲刚删除，因此可以看做又是一次双黑缺陷。所以需要再次做迭代循环。

  这也是双黑修正过程中，需要再次迭代的唯一可能。（可能进入情况1 2 3 4中任何一种）。

（4）s为红，s的两个孩子必然为黑，p必然为黑~

  先以s为p的左孩子，x为p的右孩子来处理（对称情况处理方式完全相同）
  左为红黑树，右为对应的B树

  从B树的角度来看，此时可以将p下溢，并将s’转红，s转黑，但这样会导致以s’为根的子树的高度变化，并且由于x被删除，以x为根的子树的高度必然也下降。所以，如果仅仅这么调整，会造成两颗子树的高度减少，使得情况变得更加复杂。

  而先辈们已经有了很好的解决方式。

  即先将s与p互换颜色，得到左图所示的B树，将其转换为红黑树为右图所示。

  从红黑树的角度来看，这一转换对应于以节点p为轴做一次旋转，并交换p与s的颜色。

  可以发现，经过上述处理后，双黑缺陷依然存在，而且缺陷位置的高度也未上升。但此次变换并非没有意义，仔细观察图b可以发现，被删除节点x有了一个新兄弟s’,并且s’必然为黑。

  并且，调整之后，可以发现a与b所示的红黑树，完全等价。

  再仔细观察，不难发现，此时x p s’对应的情况，不正是之前双黑修复过程中出现的情况（1）与（2）么

  所以，只需要将调整之后的红黑树，再进行一次双黑修复，就必然可以修复高度。

（5）双黑修复递归版~

template<typename T> void RedBlack<T>::solveDoubleBlack(BinNode<T>* replacer) {BinNode<T>* p = replacer ? replacer->_parent : this->_hot;if (p == nullptr)return;//如果replacer的父亲为空，则返回/*由下面的情况来分析，无论哪种情况，递归的这个节点，必然为黑色*/所以不需要考虑将根节点强转黑色BinNode<T>* sibling = (replacer == p->_lchild) ? p->_rchild : p->_lchild;//原来x的兄弟，也就是replacer此时的兄弟if (IsBlack(sibling)) {BinNode<T>* s_Red_child = nullptr;//sibling的红孩子（若左右孩子皆为红，则左者优先；皆黑时为nullptr）if (IsRed(sibling->_rchild))//需要判断sibling是不是空指针s_Red_child = sibling->_rchild;//右孩子if (IsRed(sibling->_lchild))s_Red_child = sibling->_lchild;//左孩子 /*1.第一种情况，黑s有红孩子*/if (s_Red_child != nullptr) {//如果sibling有红孩子RBColor oldColor = p->_color;//备份父亲的颜色/*接下来对s的红孩子，s以及p进行3+4重构*//*根据3+4重构后的定义，其返回的节点为根节点指针，这个根节点的名字不妨设为newNode*/BinNode<T>*& newNode = this->FromParentTo(p);//首先记录父亲的 父亲的孩子的指针newNode = this->rotateAt(s_Red_child);//3+4重构//对3+4重构后的节点进行重染色if (HasLChild(newNode)) {newNode->_lchild->_color = RBColor::BLACK;updateHeight(newNode->_lchild);}if (HasRChild(newNode)) {newNode->_rchild->_color = RBColor::BLACK;updateHeight(newNode->_rchild);}newNode->_color = oldColor;//新子树根节点继承原根节点的颜色updateHeight(newNode);//更新高度/*至此，就调整完毕，红黑树恢复平衡*/}/*黑s没有红孩子，及其孩子均为黑色（可能为空）,对其父亲是否为红色进行判断*/else {sibling->_color = RBColor::RED;//无论父亲是否为红色，都需要把s设为红色sibling->_height--; /*2.黑s只有黑孩子（可能为空，并且其父亲为红色*/if (IsRed(p)) {p->_color = RBColor::BLACK;//直接将父亲设定为黑色，父亲的高度必然没有发生变化。//因为p原来为红，现在由于两个孩子高度都减了一，所以将其变成黑色后，其高度就恢复了原来的高度/*至此，就调整完毕，红黑树恢复平衡*/} /*3.黑s只有黑孩子（可能为空，并且其父亲为黑色*/else {p->_height--;//相当于p的父亲被删，然后对p是父亲的replacer，因此，对p进行递归既可。solveDoubleBlack(p);//用递归时用/*之后可能进入1 2 3 4四种情况中的任何一种，最坏可能到根*/}}} /*4.s为红，此时其必然只有黑孩子（黑孩子可能均为空），当然s的父亲p此时也必然为黑*/else {sibling->_color = RBColor::BLACK;//将s和p的颜色互换p->_color = RBColor::RED;//取与s同侧的孩子BinNode<T>* s_child = IsLChild(sibling) ? sibling->_lchild : sibling->_rchild;this->_hot = p;//首先将p的父亲记录起来BinNode<T>*& newNode = this->FromParentTo(p);//首先记录p的 父亲的孩子的指针newNode = this->rotateAt(s_child);//将s_child,s与p 进行3+4重构/*调整之后，树的局部结构就发生了变化*/solveDoubleBlack(replacer);//用递归时用//由第四种情况的分析，可知，只需要修复重构后的replacer就可以//并且之后只有可能进入第一种和第二种情况，必然不可能进入第三种情况} }

（6）双黑修复迭代版~

  为了方便理解，我将递归的部分变成了注释，并未进行删除，方便读者比对。

template<typename T> void RedBlack<T>::solveDoubleBlack(BinNode<T>* replacer) {while (true) {BinNode<T>* p = replacer ? replacer->_parent : this->_hot;if (p == nullptr)return;//如果replacer的父亲为空，则返回/*由下面的情况来分析，无论哪种情况，递归的这个节点，必然为黑色*/所以不需要考虑将根节点强转黑色BinNode<T>* sibling = (replacer == p->_lchild) ? p->_rchild : p->_lchild;//原来x的兄弟，也就是replacer此时的兄弟if (IsBlack(sibling)) {BinNode<T>* s_Red_child = nullptr;//sibling的红孩子（若左右孩子皆为红，则左者优先；皆黑时为nullptr）if (IsRed(sibling->_rchild))//需要判断sibling是不是空指针s_Red_child = sibling->_rchild;//右孩子if (IsRed(sibling->_lchild))s_Red_child = sibling->_lchild;//左孩子 /*1.第一种情况，黑s有红孩子*/if (s_Red_child != nullptr) {//如果sibling有红孩子RBColor oldColor = p->_color;//备份父亲的颜色/*接下来对s的红孩子，s以及p进行3+4重构*//*根据3+4重构后的定义，其返回的节点为根节点指针，这个根节点的名字不妨设为newNode*/BinNode<T>*& newNode = this->FromParentTo(p);//首先记录父亲的 父亲的孩子的指针newNode = this->rotateAt(s_Red_child);//3+4重构//对3+4重构后的节点进行重染色if (HasLChild(newNode)) {newNode->_lchild->_color = RBColor::BLACK;updateHeight(newNode->_lchild);}if (HasRChild(newNode)) {newNode->_rchild->_color = RBColor::BLACK;updateHeight(newNode->_rchild);}newNode->_color = oldColor;//新子树根节点继承原根节点的颜色updateHeight(newNode);//更新高度/*至此，就调整完毕，红黑树恢复平衡*/return;//用递归的时候注释掉}/*黑s没有红孩子，及其孩子均为黑色（可能为空）,对其父亲是否为红色进行判断*/else {sibling->_color = RBColor::RED;//无论父亲是否为红色，都需要把s设为红色sibling->_height--; /*2.黑s只有黑孩子（可能为空，并且其父亲为红色*/if (IsRed(p)) {p->_color = RBColor::BLACK;//直接将父亲设定为黑色，父亲的高度必然没有发生变化。//因为p原来为红，现在由于两个孩子高度都减了一，所以将其变成黑色后，其高度就恢复了原来的高度/*至此，就调整完毕，红黑树恢复平衡*/return;//用递归的时候注释掉} /*3.黑s只有黑孩子（可能为空，并且其父亲为黑色*/else {p->_height--;//相当于p的父亲被删，然后对p是父亲的replacer，因此，对p进行递归既可。//solveDoubleBlack(p);//用递归时用replacer = p;//将replacer变成p进入迭代循环//用递归的时候注释掉/*之后可能进入1 2 3 4四种情况中的任何一种，最坏可能到根*/}}} /*4.s为红，此时其必然只有黑孩子（黑孩子可能均为空），当然s的父亲p此时也必然为黑*/else {sibling->_color = RBColor::BLACK;//将s和p的颜色互换p->_color = RBColor::RED;//取与s同侧的孩子BinNode<T>* s_child = IsLChild(sibling) ? sibling->_lchild : sibling->_rchild;this->_hot = p;//首先将p的父亲记录起来BinNode<T>*& newNode = this->FromParentTo(p);//首先记录p的 父亲的孩子的指针newNode = this->rotateAt(s_child);//将s_child,s与p 进行3+4重构/*调整之后，树的局部结构就发生了变化*///solveDoubleBlack(replacer);//用递归时用//由第四种情况的分析，可知，只需要修复重构后的replacer就可以//并且之后只有可能进入第一种和第二种情况，必然不可能进入第三种情况}} }

（7）双黑修复复杂度~

  邓老师已经用一个流程图和一个表格，帮助我们详细地分析了双黑修复算法的复杂度。其中zag，zig是左右旋（也就是我们的connect34重构）

  其中涉及的重构、染色等局部操作，均可在常数时间内完成，故为了估计整个双黑修正过程的时间复杂度，也只需统计这些操作各自的累计执行次数。

  情况BB-2-B虽可能需要反复修正，但由于待修正位置的高度严格单调上升，累计也不致过O(logn)轮，故双黑修正过程总共耗时不超过O(logn)。

  即便计入此前的关键码查找和节点摘除操作，红黑树的节点删除操作总是可在O(logn)时间内完成。

  一旦在某步迭代中做过节点的旋转调整，整个修复过程便会随即完成。因此与双红修正一样，双黑修正的整个过程，也仅涉及常数次的拓扑结构调整操作。

  这同样也是红黑树与AVL树之间最本质的差别。（在本文章的开头，就说明了AVL的不足就在于删除时可能要多达logn次调整。）

五、完整RedBlack.h~

#pragma once #include "BinNode.h" #include "BST.h"namespace my_redblack {using mytree::BinNode;using mytree::BST;using mytree::RBColor;using mytree_marcro::stature;using mytree_marcro::IsRoot;using mytree_marcro::IsLChild;using mytree_marcro::HasLChild;using mytree_marcro::HasRChild;template<typename T=int>class RedBlack :public BST<T> {protected:using BinNodePtr = BinNode<T>*;protected:void solveDoubleRed(BinNode<T>* x);//双红修正void solveDoubleBlack(BinNode<T>* replacer);//双黑修正constexpr int updateHeight(BinNode<T>* x)const override;//更新高度public:BinNode<T>* insert(const T& data)override;//插入重写bool remove(const T& data)override;//删除重写/*查找沿用BST的查找*//*遍历沿用BinTree的遍历*/protected:static constexpr bool IsBlack(const BinNodePtr& x) {//判黑//当然x为空，也为黑色return ((!x) || (RBColor::BLACK == x->_color));}static constexpr bool IsRed(const BinNodePtr& x) {//非黑即红return !IsBlack(x);}static constexpr bool IsBlackHeightBalanced(const BinNodePtr& x) {//判断是否需要更新黑高度bool is_L_C_Equal = (stature(x->_lchild) == stature(x->_rchild));int rbHeight = (IsRed(x) ? stature(x->_lchild) : stature(x->_lchild) + 1);//对于rbHeight的计算而言，取左孩子还是右孩子，均一样bool is_Height_Equal = (x->_height == rbHeight);return is_L_C_Equal && is_Height_Equal;//只要有一个为假，即为假//所以只要左孩子和右孩子高度相等，或者x没有高度变化，就黑高度平衡 }static inline BinNodePtr uncle(const BinNodePtr& x) {/*获取x的叔叔*/return IsLChild(x->_parent) ? x->_parent->_parent->_rchild : x->_parent->_parent->_lchild;}};//class RedBlacktemplate<typename T>constexpr int RedBlack<T>::updateHeight(BinNode<T>* x) const//由于stature视空节点高度为-1，所以height会比黑高度少一{x->_height = std::max(stature(x->_lchild), stature(x->_rchild));//孩子一般黑高度相等，除非出现双黑return IsBlack(x) ? x->_height++ : x->_height;//若当前节点为黑，则计入黑高度}template<typename T>void RedBlack<T>::solveDoubleRed(BinNode<T>* x){while (true) {if (IsRoot(x)) {//若已迭代到树根，则树根转黑，整树高度也随之递增this->_root->_color = RBColor::BLACK;this->_root->_height++;return;}//否则x的父亲必然存在BinNode<T>* p = x->_parent;//x的父亲if (IsBlack(p))//如果x的父亲为黑，则终止调整return;//否则x的父亲必然为红，则BinNode<T>* g = p->_parent;//x的祖父必然存在，并且，其颜色必然为黑色BinNode<T>* u = uncle(x);//x的叔叔，可能为空节点if (IsBlack(u)) {//当u为黑色时（u为空时，也为黑色）//if (IsLChild(x) == IsLChild(p))// p->_color = RBColor::BLACK;//else// x->_color = RBColor::BLACK;//g->_color = RBColor::RED;/// 以上虽保证总共两次染色，但因增加了判断而得不偿失/// 在旋转后将根置黑、孩子置红，虽需三次染色但效率更高BinNode<T>*& newNode = this->FromParentTo(g);//先记录祖父的父亲的孩子指针newNode = this->rotateAt(x);/*对x进行调整，调整之后的返回值必然为调整之后的局部子树的树根位置，此时，只需要将此树根作为原来祖父的父亲的孩子既可，当然，高度也随之更新*///重染色/*能省去之前的判断*/newNode->_color = RBColor::BLACK;newNode->_lchild->_color = RBColor::RED;newNode->_rchild->_color = RBColor::RED;return;//只要旋转了一次，就调整完整，退出循环}else {//若u为红色p->_color = RBColor::BLACK;//父亲此时必然为红色，将其转黑p->_height++;u->_color = RBColor::BLACK;//叔叔此时必然为红色，将其转黑u->_height++;if (!IsRoot(g))//如果祖父不为根节点，就转红g->_color = RBColor::RED;//solveDoubleRed(g);//递归用x = g;//将x变成其祖父，进入迭代循环。}}}template<typename T>BinNode<T>* RedBlack<T>::insert(const T& data){BinNode<T>*& x = this->search(data);//沿用BST的查找//并更新_hot//用引用接收if (x)//如果节点存在，则返回return x;x = new BinNode<T>(data, this->_hot, nullptr, nullptr, -1);//设定黑高度-1，并默认节点为红色this->_size++;solveDoubleRed(x);//双红修正//x此时必为红return x;}template<typename T>void RedBlack<T>::solveDoubleBlack(BinNode<T>* replacer){while (true) {BinNode<T>* p = replacer ? replacer->_parent : this->_hot;if (p == nullptr)return;//如果replacer的父亲为空，则返回/*由下面的情况来分析，无论哪种情况，递归的这个节点，必然为黑色*/所以不需要考虑将根节点强转黑色BinNode<T>* sibling = (replacer == p->_lchild) ? p->_rchild : p->_lchild;//原来x的兄弟，也就是replacer此时的兄弟if (IsBlack(sibling)) {BinNode<T>* s_Red_child = nullptr;//sibling的红孩子（若左右孩子皆为红，则左者优先；皆黑时为nullptr）if (IsRed(sibling->_rchild))//需要判断sibling是不是空指针s_Red_child = sibling->_rchild;//右孩子if (IsRed(sibling->_lchild))s_Red_child = sibling->_lchild;//左孩子/*1.第一种情况，黑s有红孩子*/if (s_Red_child != nullptr) {//如果sibling有红孩子RBColor oldColor = p->_color;//备份父亲的颜色/*接下来对s的红孩子，s以及p进行3+4重构*//*根据3+4重构后的定义，其返回的节点为根节点指针，这个根节点的名字不妨设为newNode*/BinNode<T>*& newNode = this->FromParentTo(p);//首先记录父亲的 父亲的孩子的指针newNode = this->rotateAt(s_Red_child);//3+4重构//对3+4重构后的节点进行重染色if (HasLChild(newNode)) {newNode->_lchild->_color = RBColor::BLACK;updateHeight(newNode->_lchild);}if (HasRChild(newNode)) {newNode->_rchild->_color = RBColor::BLACK;updateHeight(newNode->_rchild);}newNode->_color = oldColor;//新子树根节点继承原根节点的颜色updateHeight(newNode);//更新高度/*至此，就调整完毕，红黑树恢复平衡*/return;//用递归的时候注释掉}/*黑s没有红孩子，及其孩子均为黑色（可能为空）,对其父亲是否为红色进行判断*/else {sibling->_color = RBColor::RED;//无论父亲是否为红色，都需要把s设为红色sibling->_height--;/*2.黑s只有黑孩子（可能为空，并且其父亲为红色*/if (IsRed(p)) {p->_color = RBColor::BLACK;//直接将父亲设定为黑色，父亲的高度必然没有发生变化。//因为p原来为红，现在由于两个孩子高度都减了一，所以将其变成黑色后，其高度就恢复了原来的高度/*至此，就调整完毕，红黑树恢复平衡*/return;//用递归的时候注释掉}/*3.黑s只有黑孩子（可能为空，并且其父亲为黑色*/else {p->_height--;//相当于p的父亲被删，然后对p是父亲的replacer，因此，对p进行递归既可。//solveDoubleBlack(p);//用递归时用replacer = p;//将replacer变成p进入迭代循环//用递归的时候注释掉/*之后可能进入1 2 3 4四种情况中的任何一种，最坏可能到根*/}}}/*4.s为红，此时其必然只有黑孩子（黑孩子可能均为空），当然s的父亲p此时也必然为黑*/else {sibling->_color = RBColor::BLACK;//将s和p的颜色互换p->_color = RBColor::RED;//取与s同侧的孩子BinNode<T>* s_child = IsLChild(sibling) ? sibling->_lchild : sibling->_rchild;this->_hot = p;//首先将p的父亲记录起来BinNode<T>*& newNode = this->FromParentTo(p);//首先记录p的 父亲的孩子的指针newNode = this->rotateAt(s_child);//将s_child,s与p 进行3+4重构/*调整之后，树的局部结构就发生了变化*///solveDoubleBlack(replacer);//用递归时用//由第四种情况的分析，可知，只需要修复重构后的replacer就可以//并且之后只有可能进入第一种和第二种情况，必然不可能进入第三种情况}}}template<typename T>bool RedBlack<T>::remove(const T& data){BinNode<T>*& x = this->search(data);//找有没有这个节点，如果没有，则返回false,记住用引用if (!x)return false;BinNode<T>* replacer = removeAt(x, this->_hot);//调用在BST定义的全局静态函数removeAt,返回被删除节点的接替者，同时更新_hot--this->_size;//更新规模//1.如果这个被删除节点是树中唯一节点，则直接返回if (this->_size==0) {this->_root = nullptr;//将根节点置空return true;}//2.如果被删除节点为根节点，则_hot必然为空//但如果进行到此，说明此时_root必然不为空，不然上一就会退出if (this->_hot == nullptr) {this->_root->_color = RBColor::BLACK;//就将此时的根节点直接染成黑色updateHeight(this->_root);//并更新根节点的高度return true;}//如果进行到此，说明被删除节点必然存在，并且不为根节点。_hot也必然存在/*3.如果_hot的黑高度不变则返回*//*此时也必然包括了被删除节点为红色节点的情况，若为红色，则删除对高度没有影响*//*当然，也包括了双黑的可能情况*/if (IsBlackHeightBalanced(this->_hot))return true;/*4.如果_hot的黑高度变了，说明被删除节点必然为黑色*/if (IsRed(replacer)) {//就看x的接替者是不是红色，如果是红色，将其染成黑色，就必然可以使树的高度恢复。replacer->_color = RBColor::BLACK;replacer->_height++;return true;}/*5.如果进行到此，就必然说明被删除节点和replacer均为黑色节点（replacer可能为空），此时，就需要进行双黑缺陷判断*//*要进行到这里的条件即为被删除节点的父亲的黑高度变了，并且被删除节点的接替者也为黑色时。*/solveDoubleBlack(replacer);return true;}}//namespace my_redblack

六、红黑树测试~

1.插入测试代码~

#include<iostream> #include "RedBlack.h" using namespace std; using namespace my_redblack;template<typename BinNodePtr> void visite(BinNodePtr x) {cout << "数据为：" << x->_data << " ";if (x->_color == RBColor::RED) {cout << "颜色为：" << "红" << " ";}else {cout << "颜色为：" << "黑" << " ";}cout << endl; } int main() {RedBlack r;for (int i = 0; i < 10; ++i) {r.insert(i);}cout << "层次遍历为：" << endl;r.travLevel(visite<BinNode<int>*>);cout << endl;cout << "先序遍历为：" << endl;r.travPre(visite<BinNode<int>*>);cout << endl;cout << "中序遍历为：" << endl;r.travIn(visite<BinNode<int>*>);cout << endl;cout << "后序遍历为：" << endl;r.travPost(visite<BinNode<int>*>);cout << endl;return 0; } 层次遍历为： 数据为：3 颜色为：黑 数据为：1 颜色为：黑 数据为：5 颜色为：黑 数据为：0 颜色为：黑 数据为：2 颜色为：黑 数据为：4 颜色为：黑 数据为：7 颜色为：红 数据为：6 颜色为：黑 数据为：8 颜色为：黑 数据为：9 颜色为：红先序遍历为： 数据为：3 颜色为：黑 数据为：1 颜色为：黑 数据为：0 颜色为：黑 数据为：2 颜色为：黑 数据为：5 颜色为：黑 数据为：4 颜色为：黑 数据为：7 颜色为：红 数据为：6 颜色为：黑 数据为：8 颜色为：黑 数据为：9 颜色为：红中序遍历为： 数据为：0 颜色为：黑 数据为：1 颜色为：黑 数据为：2 颜色为：黑 数据为：3 颜色为：黑 数据为：4 颜色为：黑 数据为：5 颜色为：黑 数据为：6 颜色为：黑 数据为：7 颜色为：红 数据为：8 颜色为：黑 数据为：9 颜色为：红后序遍历为： 数据为：0 颜色为：黑 数据为：2 颜色为：黑 数据为：1 颜色为：黑 数据为：4 颜色为：黑 数据为：6 颜色为：黑 数据为：9 颜色为：红 数据为：8 颜色为：黑 数据为：7 颜色为：红 数据为：5 颜色为：黑 数据为：3 颜色为：黑

2.插入测试图示~

3.删除测试代码~

#include<iostream> #include "RedBlack.h" using namespace std; using namespace my_redblack;template<typename BinNodePtr> void visite(BinNodePtr x) {cout << "数据为：" << x->_data << " ";if (x->_color == RBColor::RED) {cout << "颜色为：" << "红" << " ";}else {cout << "颜色为：" << "黑" << " ";}cout << endl; } int main() {RedBlack r;for (int i = 0; i < 10; ++i) {r.insert(i);}cout << "中序遍历为：" << endl;r.travIn(visite<BinNode<int>*>);cout << endl;for (int i = 0; i < 10; ++i) {r.remove(i);r.travIn(visite<BinNode<int>*>);cout << endl;}return 0; } 中序遍历为： 数据为：0 颜色为：黑 数据为：1 颜色为：黑 数据为：2 颜色为：黑 数据为：3 颜色为：黑 数据为：4 颜色为：黑 数据为：5 颜色为：黑 数据为：6 颜色为：黑 数据为：7 颜色为：红 数据为：8 颜色为：黑 数据为：9 颜色为：红数据为：1 颜色为：黑 数据为：2 颜色为：红 数据为：3 颜色为：黑 数据为：4 颜色为：黑 数据为：5 颜色为：黑 数据为：6 颜色为：黑 数据为：7 颜色为：黑 数据为：8 颜色为：黑 数据为：9 颜色为：红数据为：2 颜色为：黑 数据为：3 颜色为：黑 数据为：4 颜色为：黑 数据为：5 颜色为：黑 数据为：6 颜色为：黑 数据为：7 颜色为：黑 数据为：8 颜色为：黑 数据为：9 颜色为：红数据为：3 颜色为：黑 数据为：4 颜色为：红 数据为：5 颜色为：黑 数据为：6 颜色为：黑 数据为：7 颜色为：红 数据为：8 颜色为：黑 数据为：9 颜色为：红数据为：4 颜色为：黑 数据为：5 颜色为：黑 数据为：6 颜色为：黑 数据为：7 颜色为：红 数据为：8 颜色为：黑 数据为：9 颜色为：红数据为：5 颜色为：黑 数据为：6 颜色为：红 数据为：7 颜色为：黑 数据为：8 颜色为：黑 数据为：9 颜色为：红数据为：6 颜色为：黑 数据为：7 颜色为：黑 数据为：8 颜色为：黑 数据为：9 颜色为：红数据为：7 颜色为：黑 数据为：8 颜色为：黑 数据为：9 颜色为：黑数据为：8 颜色为：黑 数据为：9 颜色为：红数据为：9 颜色为：黑

4.删除测试图示~

七、结语~

本系列文章，总共6篇，分别介绍了

基本二叉树节点（1w9字）

基本二叉树类（6000字）

BST（1w2字）

AVL（1w1字）

B树（1w5字）

红黑树（2w8字）

  其中B树和红黑树的难度最大的，这两种树情况分析确实十分复杂，除非背下来，不然是不可能在短时间内一下就能分析出这么多情况，并且不发生遗漏的。

  在此，再次感谢邓老师的教材和视频，我才能够掌握树的核心框架。并且感谢发明这些树的前辈们，多亏了他们的智慧，才有了这些高效的数据结构和算法的出现，提高了我们的计算机处理问题的能力。

  并且不知不觉，算上代码，此系列文章也写了将近9w字。零零散散大概写了两个星期左右。初衷是想要锻炼一下c++的编程能力以及数据结构和算法。但写着写着就想尽可能地将内容完善，简洁，并且简单易懂地描述各种插入和删除的过程。

  我相信，只要你从头看下来，你对树的理解必然会上升一个档次。如果你对某些地方的算法有所困惑，那不妨将其手敲一遍，对照着文章再看一遍，或者看下邓老师的书和讲解，你一定能理解这里为什么要用这种算法。

  c++就我个人理解而言，是一门非常严谨的语言。写c++代码的时候，要考虑的因素很多，因此可能初学起来相对java，c#等语言而言，会感到进度缓慢，但只要入门了之后，特别是了解了c++11常用特性，以及c++的常用语法之后，你会对c++越来越喜爱，也会明白为什么c++是世界上效率最高的语言。

  废话不多说，感谢你能耐心看完我精心准备的此系列文章，虽然我已经和邓老师的代码的各个实现进行了比对，但难免会有所遗漏之处，希望广大读者能够即时进行指正。

  如果你觉得对你有用，请不要光收藏，你的赞是我继续分享好东西的动力。

另外，借用侯捷大师的话：

学一个东西，不知道其道理，不高明！

总结

以上是生活随笔为你收集整理的真c++ 从二叉树到红黑树（6）之红黑树RedBlack的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。