红黑树（RBTree）的模拟实现

目录

为什么要存在红黑树呢？

红黑树的相关概念

红黑树的性质（或者说规定）

RBTree和AVLTree的思想差异以及性能对比

RBTree的基础框架

RBTree的Insert

实现过程

Insert的整体代码

检验一棵树是否为红黑树的方法

Insert的测试

RBTree的Erase

实现过程

Erase的整体代码

Erase的测试

红黑树的迭代器

实现过程

RBTree类的begin()等接口、RBTreeIterator类的operator*()等接口

前置和后置的operator++和operator--接口

迭代器的整体代码

迭代器的测试

红黑树的整体代码

为什么要存在红黑树呢？

问题：在前面学习BSTree（二叉搜索树）和AVLTree（高度平衡二叉搜索树）的时候我们说过，红黑树是一种需要控制高度平衡的二叉搜索树，但既然已经存在了AVLTree，它也是一种需要控制高度平衡的的二叉搜索树，为什么还要存在RBTree呢？

答案：因为AVLTree要求每一个节点的左右子树的高度差都不超过1，即对于【平衡】的要求过于严格，是一种【绝对平衡】，所以AVLTree在插入节点和删除节点时，一定会大量发生旋转，而我们在<<AVL树（高度平衡二叉搜索树）的模拟实现>>一文中说过，旋转的时间复杂度为O(1)，可不要小看这O（1），在大量发生旋转的情况下，也是有消耗的。所以，正是因为大量发生旋转导致AVLTree的性能降低，所以又诞生了RBTree，即红黑树。注意这里不是说AVLTree不好，相反，AVLTree的效率和性能已经是非常优秀了的，如果没有RBTree的存在，目前各种需要用RBTree的场景肯定都会使用AVLTree替代，只不过因为RBTree比AVLTree更加优秀，所以AVLTree才在RBTree的光环下泯然众人矣。

红黑树的相关概念

强调一下，红黑树中所说的路径是指从任意非NIL节点到NIL节点的路径，而不是从任意非NIL节点到叶子节点的路径（NIL节点就是nullptr节点），但注意NIL节点不算1个长度。

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位（即给Node类增加一个color成员）表示结点的颜色，可以是Red或Black。 通过对任何一条从根节点到NIL节点的路径上各个结点着色方式的限制，红黑树可以确保没有一条路径会比其他路径长出两倍（路径是指从根节点到NIL节点的路径，但注意NIL节点不算1个长度），即最长路径不会超过最短路径的两倍，因而是接近平衡的。

红黑树的性质（或者说规定）

再次强调一下，红黑树中所说的路径是指从任意非NIL节点到NIL节点的路径，而不是从任意非NIL节点到叶子节点的路径（NIL节点就是nullptr节点），但注意NIL节点不算1个长度。

1. 每个结点不是红色就是黑色。

2. 根节点是黑色的。

3. 对于每个结点，从该结点到其所有后代NIL节点的简单路径上，均包含相同数目的黑色结点，即树中每条路径的黑色节点数量相等。本质上这一点就控制了每条路径上黑色节点的数量。

4. 如果一个节点是红色的，则它的两个孩子结点是黑色的，换句话说就是红黑树中没有连续的红色节点。本质上这一点就控制了最长路径（控制不了最短，因为最短可以没有红色节点）上红色节点的数量。

通过这些性质，就能让红黑树确保没有一条路径会比其他路径长出两倍（路径是指从根节点到NIL节点的路径，但注意NIL节点不算成1个长度），即最长路径不会超过最短路径的两倍（但注意可以是相等的），因而是接近平衡的。既然最长路径都不会超过最短路径的两倍，其他路径就更不会超过最短路径的两倍了。

问题：为什么满足上面性质，就能让红黑树确保从根节点到所有NIL节点的路径中，没有一条路径会比其他路径长出两倍，即最长路径不会超过最短路径的两倍呢？

答案：因为如果满足上面的性质，理论上从根节点到NIL节点的最短的路径就是一条全部由黑色节点组成的路径，而理论上最长的路径就是一条严格由一黑一红组成的路径，所以红色节点和黑色节点的数量完全相同，相当于最短路径假如有N个节点，那最长路径就是2N，所以最长路径不会超过最短路径的两倍（不超过，但可以相等）。

（紧接上一段）而假如是从非根节点X到NIL节点的路径，如果X节点是黑色节点，那结论与结论的原因都和上一段一样：假如最短路径长度是N，则最长路径也是2N；但如果X节点是红色节点，比如下图的节点8到NIL节点的路径，那最短路径就不是全黑的了，而是一条由一个红色的X节点加剩余的全是黑色的节点组成的路径，而最长路径就不是严格的一黑一红了，红色节点会比黑色节点多一个，所以假如最短路径是N，则最长路径就是（N-1）*2+1，注意N-1是为了表示最短路径中黑色节点的个数。可以看到最长路径也不超过最短路径的2倍。

所以综上所述，只要满足红黑树上面所列举的性质，就能确保从任意节点到NIL节点的路径中，没有一条路径会比其他路径长出两倍，即最长路径不会超过最短路径的两倍

RBTree和AVLTree的思想差异以及性能对比

通过上文可以看出，红黑树控制平衡的思想就就是把AVLTree严格的绝对平衡调整成不严格的近似平衡。起到的正面作用就是RBTree相比于AVLTree，在插入或者删除同样数量的节点时，RBTree发生的旋转更少，而AVLTree发生的旋转更多；

但注意起到了正面作用的同时，也有负面作用。比如在查找某个节点时，因为AVLTree的高度严格平衡，所以AVLTree的最低高度为 (logN)-1，最大高度为logN，N表示节点总数，所以最坏情况下，在N个节点中查找一个节点最多找logN次，如果N是1000，则最多找10次（因为log1000=10），如果N是100w，则最多找20次，如果N是10亿，则最多找30次。而RBTree就不一样了，因为它的高度不需要严格平衡，只需要确保从根节点到所有NIL节点的路径中，没有一条路径会比其他路径长出两倍，即最长路径不会大于等于最短路径的两倍即可，所以可以认为RBTree中的最小高度，即从根节点到NIL节点的最短路径是logN，而最大高度，即从根节点到NIL节点的最大路径是2*logN，所以最坏情况下，在N个节点中查找一个节点最多找2*logN次，如果N是1000，则最多找20次（因为log1000=10），如果N是100w，则最多找40次，如果N是10亿，则最多找60次。可以看到在相同情况下，RBTree查找的次数是AVLTree的双倍次。

但注意上面所说的负面作用不算啥，即使RBTree查找的次数是AVLTree的2倍，但相较于AVLTree在插入删除、尤其是删除时的频繁发生旋转而言，RBTree查找的代价也不算大，为什么呢？因为查找的次数的量级太小了，即使AVLTree和RBTree在10亿个节点中查找也不过是30次和60次的区别，而每找一次，换算成代码也就是不到10行代码（先if判断，然后向下更新双指针），对于现代CPU来说不算啥，这就像两个人比财产，在了，一个人只有5毛钱，另一个人即使是它的2倍，也只不过有1块钱而已，1块钱对于来说算个p。而旋转就不一样了，因为AVLTree在删除时，有可能一直要让旋转持续到根的位置，也就是旋转高度次，不同类型的旋转的代码量不同，但起码40到50行代码，当AVLTree的高度是30时，最坏的查找次数为30，对比RBTree的最坏查找次数（60次），少了30次查找，即少了大概30*10（上面说了，单次查找大概10行代码）行代码，而最坏旋转高度次（30次），比RBTree多了大概30次旋转，即多了大概30*50（上面说了，单次旋转大概40到50行代码）行代码，这个代价可就大了。

所以上面说了这么多，就是在讲虽然AVLTree的查找比RBTree的查找更优，但也没优多少，性能的差别不大，但RBTree在插入和删除时的性能就远比AVLTree要高了，所以总体上RBTree的性能还是更优秀的。

RBTree的基础框架

#pragma once#include<iostream>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x,color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree<T>():_root(nullptr){}private:Node* _root;};

和AVLTree的基础框架不一样的是把平衡因子换成了color颜色，其他都没啥区别。

RBTree的Insert

实现过程

红黑树是在二叉搜索树BSTree的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：1. 按照二叉搜索的树规则插入新节点。2. 检测新节点插入后红黑树的性质是否造到破坏，如果受到破坏则需要变色进行调整，若有需要，可能还会发生旋转，如果忘了左单旋和右单旋，还请先回顾<<AVL树（高度平衡二叉搜索树）的模拟实现>>一文。

咱们先来进行第一步：按照二叉搜索树的规则插入新节点。回看BSTree的插入，如下图所示。

根据上图咱们就能编写出以下代码，注意我们在插入的过程中，要顺便把新插入的节点的颜色给设置好。（这里先给出代码，然后在下文中解释代码）

#pragma once#include<iostream>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x,color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree<T>():_root(nullptr){}bool Insert(const T& x){if (_root == nullptr){_root = new Node(x, black);return true;}else{Node* cur = _root;Node* curParent = nullptr;while (cur != nullptr){if (x > cur->_data){curParent = cur;cur = cur->_right;}else if (x < cur->_data){curParent = cur;cur = cur->_left;}else{return false;}}//找到了nullptr空位置，开始插入if (x > curParent->_data){cur = new Node(x, red);curParent->_right = cur;cur->_parent = curParent;}else{cur = new Node(x, red);curParent->_left = cur;cur->_parent = curParent;}//插入成功，开始调整颜色控制平衡，这是第二阶段的任务/*————未完待续————*/return true;}}private:Node* _root;};

上文说过【在插入的过程中，要顺便把新插入的节点的颜色给设置好】，而根据上面代码可以看到，上面代码插入新节点时，除了第一次插入新节点，也就是插入根节点时给节点的颜色是黑色，其他插入节点的时候都给的是红色，这是为什么呢？看了下面的问题与答案你就知道了。

问题：根据上面讲解性质的部分，我们知道红黑树的根节点必定是黑色节点，因此上面代码中第一次插入新节点时，给节点的颜色是黑；现在有一个问题，第二次、第三次、第N次插入新节点时，给新节点的颜色是红色比较好，还是黑色比较好呢？

答案：先给答案再分析，答案是红色。咱们分析一下（结合下图思考），新插入一个节点时（注意数量是1），如果是黑色，则此时从根节点到NIL节点的所有路径上的黑色节点就一定不再相同（注意是一定），则就违反了上面的性质3；而如果是红色，则此时可能会存在连续的红色节点（注意只是可能），则就可能会违反上面的性质4（注意只是可能）。从前面可以看出，如果选择是黑色，则一定违反规则，而如果选择红色，只是可能会违反规则，所以这是我们选择红色的第一个理由。那第二个理由是什么呢？结合上面讲解红黑树的性质（或者说规定）的部分可以看出，那就是如果选择黑色，则整棵树都会受到影响，即每条路径都会受到影响，调整起来就会极度麻烦，伤筋动骨；而如果选择红色，最多只有一条路径会破坏红黑树的性质，甚至根据前面的理由1我们可知有可能插入后没有路径会破坏红黑树的性质，所以最多只需要调整一条路径即可，所以这就是我们选择红色的第二个理由。

既然上面决定了新插入节点是红色节点，接下来咱们说说Insert的第二步：在插入新节点完毕后如果产生了连续的2个红色节点，破坏了性质4，该如何控制平衡。

为了归类归得简单一点，咱们把会产生连续两个红色节点的情况分为3类。这里为什么标红呢？就是为了再次强调：因为新插入节点都是红色节点，所以如果新插入节点的父亲节点是黑色节点，则无需进行调整，这种情况不属于下面即将说明的三种情况中的任何一种。

假如把新插入节点称为cur，cur的父亲节点为parent，cur的爷爷节点叫grandParent，cur的叔叔节点叫uncle，注意下图的p或者u是这些节点名称的缩写。

第一种情况如下图的区域1，本种情况是无所谓cur是parent的左孩子还是右孩子的。此时新插入节点的父亲节点parent和叔叔节点uncle都是红色节点，则此时爷爷节点grandParent一定存在（因为如果不存在，则parent一定是黑色节点，parent一定是整棵树的根节点）且是黑色节点（因为如果为红色，则在插入前就不满足红黑树的性质4，插入cur前整棵树就不是一棵红黑树）。在这种情况下，不管cur是parent的左孩子还是右孩子，都只需要把parent和uncle节点都变成黑色，然后看grandParent是否为整棵树的根节点，如果不是，则把grandParent变成红色，然后继续往上调整一次（需要继续往上调整一次的原因在下面说），具体做法就是让cur指针指向grandParent节点，并更新parent、uncle、grandParent指针的指向，然后继续调整（如何调整得根据各个指针指向节点的情况决定，看所处的情况是正在讲解的3种情况中的哪一个，然后根据各自情况的调整变色规则变色）；如果是，则直接结束Insert函数，插入成功。

（有一种记忆第一种情况的方式，就是不管cur、parent、grandParent呈现成一条直线还是折线，只要存在uncle节点且为红色，那就是第一种情况）

问题：上一段为什么说如果grandParent节点不是整棵树的根节点，则要把grandParent变成红色后继续往上调整呢？

答案：因为如果grandParent的父亲节点存在，则grandParent的父亲节点可能为红色节点，也可能为黑色节点，而只要grandParent的父亲节点为红色节点，因为grandParent在变色调整后也是红色节点，此时就会产生连续的红色节点，就会破坏上文中所说的性质4。所以综上所述，把grandParent变成红色后，是有可能破坏红黑树的性质4的，所以需要往上调整一次（注意只是一次），看看到底是否破坏了性质4。如果破坏了，则根据节点之间的形状判断是文中所讲的第几种情况并进行调整，如果没有破坏，则插入新节点成功，直接结束Insert函数即可。

有了上面的铺垫，我们就知道了cur指针可能会往上走进行变色调整，所以也就意味着cur指向的节点并不一定是新插入节点，还有可能是被变色调整完毕后的子树的根节点，所以第一种情况还可以画成下图区域1这样，a、b、c、d、e都是根节点为黑色节点的子树（因此绝无可能是空树）。对于下图情况，因为cur和parent是连续红色节点，所以也需要进行变色调整，变色方法和上一段是完全一致的。

注意上面讲解第一种情况时给出的所有示例图的区域1都是cur与parent节点在grandParent节点的左子树上，uncle节点在grandParent节点的右子树上。这里我想说的是如果发生对调，即如果cur与parent节点在grandParent节点的右子树上，uncle节点在grandParent节点的左子树上，则变色以及调整的方法也和上文中完全一致。这里说一下如何判断cur与parent节点在grandParent节点的左子树还是右子树上：如果parent是grandParent的左孩子，则cur与parent节点都在grandParent节点的左子树上（因为cur是parent的孩子节点，cur与parent是绑定在一起的）；如果如果parent是grandParent的右孩子，则cur与parent节点都在grandParent节点的右子树上。

————分割线————

第二种情况如下图区域1，cur一定是和parent与grandParent形成一条直线，此时uncle不存在，cur是新插入节点（当uncle节点不存在时，cur一定是新插入节点，因为假如cur不是新插入的，则说明cur还有自己的子树，为了不产生连续红节点，在发生调整变色前，cur一定是黑色的，但这又会导致每条路径黑色节点不相同，所以假设是不成立的，所以cur一定是新插入节点），当新插入节点cur和cur的父亲节点parent节点都是红色节点，此时爷爷节点grandParent一定存在（因为如果不存在，则parent一定是黑色节点，parent一定是整棵树的根节点）且是黑色节点（因为如果为红色，则在插入前就不满足红黑树的性质4，插入cur前整棵树就不是一棵红黑树）。此时直接对grandParent节点为根节点的子树进行右单旋，旋转完毕后将grandParent从黑色变成红色，然后将旋转后的子树的根节点parent从红色变成黑色，此时Insert函数就结束了（原因在下面的问题与答案中），插入成功。

（有一种记忆第二种情况的方式，第二种情况就是cur、parent、grandParent呈一条直线，并且要么不存在uncle节点，要么存在且为黑色）

问题：为什么上一段最后Insert函数就结束了呢？或者换句话说，虽然在第一种情况中已经证明了子树的根节点被更新成红色时需要继续向上调整，但在第二种情况下为什么发生旋转后，旋转后的子树的根节点被更新成黑色就不需要向上调整，Insert函数就直接结束了呢？

答案：因为不管被旋转的树是整棵树，还是某棵子树，插入新节点发生旋转并且变色后，从子树到NIL节点的局部路径上，每一条路径上的黑色节点的数量对比【插入新节点前】的数量，没有发生变化，因此不会破坏性质3，并且此时也没有连续红色节点，所以也不会破坏性质4，既然我们能确定没有破坏红黑树的任何性质，所以也就确定此时无需做任何操作，插入Insert已经成功，所以可以直接让Insert函数结束了，所以就无需继续向上调整。

在讲解第一种情况时我们证明过cur不一定是新插入节点，还有可能是被变色调整完毕后的子树的根节点，所以第二种情况还可以画成下图区域1这样，a、b、c都是根节点为黑色节点的子树（因此绝无可能是空树）。此时uncle节点存在且为黑色，cur节点不是新插入节点，而是被变色调整完毕后的子树的根节点，cur节点是从调整前的黑色变成了红色，parent本来就是红色，则此时也违反了规则4，需要进行变色调整。如何调整呢？和上一段中说的一样，直接先对grandParent节点为根节点的子树进行右单旋，旋转完毕后将grandParent节点从黑色变成红色，然后将旋转后的子树的根节点parent从红色变成黑色，此时Insert函数就结束了，插入成功。

注意上面讲解第二种情况时给出的所有示例图的区域1都是cur与parent节点在grandParent节点的左子树上，uncle节点在grandParent节点的右子树上。这里我想说的是如果发生对调，即如果cur与parent节点在grandParent节点的右子树上，uncle节点在grandParent节点的左子树上，则虽然变色规则相同，但不同点在于此时需要进行左单旋，而不是原来的右单旋。这里说一下如何判断cur与parent节点在grandParent节点的左子树还是右子树上：如果parent是grandParent的左孩子，则cur与parent节点都在grandParent节点的左子树上（因为cur与parent是绑定在一起的）；如果如果parent是grandParent的右孩子，则cur与parent节点都在grandParent节点的右子树上。

————分割线————

第三种情况如下图区域1，cur一定是和parent与grandParent形成一条折线，当cur是新插入节点时，并且新插入节点cur和cur的父亲节点parent节点都是红色节点，此时爷爷节点grandParent一定存在且是黑色节点（因为如果为红色，则在插入前就不满足红黑树的性质4，插入cur前整棵树就不是一棵红黑树），但不存在uncle节点。（结合下图思考）此时直接对以parent为根节点的树进行左单旋，注意旋转完毕后还一定要将parent指针和cur指针的指向交换（即编写代码时一定要在左单旋后swap一下parent指针和cur指针的值，原因在下一段），此时节点之间就形成了和上文中的第二种情况完全一致的形状，接下来就照着上文第二种情况的做法去做即可控制平衡。

（有一种记忆第三种情况的方式，第三种情况就是cur、parent、grandParent呈一条折线，并且要么不存在uncle节点，要么存在且为黑色）

问题：上一段中为什么说编写代码时，对以parent为根节点的树进行左单旋后，要交换parent指针和cur指针的指向呢？（这里写一个日志：开始笔者没有交换指针的指向，这个坑可真是调试死我了，还要通过随机值找错误示例，然后结合下文中检验一棵树是否为红黑树的方法，发现插入第三次时，检测方法就打印出有根节点不为黑色的错误，所以从这里可以得到一个启示，检测一棵树是否为红黑树的检测方法非常重要，还能帮我们检查Insert或者Erase的代码是否有问题，知道错误原因后，又觉得找错很简单，毕竟既然是颜色不对，那问题肯定就出现在变色的那几行代码，变色的代码这么少，肯定很容易找错）

答案：（结合下图思考）理解完上一段的第三种情况后，我们知道第三种情况的处理方式（结合下图区域1思考）是通过对以parent为根节点的树进行左单旋后，让节点之间的形状成为情况2，即通过单旋函数把第三种情况变成第二种情况，然后按照第二种情况的处理方式解决剩下的问题。但此时就有一个问题，第二种情况的区域1是cur指针指向第三层的节点，parent指针指向第二层节点，因为最后旋转完毕后是要把该第二层的节点变成黑色，所以最后要通过parent指针把中间节点变成黑色，而第三种情况从区域1的形状经过旋转变成区域2的形状、也就是变成第二种情况的形状后，是cur指针指向第二层节点，如果在第三种情况下，从区域1单旋成区域2后，按照第二种情况的变色方式变色时（第二种情况的变色方式就是把parent指针指向的节点变成黑色），不把cur和parent指针的指向交换，那么parent指针就指向第三层的节点，按照第二种情况的处理方式，把parent指针指向的节点变成黑色就出错了，因为此时parent指针不指向第二层的节点，而是指向第三层的节点。

在上文中讲解第一种情况时我们证明过cur不一定是新插入节点，还有可能是被变色调整完毕后的子树的根节点，所以第三种情况还可以画成下图区域1这样。此时uncle节点存在且为黑色，cur节点不是新插入节点，而是被变色调整完毕后的子树的根节点，cur节点是从调整前的黑色变成了红色，parent本来就是红色，则此时也违反了规则4，需要进行变色调整。如何调整呢？和上一段中说的一样，此时也直接对以parent为根节点的树进行左单旋，旋转完毕后，此时节点之间就形成了和上文中的第二种情况完全一致的形状，接下来就照着上文第二种情况的做法去做即可控制平衡。

注意上面讲解第三种情况时给出的所有示例图的区域1都是cur与parent节点在grandParent节点的左子树上，uncle节点在grandParent节点的右子树上。这里我想说的是如果发生对调，即如果cur与parent节点在grandParent节点的右子树上，uncle节点在grandParent节点的左子树上，则此时需要从【对以parent为根节点的树进行左单旋】变成【对以parent为根节点的树进行右单旋】，然后第三种情况就会转化成第二种情况，所以剩下的操作就照着上文第二种情况的做法去做即可控制平衡。这里说一下如何判断cur与parent节点在grandParent节点的左子树还是右子树上：如果parent是grandParent的左孩子，则cur与parent节点都在grandParent节点的左子树上（因为cur与parent是绑定在一起的）；如果如果parent是grandParent的右孩子，则cur与parent节点都在grandParent节点的右子树上。

————end————

Insert需要的理论知识已经全部讲解完毕，加下来咱们就来编写第二阶段、同时也是最终阶段的Insert的代码。

首先编写两个单旋函数，为了减轻工作量，我们直接在<<AVL树（高度平衡二叉搜索树）的模拟实现>>一文中把AVL树的左单旋和右单旋的代码拷贝一份后略作修改，然后就拿来用，如何修改呢？啥也不用做，只需把修改平衡因子的两行代码给删除即可，代码如下。

#pragma once#include<iostream>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x,color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree<T>():_root(nullptr){}private:void RotateR(Node* p){if (p != _root){Node* subL = p->_left;Node* subLR = subL->_right;Node* p_parent = p->_parent;subL->_right = p;subL->_parent = p_parent;if (p == p_parent->_right)p_parent->_right = subL;elsep_parent->_left = subL;p->_left = subLR;p->_parent = subL;if (subLR != nullptr)subLR->_parent = p;}else{Node* subL = p->_left;Node* subLR = subL->_right;_root = subL;subL->_right = p;subL->_parent = nullptr;p->_left = subLR;p->_parent = subL;if (subLR != nullptr)subLR->_parent = p;}}void RotateL(Node* p){if (_root != p){Node* subR = p->_right;Node* subRL = subR->_left;Node* p_parent = p->_parent;subR->_left = p;subR->_parent = p_parent;p->_parent = subR;p->_right = subRL;if (p == p_parent->_right)p_parent->_right = subR;elsep_parent->_left = subR;if (subRL != nullptr)subRL->_parent = p;}else{Node* subR = p->_right;Node* subRL = subR->_left;_root = subR;subR->_left = p;subR->_parent = nullptr;p->_right = subRL;p->_parent = subR;if (subRL != nullptr)subRL->_parent = p;}}Node* _root;};

最后编写最终版本的Insert的代码，代码如下。

Insert的整体代码

#pragma once#include<iostream>#include<vector>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x,color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree<T>():_root(nullptr){}bool Insert(const T& x){if (_root == nullptr){_root = new Node(x, black);return true;}else{Node* cur = _root;Node* curParent = nullptr;while (cur != nullptr){if (x > cur->_data){curParent = cur;cur = cur->_right;}else if (x < cur->_data){curParent = cur;cur = cur->_left;}else{return false;}}//找到了nullptr空位置，开始插入if (x > curParent->_data){cur = new Node(x, red);curParent->_right = cur;cur->_parent = curParent;}else{cur = new Node(x, red);curParent->_left = cur;cur->_parent = curParent;}//插入新节点成功，开始控制平衡Node* parent = nullptr;Node* grandParent = nullptr;while (cur->_col == red)//如果调整到根节点来了，就不能再调整了。因为根节点的颜色必须是黑色，所以这里拿cur的颜色是红色作为继续循环的条件{parent = cur->_parent;//父亲节点不可能为nullptr，因此下一行代码无需判空grandParent = parent->_parent;//注意grandParent可能为nullptr//如果cur的爷爷节点存在，并且cur和parent是连续红色节点，此时才需要变色控制平衡;否则不需要控制平衡，此时插入新节点成功,直接就可以结束Insert函数了if (grandParent != nullptr && (cur->_col == red && parent->_col == red)){//当cur与parent节点都在grandParent的左子树上时走这里if (parent == grandParent->_left){Node* uncle = grandParent->_right;//第一种情况，此时无所谓cur与parent和grandParent是否为一条直线，但要求parent为红，uncle存在且为红//g// p u// cif (parent->_col == red && uncle != nullptr && uncle->_col == red){parent->_col = black;uncle->_col = black;if (grandParent != _root)grandParent->_col = red;cur = grandParent;}else if ((parent->_col == red && uncle == nullptr) || (parent->_col == red && uncle != nullptr && uncle->_col == black)){//第二种情况，此时cur与parent和grandParent是一条直线，parent为红，uncle不存在或者存在且为黑//g// p u // cif (cur == parent->_left){RotateR(grandParent);parent->_col = black;grandParent->_col = red;return true;}//第三种情况，此时cur与parent和grandParent是一条折线，parent为红，uncle不存在或者存在且为黑//g// p u //celse if (cur == parent->_right){//先对以p为根节点的树进行左单旋，旋转完毕后将parent指针和cur指针的指向交换，此时节点之间就形成了和第二种情况完全一致的形状，接下来就照着第二种情况的做法去做即可控制平衡。//先左单旋RotateL(parent);swap(parent, cur);//注意一定要交换两个指针的指向，否则本行下面第4行和第5行的代码（即变色的代码）会出问题，会给节点变错颜色。//然后按照第二种情况的做法去做RotateR(grandParent);parent->_col = black;grandParent->_col = red;return true;}}}//当cur与parent节点都在grandParent的右子树上时走这里else if (parent == grandParent->_right){Node* uncle = grandParent->_left;//第一种情况，此时无所谓cur与parent和grandParent是否为一条直线，但要求parent为红，uncle存在且为红//g// u p//cif (parent->_col == red && uncle != nullptr && uncle->_col == red){parent->_col = black;uncle->_col = black;if (grandParent != _root)grandParent->_col = red;cur = grandParent;}else if ((parent->_col == red && uncle == nullptr) || (parent->_col == red && uncle != nullptr && uncle->_col == black)){//第二种情况，此时cur与parent和grandParent是一条直线，parent为红，uncle不存在或者存在且为黑//g// u p //cif (cur == parent->_right){RotateL(grandParent);parent->_col = black;grandParent->_col = red;return true;}//第三种情况，此时cur与parent和grandParent是一条折线，parent为红，uncle不存在或者存在且为黑// g// u p // celse if (cur == parent->_left){//先对以p为根节点的树进行右单旋，旋转完毕后将parent指针和cur指针的指向交换，此时节点之间就形成了和第二种情况完全一致的形状，接下来就照着第二种情况的做法去做即可控制平衡。//先右单旋RotateR(parent);swap(parent, cur);//注意一定要交换两个指针的指向，否则本行下面第4行和第5行的代码（即变色的代码）会出问题，会给节点变错颜色。//然后按照第二种情况的做法去做RotateL(grandParent);parent->_col = black;grandParent->_col = red;return true;}}}}//如果cur的爷爷节点不存在，或者爷爷节点存在但cur和parent节点不同时为红色，此时不需要变色控制平衡,插入函数直接就可以结束了else//(grandParent == nullptr||(grandParent != nullptr && (cur->_col == black || parent->_col == black))){return true;}}//如果cur指针一直向上调整到了根节点，根节点被调整完毕后就会走出循环，出了循环后也要return true，不要忘记了return true;}}private:void RotateR(Node* p){if (p != _root){Node* subL = p->_left;Node* subLR = subL->_right;Node* p_parent = p->_parent;subL->_right = p;subL->_parent = p_parent;if (p == p_parent->_right)p_parent->_right = subL;elsep_parent->_left = subL;p->_left = subLR;p->_parent = subL;if (subLR != nullptr)subLR->_parent = p;}else{Node* subL = p->_left;Node* subLR = subL->_right;_root = subL;subL->_right = p;subL->_parent = nullptr;p->_left = subLR;p->_parent = subL;if (subLR != nullptr)subLR->_parent = p;}}void RotateL(Node* p){if (_root != p){Node* subR = p->_right;Node* subRL = subR->_left;Node* p_parent = p->_parent;subR->_left = p;subR->_parent = p_parent;p->_parent = subR;p->_right = subRL;if (p == p_parent->_right)p_parent->_right = subR;elsep_parent->_left = subR;if (subRL != nullptr)subRL->_parent = p;}else{Node* subR = p->_right;Node* subRL = subR->_left;_root = subR;subR->_left = p;subR->_parent = nullptr;p->_right = subRL;p->_parent = subR;if (subRL != nullptr)subRL->_parent = p;}}private:Node* _root;};

检验一棵树是否为红黑树的方法

因为红黑树是平衡二叉搜索树的一种，因此我们先检验这棵树是一棵搜索树，如果是搜索树，再检验是否平衡。这里笔者只说明如何检验平衡性，关于如何检验是否为搜索树就不详细说明了（比较粗糙的检验方法是中序遍历打印一下，看看是否为升序且没有重复元素，中序遍历Inorder的代码如下）。

#pragma once#include<iostream>#include<vector>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x,color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree<T>():_root(nullptr){}public:void Inorder(){_Inorder(_root);}private:void _Inorder(Node*root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_data << ' ';_Inorder(root->_right);}private:Node* _root;};

那如何检验搜索树是否平衡、或者说搜索树是否为红黑树呢？

问题：有人可能会说，测量一棵树中每个节点到NIL节点的最长路径和最短路径，如果每个节点的最长路径都不超过最短路径的2倍，那就是红黑树了。那能不能这样呢？

答案：不能，因为这样有点本末倒置了。我们是通过确保红黑树的4个性质不被破坏，间接性的确保了红黑树中任意节点到NIL节点的最长路径不超过最短路径的2倍，如果光是确保最长路径不超过最短路径的2倍，是无法确保每个节点的颜色是它应有的颜色的，或者换句话说，虽然我这棵树中任意一个节点的最长路径都不超过最短路径的2倍，但每个节点的颜色都是红色，很明显，这不是一棵红黑树。

那该怎么检验呢？正确答案是需要确保4个性质没被破坏。

先说说思路，然后再写代码。如何检测性质1、2就不多说了，如何检测性质3呢？

常见的方法是创建一个vector，然后设置一个blackNum记录遍历到当前节点时，路径上共有多少黑色节点，什么意思呢？结合上图思考，从根节点13开始前序遍历，一进递归函数，发现13是黑色节点，则把blackNum++，然后向左递归，发现8是红色节点，则blackNum不加1，继续向左递归，发现1是黑色节点，则把blackNum++，此时到节点1，就记录了2个黑色节点，然后再向左递归，发现遍历到了NIL节点（即nullptr节点），则直接把blackNum放进vector中，这样就记录了从根节点到NIL节点的若干路径的其中之一的路径上的黑色节点的数量，然后回退继续前序遍历。。通过这样的方式，每遍历到NIL节点就把blackNum的值放进vector，最后就能记录每一条路径上的黑色节点数量，如果vector中存储的某条路径上的黑色节点数量和其他路径不相等，则说明性质3被破坏了，反之就没有被破坏。

有人可能会说：不对啊，你不是说红黑树要求从任意一个节点到NIL节点的所有路径上的黑色节点数量相同吗，上面只检测了从根节点到NIL节点的所有路径上的黑色节点数量相同，除根节点外，还有这么多节点没有检测，你凭什么就说性质3没有被破坏呢？

答案：事实上，你可以结合上图思考一下，我们假设从节点8开始到NIL节点的所有路径上的黑色节点数量不相等，那你觉得从根节点到NIL节点的路径上的黑色节点数量会相同吗？答案是不会，因为从根节点到NIL节点这段路程涵盖了从节点8到NIL节点，因此如果从根节点到NIL节点的所有路径上的黑色节点数量相同，其他节点到NIL节点的所有路径上的黑色节点的数量也一定是相同的。

如何检验性质4呢？答案：在检测性质3的方法中顺便就能把性质4给检验了，比如在前序遍历每个节点时，如果遇到黑色节点就让blackNum++，如果遇到红色节点，此时就可以直接检测该节点的左右孩子节点（如果存在的话），看看孩子节点是否为红色节点，如果是，则破坏了性质4，如果没有，则没有破坏性质4。

————分割线————

有了上面的思路，貌似检验红黑树的平衡性的代码就很好写了，但注意，虽然上面的思路的确是没问题的，但实际上如果严格按照上面的思路写代码的话，在编写的过程中，代码会很繁琐，不好写，并且还要借助vector，存在一定的空间复杂度，如下代码所示。所以这只是第一种方法，该方法不是最优解。

#pragma once#include<iostream>#include<vector>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x,color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree<T>():_root(nullptr){}public:bool isbalance(){//检验性质2是否被破坏if (_root != nullptr && _root->_col == red){cout << "根节点不是黑色" << endl;return false;}//检验性质3和4是否被破坏，这俩性质都通过子函数 _isbalance检验，_isbalance的返回值用于检测性质4，传给_isbalance函数的vector作为输出型参数，用于检验性质3else{vector<int>v;bool factor3 = _isbalance(_root, 0, v); //_isbalance的返回值用于检测性质4，传给_isbalance函数的vector作为输出型参数，用于检验性质3//检验性质4if (factor3 == false)return false;//检验性质3for (int i = 0; i < v.size(); i++){if (v[0] != v[i]){return false;}}}return true;}private:bool _isbalance(Node* root,int blackNum,vector<int>&v){if (root == nullptr){v.push_back(blackNum);return true;}if (root != nullptr && root->_col == black){blackNum++;}//检验性质4，看是否有连续红色节点else if(root != nullptr && root->_col == red){if (root->_left != nullptr && root->_left->_col == red)return false;else if (root->_right != nullptr && root->_right->_col == red)return false;}bool x = _isbalance(root->_left, blackNum, v);if (x == false)//这是为了提高效率，剪枝return false;bool y = _isbalance(root->_right, blackNum, v);return y;}private:Node* _root;};

最优解的思路：如何检测性质3呢？思考一下，事实上我们不需要通过vector这样的容器记录从根节点到NIL节点的所有路径上的黑色节点数量，只需要知道一条路径上的黑色节点数量即可，然后将这个数量作为一个基准值benchmark，因为红黑树要求每条路径上的黑色节点数量相同，那么知道benchmark后，如果在前序遍历时，发现存在某条路径上的黑色节点数量不等于benchmark，那么性质3也就被破坏了。如何获取benchmark呢？选择一条最简单的路径，即一直向左走的路径或者一直向右走的路径，我们不要在子函数 _isbalance中递归获取，而是直接在父函数 isbalance中非递归，通过循环的方式获取，即让cur从_root开始，然后不断循环的cur=cur->_left向左遍历计算黑色节点的数量，计算出benchmark的值后，将基准值benchmark传给子函数，让子函数去递归计算每条路径上的黑色节点数量，然后看是否和benchmark相等，在这个过程中，我们可以顺便把性质4给检测了，在上一种方法中我们是检测左孩子和右孩子的颜色（如果孩子节点存在的话），我们发现这样是比较繁琐的，需要判空，判定颜色，还要检测两次（孩子节点有两个），所以在最优解中我们换一个方法，我们只检测当前节点的父亲节点，如果当前节点是红色，那么只检测父亲节点的颜色，如果为红色则破坏了性质4，反之则没有破坏性质4。

结合上面的思路，最优解的代码如下。

#pragma once#include<iostream>#include<vector>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x,color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree<T>():_root(nullptr){}public:bool isbalance(){//检验性质2是否被破坏if (_root != nullptr && _root->_col == red){cout << "根节点不是黑色" << endl;return false;}//检验性质3和4是否被破坏，这俩性质都通过子函数_isbalance检验else{int benchmark=0;Node* cur = _root;while (cur != nullptr){if (cur->_col == black){benchmark++;}cur = cur->_left;}return _isbalance(_root, 0, benchmark);}}private:bool _isbalance(Node* root,int blackNum,int benchmark){//检测性质3if (root == nullptr){if (blackNum != benchmark){cout << "某条路径上的黑色节点的数量和基准值benchmark不相等，性质3被破坏了" << endl;return false;}elsereturn true;}if (root->_col == black)blackNum++;//检测性质4if (root->_col == red && root->_parent->_col == red)//这里root->_parent不可能为nullptr，因为root的颜色是红色，所以root不可能为整棵树的根节点，所以root->_parent不可能为nullptr。{cout << "存在连续红色节点，性质4被破坏" << endl;return false;}bool x = _isbalance(root->_left, blackNum, benchmark);bool y = _isbalance(root->_right, blackNum, benchmark);return x && y;}private:Node* _root;};

Insert的测试

测试代码如下图所示。

RBTree的Erase

实现过程

红黑树和二叉搜索树的删除类似，只不过加上颜色属性，要删除目标节点首先得找到它，找到后，删除的情况可以分为以下四种。

第一种情况：要删除的目标节点无子节点。此时要删除的节点cur可能为红色或者黑色；

1.1：如果为红色，如下图，直接删除即可，不会影响黑色节点的数量，也不会破坏红黑树的性质（有一点要注意，删除cur后，记得把curParent指向cur的那个指针成员给设置成nullptr）。

1.2：如果为黑色，则删除后需要进行控制平衡的操作了，关于这个控制平衡，因为太过复杂，所以我们放到下文再说。

第二种情况：要删除的目标节点只有左子节点。此时要删除的目标节点cur只能是黑色，其子节点child只能为红色并且再没有子树，即形状必须如下图所示，否则就无法满足红黑树的性质了（注意curParent无所谓黑或者红）。 此时将要删除的目标节点的子节点child交给目标节点的父亲节点curParent托管，然后将子节点child的颜色涂黑，最后删除cur即可保证黑色节点的数量不变。该如何托管呢？父亲节点curParent有两个指针成员，为_left和_right，如果cur是curParent的左孩子，则让curParent的_left指针成员指向child（因为cur作为curParent的左孩子，cur的左右孩子节点都是小于curParent的）；如果cur是curParent的右孩子，则让curParent的_right指针成员指向child。注意，不要只顾着让curParent节点的_left或者_right成员指针指向child，还要让child节点的_parent成员指针指向curParent，笔者当时写时就踩过这个坑，导致调用用于检验是否为红黑树的函数时出现了解引用野指针的问题，调试了老半天┭┮﹏┭┮。

第三种情况：要删除的目标节点只有右子节点。此时要删除的目标节点cur只能是黑色，其子节点child只能为红色并且再没有子树，即形状必须如下图所示，否则就无法满足红黑树的性质了（注意curParent无所谓黑或者红）。 此时将要删除的目标节点的子节点child交给目标节点的父亲节点curParent托管，然后将子节点child的颜色涂黑，最后删除cur即可保证黑色节点的数量不变。该如何托管呢？父亲节点curParent有两个指针成员，为_left和_right，如果cur是curParent的左孩子，则让curParent的_left指针成员指向child（因为cur作为curParent的左孩子，cur的左右孩子节点都是小于curParent的）；如果cur是curParent的右孩子，则让curParent的_right指针成员指向child。注意，不要只顾着让curParent节点的_left或者_right成员指针指向child，还要让child节点的_parent成员指针指向curParent，笔者当时写时就踩过这个坑，导致调用用于检验是否为红黑树的函数时出现了解引用野指针的问题，调试了老半天┭┮﹏┭┮。

第四种情况：要删除的目标节点有两个子节点。此时与二叉搜索树的删除一样，使用后继节点（即目标节点的右子树中值最小的节点）作为替死鬼节点，替死鬼节点一定要么是没有孩子节点，要么是只有一个孩子节点，此时第四种情况就转换成了前三种情况中的任意一个，按照对应的情况处理即可。

我们可以发现，第四种情况总是会转换为前三种情况，而第一种情况的1.1和第二、三种情况的删除非常简单，所以接下来主要讨论的是第一种情况的1.2：要删除的目标节点没有孩子节点且为黑。此时一旦该节点被删除，红黑树中通过该节点的路径黑色节点数量将会减1，而且无法像第二、三种情况那样将子节点涂黑来达到平衡，所以只能自底向上进行平衡操作。

我们先约定一下节点名称，如下图。

然后我们再把【第一种情况的1.2：要删除的目标节点cur是黑色的叶子节点】这种情况细分成2类。

情形1：如果cur是整棵树的根节点，则直接删除cur节点，然后把_root指针的指向更新成nullptr，最后return true即可。

————分割线————

情形2：如果cur不是整棵树的根节点，则需要在情形2的基础上再次划分情形。

2.1：如果cur是curParent的左孩子。

2.1.1：如果cur的兄弟节点curBrother是黑色节点（说一下，当前情况cur是黑色节点，则curBrother节点是一定存在的，因为如果此时curBrother节点不存在，则会导致每条路径上的黑色节点数量不同，则不符合红黑树的性质3）

2.1.1.1：如果curBrother只有左孩子节点，则左孩子一定是红色节点，并且左孩子节点没有子树（否则不满足红黑树的性质），处理方式如下图。

2.1.1.2：如果curBrother只有右孩子节点，则右孩子一定是红色节点，并且右孩子节点没有子树（否则不满足红黑树的性质），处理方式如下图。

2.1.1.3：如果curBrother既有左孩子节点，又有右孩子节点，则左右孩子都一定是红色节点，并且左右孩子节点都没有子树（否则不满足红黑树的性质），此时处理方式可以完全按照2.1.1.1，也可以完全按照2.1.1.2，可以看到2.1.1.2只需要旋转一次，效率更高，所以本种情况的处理方式完全复用2.1.1.2即可，体现在代码上就是走同一个if分支。

2.1.1.4：如果curBrother没有孩子节点，此时就要根据curParent节点的颜色分类。

2.1.1.4.1：如果curParent是红色节点，处理方式如下图。

2.1.1.4.2：如果curParent是黑色节点，则处理方式为：把curBrother染红后直接删除cur节点，如下图1。（结合下图1思考）做完这些后，此时从curParent节点到所有NIL节点的所有路径上的黑色节点数量都少了1，这会导致在【curParent的所有祖先节点——>NIL节点】这些路径中，如果经过curParent节点，则路径上的黑色节点数量少1，如果不经过curParent节点，则路径上的黑色节点数量不变，此时不同路径上的黑色节点数量不同，就会破坏红黑树的性质3，为了保持平衡性，所以需要cur往上迭代调整一次，以此控制平衡（方法在下一段）。

图1如下。

图2如下。

那如何迭代调整呢？让cur和curParent指针向上走一次，选出新的curBrother节点，如上面的图2，然后继续“删除”cur指针指向的节点（注意这里的删除并不是真的删除，在向上调整的过程中，真正要删除的cur节点在第一次向上调整前就已经被删除了，或者说在上一段的第一句话中就已经被删除了，后序在向上调整控制平衡时，cur指针指向的节点是不能被删除的，只是通过cur指针指向的节点辅助控制平衡，也就是说，这里的“删除”只表示控制平衡的意思）。

既然上一段中说“删除”不是真的删除，而只表示控制平衡，那该如何理解通过“删除”cur节点来控制平衡呢？

首先要知道，在cur指针向上走控制平衡的过程中，即使cur指针指向的这个黑色节点有孩子节点，我们也要当作他是没有孩子节点的，这是向上调整的守则（顺便一提，这个守则体现在代码上就是让cur指针向上迭代调整的while循环位于【要删除的目标节点cur为黑色的叶子节点】的if分支中，也就是位于上文所说的第一种情况的1.2中，这样不管cur是否存在孩子节点，每次循环都无脑按照cur是黑色叶子节点的情况进行处理）。

既然此时要当作cur指针指向的黑色节点是没有孩子节点的，那也就是说要“删除”的cur节点是黑色的叶子节点，而这种情况又是最上面讲解的第一种情况的1.2，所以要“删除”cur节点就回到了最上面判断当前情况是第一种情况的1.2的情形1还是情形2，然后根据具体的分类进行对应的处理，而正是因为“删除”cur节点会经过这些各自分类的对应的处理，所以才能通过“删除”cur节点来控制平衡。这里我想表达的意思就是说：通过“删除”cur节点来控制平衡，就是通过cur和curBroher还有其他等等节点的状态判断当前情况是哪种分类，然后根据各自分类的处理方法去变色或者旋转，只是最后不delete删除cur节点，以此达到控制平衡的作用（能控制平衡的原因在下一段）。如何通过代码做到这一点呢？可以设置一个flag标志，在删除真正要删除的目标节点cur节点后，就将标志位flag设置成1，后序在while循环中cur指针向上走控制平衡时，根据cur和curBroher还有其他等等节点的状态进入对应的情况的if分支后，如果发现flag==1，就不delete cur，而只做对应情况的变色或者旋转处理。

那凭什么经过这些各自分类的对应的处理后，就能控制平衡呢？答案：在2.1.1.4.2，也就是本种情况的第一段中就说过，真正要删除的目标节点cur被删除后，会导致有一些路径上的黑色节点数量少1，导致不同路径上的黑色节点数量不同，就会破坏红黑树的性质3，所以需要cur指针向上走进行调整，控制平衡，而控制平衡的办法无非就两种，如下。

其一，要么让黑色节点数量少了1的路径再加1，以此让所有路径上黑色节点数量相同。比如观察上面除2.1.1.4.2之外的几种情况的处理流程图可以发现经过这些各自分类的对应的处理后，如果最后真的delete删除cur节点，对比删除cur前和删除cur后的状态，每条路径上的黑色节点数量是不变的，但注意，cur指针向上走控制平衡的过程中最后是不delete删除cur节点的，这会导致经过cur节点到NIL节点的路径上的黑色节点数量+1，而经过cur节点到NIL节点的这些路径刚好就是【在第一次向上调整前】的黑色节点数量少了1的路径，所以最后这些少了1的路径经过+1后，黑色节点的数量就不变，那所有路径上的黑色节点的数量就都重新变得相等了，也就恢复的平衡性。

其二，要么让其他黑色节点数量不变的路径上的黑色节点也跟着少1，以此让所有路径上黑色节点数量相同。比如观察上面2.1.1.4.2的流程图可以发现，如果是在cur向上调整的过程中，只把curBrother的颜色染红，但最后不delete cur，就会让【在cur第一次向上调整前】的黑色节点数量少了1的路径上的黑色节点数量不变，而会让其他黑色节点数量不变的路径上的黑色节点也少1，那所有路径上的黑色节点的数量就都重新变得相等了，也就恢复的平衡性。

————分割线————

最后还有一点很重要，这也是一个在向上调整时需要遵守的守则：既然上文中说在cur指针向上走控制平衡的过程中，即使cur这个黑色节点有孩子节点，我们也要当作cur指针指向的黑色节点是没有孩子节点的，那如果在向上调整时发现curBrother节点为黑色（这是前提条件），则不管curBrother节点是否有黑色子节点，我们也都要当作curBrother节点是不存在黑色子节点的（该守则存在的原因在下面），举几个例子：

（注意并没有穷举完，因为不需要，这里只是助于理解）

如果curBrother节点的左孩子是黑色，右孩子是红色，则我们要当作是左孩子空，右孩子红；

如果curBrother节点的左孩子黑，右孩子黑，则我们要当作是左孩子空，右孩子空；

如果curBrother节点的左孩子红，右孩子红，则我们要当作是左孩子红，右孩子红；

如果curBrother节点的左孩子空，右孩子红，则我们要当作是左孩子空，右孩子红；

（注意不存在curBrother节点的【左孩子空，右孩子黑】或者【左孩子黑，右孩子空】的情况，这种情况下不同路径上的黑色节点数量不相等，就不符合红黑树的性质3了）

该守则存在的原因其实也容易想到，毕竟我们要当作cur节点是没有孩子的黑色节点，如果在curBrother节点真有黑色子节点的情况下，我们还认为curBrother节点有黑色子节点，那不同路径上的黑色节点数量就不相同，就不符合红黑树的性质3了。这个守则体现在代码上就是：让curBrother节点在没有孩子节点时和有两个黑色子节点（一定注意没有红色子节点）时进入同一个if分支。让curBrother节点在【左孩子黑、右孩子红】时和【左孩子空、右孩子红】时走同一个if分支。让curBrother节点在【左孩子红、右孩子黑】时和【左孩子红、右孩子空】时走同一个if分支。

2.1.2：如果cur的兄弟节点curBrother是红色节点（说一下，当前情况cur节点是黑色，则curBrother节点是一定存在的，并且如果此时curBrother节点是红色，则curBrother节点一定有左右子节点且都是黑色，否则会导致每条路径上的黑色节点的数量不同，则就不符合红黑树的性质3）。当前处理方式如下图所示。

2.2：如果cur是curParent的右孩子。

2.2.1：如果cur的兄弟节点curBrother是黑色节点（说一下，当前情况cur是黑色节点，则curBrother节点是一定存在的，因为如果此时curBrother节点不存在，则会导致每条路径上的黑色节点数量不同，则不符合红黑树的性质3）

2.2.1.1：如果curBrother只有左孩子节点，则左孩子一定是红色节点，并且左孩子节点没有子树（否则不满足红黑树的性质），处理方式如下图。

2.2.1.2：如果curBrother只有右孩子节点，则右孩子一定是红色节点，并且右孩子节点没有子树（否则不满足红黑树的性质），处理方式如下图。

2.2.1.3：如果curBrother既有左孩子节点，又有右孩子节点，则左右孩子都一定是红色节点，并且左右孩子节点都没有子树（否则不满足红黑树的性质），此时处理方式可以完全按照2.2.1.1，也可以完全按照2.2.1.2，可以看到2.2.1.1只需要旋转一次，效率更高，所以本种情况的处理方式完全复用2.2.1.1即可，体现在代码上就是走同一个if分支。

2.2.1.4：如果curBrother没有孩子节点，此时就要根据curParent节点的颜色分类。

2.2.1.4.1：如果curParent是红色节点，处理方式如下图。

2.2.1.4.2：如果curParent是黑色节点，则处理方式为：把curBrother染红后直接删除cur节点，如下图。做完这些后，此时从curParent节点到所有NIL节点的所有路径上的黑色节点数量都少了1，这会导致curParent的所有祖先节点到NIL节点的不同路径上的黑色节点数量不同，就会破坏红黑树的性质3，所以需要cur往上迭代调整一次控制平，向上迭代调整的细节已经在上文中全部说过了，这里不再赘述。

2.2.2：如果cur的兄弟节点curBrother是红色节点（说一下，当前情况cur节点是黑色，则curBrother节点是一定存在的，并且如果此时curBrother节点是红色，则curBrother节点一定有左右子节点且都是黑色，否则会导致每条路径上的黑色节点的数量不同，则就不符合红黑树的性质3）。当前处理方式如下图所示。

以上就是红黑树的删除的所有情况的分类，接下来直接给出Erase的代码。

Erase的整体代码

#pragma once#include<iostream>#include<vector>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x, color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree<T>():_root(nullptr){}bool Erase(const T& x){if (_root == nullptr){cout << "树中已经不存在节点了，无法继续删除" << endl;return false;}Node* cur = _root;Node* curParent = cur->_parent;while (cur != nullptr){if (x < cur->_data){curParent = cur;cur = cur->_left;}else if (x > cur->_data){curParent = cur;cur = cur->_right;}//找到了要删除的目标节点，开始删除else{//第一种情况，如果目标节点没有孩子节点if (cur->_left == nullptr && cur->_right == nullptr){//对应文中的1.1 —— 如果删除的节点是红色叶子节点if (cur->_col == red){if (cur == curParent->_left)curParent->_left = nullptr;//删除cur前，记得断开curParent与cur的连接关系elsecurParent->_right = nullptr;//删除cur前，记得断开curParent与cur的连接关系delete cur;return true;}//对应文中的1.2 —— 如果删除的节点是黑色，且没有孩子节点，则删除后需要调整平衡else{//情形1：要删除的目标节点cur是根节点，所以删除后无需调整平衡if (cur == _root){delete cur;_root = nullptr;return true;}// 情形2：被删除节点不是根节点，需要进行调整平衡，注意，在向上调整时，不管cur这个黑色节点的是否存在孩子节点，我们都把cur当作没有孩子节点int flag = 0;//用于在向上迭代调整的时候，控制不要把cur删除while (cur != _root){//情形2.2：如果cur是curParent的右孩子if (cur == curParent->_right){Node* curBrother = curParent->_left;//无需判空，因为cur不是根节点，所以curParent一定不为空//情形2.2.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.2.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//情形2.2.1.3：说明一下，如果兄弟有两个红色子节点，也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curParent节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewL->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支else if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curBrother节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curBrother);RotateR(curParent);curNephewR->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4：如果cur的兄弟没有子节点走这里 //说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.2.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把他删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}//情形2.2.2：如果cur的兄弟curBrother是红色节点，则说明curBrother一定有左右孩子节点，并且都是黑色else{//当前情况cur是curParent的右孩子，curBrother是curParent的左孩子，所以直接对curParent右单旋RotateR(curParent);swap(curBrother->_col, curParent->_col);//旋转完毕后，关系可能会乱，所以更新curBrother与curParent指针的指向,这里我们根据示例图可以知道只有curBrother指针需要更新curBrother = curParent->_left;//走到这里，情况会转换成2.2.1：cur和curBrother都是黑色节点，此时直接拷贝上面2.2.1的代码//情形2.2.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.2.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//情形2.2.1.3：说明一下，如果兄弟有两个红色子节点，也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curParent节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewL->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支else if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curBrother节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curBrother);RotateR(curParent);curNephewR->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4：如果cur的兄弟没有子节点走这里 //说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.2.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把他删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}}}//情形2.1：如果cur是curParent的左孩子else{Node* curBrother = curParent->_right;//无需判空，因为cur不是根节点，所以curParent一定不为空//情形2.1.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.1.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//情形2.1.1.3：如果兄弟有两个红色子节点，我们也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curParent节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewR->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支else if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curBrother节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curBrother);RotateL(curParent);curNephewL->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4：如果cur的兄弟没有子节点走这里//说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.1.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把cur删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}//情形2.1.2：如果cur的兄弟是红色节点else{//当前情况cur是curParent的左孩子，所以curBrother一定是curParent的右孩子，所以直接对curParent左单旋RotateL(curParent);swap(curBrother->_col, curParent->_col);//旋转完毕后，关系可能会乱，所以更新curBrother与curParent指针的指向,这里我们根据示例图可以知道只有curBrother指针需要更新curBrother = curParent->_right;//走到这里，情况会转换成2.1.1：cur和curBrother都是黑色节点，此时直接拷贝上面2.1.1的代码//情形2.1.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.1.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//情形2.1.1.3：如果兄弟有两个红色子节点，我们也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curParent节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewR->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支else if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curBrother节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curBrother);RotateL(curParent);curNephewL->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4：如果cur的兄弟没有子节点走这里//说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.1.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把cur删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}}}}//走到这里,即走出了用于向上调整的循环，说明是向上调整到了根节点，此时直接return true即可return true;}}//第二种情况，如果目标节点只有左孩子else if (cur->_left != nullptr && cur->_right == nullptr){if (cur == _root){_root = cur->_left;_root->_parent = nullptr;//不要忘了修改新根节点的parent指针的指向_root->_col = black;//如果要删除的目标节点是整棵树的根节点，并且还只有左孩子，则说明左孩子一定为红，此时一定不要忘了的修改新根节点的颜色，把他从红色变成黑色delete cur;return true;}else{if (cur == curParent->_left){curParent->_left = cur->_left;cur->_left->_parent = curParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}else{curParent->_right = cur->_left;cur->_left->_parent = curParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}cur->_left->_col = black;delete cur;return true;}}//第三种情况，如果目标节点只有右孩子else if (cur->_left == nullptr && cur->_right != nullptr){if (cur == _root){_root = cur->_right;_root->_parent = nullptr;//不要忘了修改新根节点的parent指针的指向_root->_col = black;//如果要删除的目标节点是整棵树的根节点，并且还只有右孩子，则说明右孩子一定为红，此时一定不要忘了的修改新根节点的颜色，把他从红色变成黑色delete cur;return true;}else{if (cur == curParent->_left){curParent->_left = cur->_right;cur->_right->_parent = curParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}else{curParent->_right = cur->_right;cur->_right->_parent = curParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}cur->_right->_col = black;delete cur;return true;}}//第四种情况，如果目标节点既有左孩子，又有右孩子else if (cur->_left != nullptr && cur->_right != nullptr){Node* Rmin = cur->_right;Node* RminParent = cur;while (Rmin->_left != nullptr){RminParent = Rmin;Rmin = Rmin->_left;}cur->_data = Rmin->_data;//走到这里，替死鬼节点Rmin就被找到了,Rmin只有两种可能，第一：只有右孩子，第二：没有孩子节点//如果只有右孩子,则套用上面的第三种情况的思路即可。if (Rmin->_right != nullptr){//注意Rmin不可能是整棵树的根节点，所以不必一板一眼的套用第三种情况的思路if (Rmin == RminParent->_left){RminParent->_left = Rmin->_right;Rmin->_right->_parent = RminParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}else{RminParent->_right = Rmin->_right;Rmin->_right->_parent = RminParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}Rmin->_right->_col = black;delete Rmin;return true;}//替死鬼节点Rmin没有孩子节点,此时直接套用第一种情况的思路即可，但注意，因为第一种情况的代码量太大了，这里我们就不套用思路了，而是直接拷贝第一种情况的代码else{//先把Rmin和RminParent指针的值赋给cur与curParent，这样我们就可以直接拷贝第一种情况的代码并复用了cur = Rmin;curParent = RminParent;//以下所有代码都是拷贝的第一种情况的代码//对应文中的1.1 —— 如果删除的节点是红色叶子节点if (cur->_col == red){if (cur == curParent->_left)curParent->_left = nullptr;//删除cur前，记得断开curParent与cur的连接关系elsecurParent->_right = nullptr;//删除cur前，记得断开curParent与cur的连接关系delete cur;return true;}//对应文中的1.2 —— 如果删除的节点是黑色，且没有孩子节点，则删除后需要调整平衡else{//情形1：要删除的目标节点cur是根节点，所以删除后无需调整平衡if (cur == _root){delete cur;_root = nullptr;return true;}// 情形2：被删除节点不是根节点，需要进行调整平衡，注意，在向上调整时，不管cur这个黑色节点的是否存在孩子节点，我们都把cur当作没有孩子节点int flag = 0;//用于在向上迭代调整的时候，控制不要把cur删除while (cur != _root){//情形2.2：如果cur是curParent的右孩子if (cur == curParent->_right){Node* curBrother = curParent->_left;//无需判空，因为cur不是根节点，所以curParent一定不为空//情形2.2.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.2.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//情形2.2.1.3：说明一下，如果兄弟有两个红色子节点，也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curParent节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewL->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支else if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curBrother节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curBrother);RotateR(curParent);curNephewR->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4：如果cur的兄弟没有子节点走这里 //说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.2.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把他删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}//情形2.2.2：如果cur的兄弟curBrother是红色节点，则说明curBrother一定有左右孩子节点，并且都是黑色else{//当前情况cur是curParent的右孩子，curBrother是curParent的左孩子，所以直接对curParent右单旋RotateR(curParent);swap(curBrother->_col, curParent->_col);//旋转完毕后，关系可能会乱，所以更新curBrother与curParent指针的指向,这里我们根据示例图可以知道只有curBrother指针需要更新curBrother = curParent->_left;//走到这里，情况会转换成2.2.1：cur和curBrother都是黑色节点，此时直接拷贝上面2.2.1的代码//情形2.2.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.2.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//情形2.2.1.3：说明一下，如果兄弟有两个红色子节点，也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curParent节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewL->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支else if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curBrother节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curBrother);RotateR(curParent);curNephewR->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4：如果cur的兄弟没有子节点走这里 //说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.2.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把他删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}}}//情形2.1：如果cur是curParent的左孩子else{Node* curBrother = curParent->_right;//无需判空，因为cur不是根节点，所以curParent一定不为空//情形2.1.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.1.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//情形2.1.1.3：如果兄弟有两个红色子节点，我们也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curParent节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewR->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支else if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curBrother节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curBrother);RotateL(curParent);curNephewL->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4：如果cur的兄弟没有子节点走这里//说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.1.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把cur删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}//情形2.1.2：如果cur的兄弟是红色节点else{//当前情况cur是curParent的左孩子，所以curBrother一定是curParent的右孩子，所以直接对curParent左单旋RotateL(curParent);swap(curBrother->_col, curParent->_col);//旋转完毕后，关系可能会乱，所以更新curBrother与curParent指针的指向,这里我们根据示例图可以知道只有curBrother指针需要更新curBrother = curParent->_right;//走到这里，情况会转换成2.1.1：cur和curBrother都是黑色节点，此时直接拷贝上面2.1.1的代码//情形2.1.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.1.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//情形2.1.1.3：如果兄弟有两个红色子节点，我们也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curParent节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewR->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支else if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curBrother节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curBrother);RotateL(curParent);curNephewL->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4：如果cur的兄弟没有子节点走这里//说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.1.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把cur删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}}}}//走到这里,即走出了用于向上调整的循环，说明是向上调整到了根节点，此时直接return true即可return true;}}}}}//没有在树中找到目标节点，说明目标节点不存在，直接return falsecout << "你要删除的节点不存在" << endl;return false;}private:void RotateR(Node* p){if (p != _root){Node* subL = p->_left;Node* subLR = subL->_right;Node* p_parent = p->_parent;subL->_right = p;subL->_parent = p_parent;if (p == p_parent->_right)p_parent->_right = subL;elsep_parent->_left = subL;p->_left = subLR;p->_parent = subL;if (subLR != nullptr)subLR->_parent = p;}else{Node* subL = p->_left;Node* subLR = subL->_right;_root = subL;subL->_right = p;subL->_parent = nullptr;p->_left = subLR;p->_parent = subL;if (subLR != nullptr)subLR->_parent = p;}}void RotateL(Node* p){if (_root != p){Node* subR = p->_right;Node* subRL = subR->_left;Node* p_parent = p->_parent;subR->_left = p;subR->_parent = p_parent;p->_parent = subR;p->_right = subRL;if (p == p_parent->_right)p_parent->_right = subR;elsep_parent->_left = subR;if (subRL != nullptr)subRL->_parent = p;}else{Node* subR = p->_right;Node* subRL = subR->_left;_root = subR;subR->_left = p;subR->_parent = nullptr;p->_right = subRL;p->_parent = subR;if (subRL != nullptr)subRL->_parent = p;}}private:Node* _root;};

Erase的测试

在上文中编写完检测一棵树是否为红黑树的函数后，通过该函数就可以检测出咱们实现的Erase函数是否存在问题，比如下图示例中我们生成了2w个随机数插进红黑树，然后再依次从红黑树中将这2w个数字一个个删除，每删除一个后都检测平衡性。可以看到打印出来的结果是符合我们的预期的，说一下，黑框中出现了【你要删除的节点不存在】和【树中已经不存在节点了，无法继续删除】，这是因为rand函数可能会生成重复的值，但我们知道红黑树是二叉搜索树的一种，天生支持排序和去重，所以在插入重复值时只会插入成功一次，所以在删除时如果多次删除同一个值，就会出现了【你要删除的节点不存在】的情况，而出现【树中已经不存在节点了，无法继续删除】的原因也是类似的道理，说明rand生成的具有重复值的数字不止1个，比如生成了1、1、1、2、2....，有1和2这两个具有重复值的数字。

上图的代码如下。

#include"RBTree.h"void test4(){srand(time(0));RBTree<int>t1;int a[20000];for (int i = 0; i < 20000; i++){a[i] = rand();}for (int i = 0; i < (sizeof(a) / sizeof(int)); i++){t1.Insert(a[i]);}cout << "（1表示平衡，0表示不平衡）插入结束后平衡性是：" << t1.isbalance() << endl;cout << "——开始删除——" << endl;for (int i = 0; i < (sizeof(a) / sizeof(int)); i++){cout << "现在循环的次数的是:" <<i<< " 现在删除的是:" << a[i] << endl;t1.Erase(a[i]);cout << "平衡性是：" << t1.isbalance() << endl;}cout << "——所有节点删除完毕——" << endl;cout << "平衡性是：" << t1.isbalance() << endl;}void main(){test4();}

红黑树的迭代器

实现过程

RBTree类的begin()等接口、RBTreeIterator类的operator*()等接口

红黑树的迭代器本质上和链表一样，就是对节点的指针变量的一层封装，所以红黑树的迭代器只有一个Node*的指针成员。begin()返回的迭代器指向整棵树的最左节点，也就是值最小的节点，end()返回的迭代器指向空，即end()返回的迭代器的成员Node* _n是nullptr。

先写一些比较简单的接口，就不再说明，直接上代码，如下。注意为什么RBTreeIterator有两个模板参数T1、T2呢？直接一个T不行吗？答案是不行，原因在下面代码的const_iterator begin()const这个接口的注释中。

template<class T1,class T2>struct RBTreeIterator{typedef RBTreeNode<T1> Node;RBTreeIterator():_n(nullptr){}RBTreeIterator(Node* n):_n(n){}T2& operator*(){return (*_n)._data;}T2* operator->(){return &((*_n)._data);}bool operator==(const RBTreeIterator it)const //加const是为了让被const iterator也能调用该接口，注意区分const iterator和const_iterator，前者不是const迭代器{return _n == it._n;}bool operator!=(const RBTreeIterator it)const //加const是为了让被const iterator也能调用该接口，注意区分const iterator和const_iterator，前者不是const迭代器{return !(operator==(it));}Node* _n;};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T,T> iterator;typedef RBTreeIterator<T,const T> const_iterator;RBTree<T>():_root(nullptr){}iterator begin(){if (_root == nullptr)return iterator(nullptr);else{Node* cur = _root;while (cur->_left != nullptr)cur = cur->_left;return iterator(cur);}}const_iterator begin()const{if (_root == nullptr)return const_iterator(nullptr);else{Node* cur = _root;while (cur->_left != nullptr)cur = cur->_left;return const_iterator(cur);//为什么RBTreeIterator<T1,T2>有两个模板参数T1、T2呢？//如果RBTreeIterator<T>只有一个模板参数T，本行代码就会出问题，无法通过cur构造const_iterator。因为在当前begin函数中，cur的类型是RBTreeNode<T>*，//而在const_iterator类中，即RBTreeIterator<const T>类中，const_iterator类的构造函数，即RBTreeIterator<const T>类的构造函数的参数的类型则是RBTreeNode<const T>*，//因为cur的类型RBTreeNode<T>* 和const_iterator的构造函数的参数的类型RBTreeNode<const T>*不同，所以构造函数就会出现问题，所以RBTreeIterator<T>只有一个模板参数T是不行的。 }}iterator end(){return iterator(nullptr);}const_iterator end()const{return const_iterator(nullptr);}private:Node* _root;};

前置和后置的operator++和operator--接口

比较复杂的接口就是前置和后置的operator++和operator--，如何实现呢？

先说说operator++的思路。迭代器是用于遍历容器的，对于红黑树这样的容器来说，只有中序遍历才最有意义，因为这样遍历到的数据是有序的，是升序（当然如果对红黑树的Insert和Erase作改造，比如在Insert时让节点小的往右子树插入，让节点大的往左子树插入，这样在中序遍历时也能实现降序），所以operator++就应该按照中序遍历的逻辑去实现。问题来了，正常的中序遍历是通过递归的思路来实现的，并且是把整棵树都遍历完，但operator++只需要往后遍历一个数据，所以通过递归的思路就不太好解决，所以咱们的中序遍历需要通过非递归的写法实现。

在<<二叉树的非递归遍历>>一文中说过，二叉树的中序遍历的非递归写法需要借助stack栈这样的容器找到当前节点的祖先节点，那在编写operator++时，需不需要借助stack呢？答案是不用，因为RBTree是三叉链，天生就支持找到某个祖先节点。

中序遍历访问下一个节点的思路，或者说前后置的operato++的思路为：（结合下图思考）既然在中序遍历下需要operato++了，则说明当前节点的左子树以及当前节点已经被访问过了。

1，如果当前节点存在右子树，则operato++就是要找到右子树中最左节点，即值最小的节点（这就是搜索树在删除【存在左右孩子节点的节点】时找替死鬼节点的方法）。

2，如果当前节点没有右子树，则说明以当前节点为根节点的子树已经被访问完毕了，则operato++就是要找一个祖先节点，哪个祖先节点呢？从当前节点开始向上，到整棵树的根节点结束，如果当前节点在第一个遇到的祖先节点的左子树中，则该祖先节点就是operato++要找的节点，举个例子，如果当前节点是下图的6，则operator++时，因为6没有右子树，说明以6为根节点的子树已经被访问完毕了，则operato++就是要找一个祖先节点，6在1的右子树中，所以1不是该祖先节点，6在8的左子树中，所以8就是要找的该祖先节点。

结合上面理论，编写前后置的operato++的代码如下。

template<class T1,class T2>struct RBTreeIterator{typedef RBTreeNode<T1> Node;RBTreeIterator():_n(nullptr){}RBTreeIterator(Node* n):_n(n){}RBTreeIterator operator++()//前置++{if (_n->_right == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_left){_n = curParent;return (*this);//this指针的类型是RBTreeIterator<T>*, this指针的值是调用operator++接口的迭代器对象的地址}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return (*this);}else{Node* Rmin = _n->_right;while (Rmin->_left != nullptr){Rmin = Rmin->_left;}_n = Rmin;return (*this);}}RBTreeIterator operator++(int)//后置++{Node* temp = _n;if (_n->_right == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_left){_n = curParent;return RBTreeIterator(temp);}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了,直接return_n = nullptr;return RBTreeIterator(temp);}else{Node* Rmin = _n->_right;while (Rmin->_left != nullptr){Rmin = Rmin->_left;}_n = Rmin;return RBTreeIterator(temp);}}Node* _n;};

至于前后置的operator-- 的思路，和operator++是完全一样的，只不过方向相反，如下。

（结合下图思考）1，如果当前节点存在左子树，则operato--就是要找到左子树中最右节点，即值最大的节点（这就是搜索树在删除【存在左右孩子节点的节点】时找替死鬼节点的方法）。

（结合下图思考）2，如果当前节点没有左子树，则operato--就是要找一个祖先节点，哪个祖先节点呢？从当前节点开始向上，到整棵树的根节点结束，如果当前节点在第一个遇到的祖先节点的右子树中，则该祖先节点就是operato--要找的节点，举个例子，如果当前节点是下图的6，则operator--时，因为6没有左子树，则operato--就是要找一个祖先节点，6在1的右子树中，所以1就是该祖先节点；再举个例子，如果当前节点是下图的1，1在8的左子树中，所以8不是要找的该祖先节点，1在13的左子树中，所以13也不是该祖先节点，因为已经找到整棵树的根节点13上来了，无法再继续向上找1的祖先节点了，到这时都没找到目标祖先节点，说明节点1是begin()，operator--直接返回一个iterator（nullptr）即可。

结合上面思路，前后置的operator-- 的代码如下。

template<class T1,class T2>struct RBTreeIterator{typedef RBTreeNode<T1> Node;RBTreeIterator():_n(nullptr){}RBTreeIterator(Node* n):_n(n){}RBTreeIterator operator--()//前置--{if (_n->_left == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_right){_n = curParent;return (*this);//this指针的类型是RBTreeIterator<T>*, this指针的值是调用operator++接口的迭代器对象的地址}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return (*this);}else{Node* Lmax = _n->_left;while (Lmax->_right != nullptr){Lmax = Lmax->_right;}_n = Lmax;return (*this);}}RBTreeIterator operator--(int)//后置--{Node* temp = _n;if (_n->_left == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_right){_n = curParent;return RBTreeIterator(temp);}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return RBTreeIterator(temp);}else{Node* Lmax = _n->_left;while (Lmax->_right != nullptr){Lmax = Lmax->_right;}_n = Lmax;return RBTreeIterator(temp);}}Node* _n;};

迭代器的整体代码

template<class T1,class T2>struct RBTreeIterator{typedef RBTreeNode<T1> Node;RBTreeIterator():_n(nullptr){}RBTreeIterator(Node* n):_n(n){}T2& operator*(){return (*_n)._data;}T2* operator->(){return &((*_n)._data);}bool operator==(const RBTreeIterator it)const //加const是为了让被const iterator也能调用该接口，注意区分const iterator和const_iterator，前者不是const迭代器{return _n == it._n;}bool operator!=(const RBTreeIterator it)const //加const是为了让被const iterator也能调用该接口，注意区分const iterator和const_iterator，前者不是const迭代器{return !(operator==(it));}RBTreeIterator operator++()//前置++{if (_n->_right == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_left){_n = curParent;return (*this);//this指针的类型是RBTreeIterator<T>*, this指针的值是调用operator++接口的迭代器对象的地址}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return (*this);}else{Node* Rmin = _n->_right;while (Rmin->_left != nullptr){Rmin = Rmin->_left;}_n = Rmin;return (*this);}}RBTreeIterator operator++(int)//后置++{Node* temp = _n;if (_n->_right == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_left){_n = curParent;return RBTreeIterator(temp);}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了,直接return_n = nullptr;return RBTreeIterator(temp);}else{Node* Rmin = _n->_right;while (Rmin->_left != nullptr){Rmin = Rmin->_left;}_n = Rmin;return RBTreeIterator(temp);}}RBTreeIterator operator--()//前置--{if (_n->_left == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_right){_n = curParent;return (*this);//this指针的类型是RBTreeIterator<T>*, this指针的值是调用operator++接口的迭代器对象的地址}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return (*this);}else{Node* Lmax = _n->_left;while (Lmax->_right != nullptr){Lmax = Lmax->_right;}_n = Lmax;return (*this);}}RBTreeIterator operator--(int)//后置--{Node* temp = _n;if (_n->_left == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_right){_n = curParent;return RBTreeIterator(temp);}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return RBTreeIterator(temp);}else{Node* Lmax = _n->_left;while (Lmax->_right != nullptr){Lmax = Lmax->_right;}_n = Lmax;return RBTreeIterator(temp);}}Node* _n;};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T,T> iterator;typedef RBTreeIterator<T,const T> const_iterator;RBTree<T>():_root(nullptr){}iterator begin(){if (_root == nullptr)return iterator(nullptr);else{Node* cur = _root;while (cur->_left != nullptr)cur = cur->_left;return iterator(cur);}}const_iterator begin()const{if (_root == nullptr)return const_iterator(nullptr);else{Node* cur = _root;while (cur->_left != nullptr)cur = cur->_left;return const_iterator(cur);//为什么RBTreeIterator<T1,T2>有两个模板参数T1、T2呢？//如果RBTreeIterator<T>只有一个模板参数T，本行代码就会出问题，无法通过cur构造const_iterator。因为在当前begin函数中，cur的类型是RBTreeNode<T>*，//而在const_iterator类中，即RBTreeIterator<const T>类中，const_iterator类的构造函数，即RBTreeIterator<const T>类的构造函数的参数的类型则是RBTreeNode<const T>*，//因为cur的类型RBTreeNode<T>* 和const_iterator的构造函数的参数的类型RBTreeNode<const T>*不同，所以构造函数就会出现问题，所以RBTreeIterator<T>只有一个模板参数T是不行的。 }}iterator end(){return iterator(nullptr);}const_iterator end()const{return const_iterator(nullptr);}private:Node* _root;};

迭代器的测试

测试代码如下图，可以发现是符合预期的。

上图中的代码如下。

//#include"Set.h";//#include"Map.h";//#include<map>;#include"RBT.h";void main(){RBTree<int>r;r.Insert(1);r.Insert(4);r.Insert(2);r.Insert(3);for (RBTree<int>::iterator it = r.begin(); it != r.end(); it++){cout << *it << ' ';}cout << endl;RBTree<int>::iterator it = r.begin(); (++it);(++it);(++it);for (; it != --r.begin(); it--){cout << *it << ' ';}cout << endl;const RBTree<int>r1(r);for (RBTree<int>::const_iterator it = r1.begin(); it != r1.end(); ++it){cout << *it << ' ';}cout << endl;}

红黑树的整体代码

RBTree.h如下。

#pragma once#include<iostream>using namespace std;enum color{red,black};template<class T>class RBTreeNode{public:T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _col;RBTreeNode():_data(), _left(nullptr), _right(nullptr), _parent(nullptr), _col(){}RBTreeNode(const T& x, color col):_data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}};template<class T1,class T2>struct RBTreeIterator{typedef RBTreeNode<T1> Node;RBTreeIterator():_n(nullptr){}RBTreeIterator(Node* n):_n(n){}T2& operator*(){return (*_n)._data;}T2* operator->(){return &((*_n)._data);}bool operator==(const RBTreeIterator it)const //加const是为了让被const iterator也能调用该接口，注意区分const iterator和const_iterator，前者不是const迭代器{return _n == it._n;}bool operator!=(const RBTreeIterator it)const //加const是为了让被const iterator也能调用该接口，注意区分const iterator和const_iterator，前者不是const迭代器{return !(operator==(it));}RBTreeIterator operator++()//前置++{if (_n->_right == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_left){_n = curParent;return (*this);//this指针的类型是RBTreeIterator<T>*, this指针的值是调用operator++接口的迭代器对象的地址}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return (*this);}else{Node* Rmin = _n->_right;while (Rmin->_left != nullptr){Rmin = Rmin->_left;}_n = Rmin;return (*this);}}RBTreeIterator operator++(int)//后置++{Node* temp = _n;if (_n->_right == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_left){_n = curParent;return RBTreeIterator(temp);}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了,直接return_n = nullptr;return RBTreeIterator(temp);}else{Node* Rmin = _n->_right;while (Rmin->_left != nullptr){Rmin = Rmin->_left;}_n = Rmin;return RBTreeIterator(temp);}}RBTreeIterator operator--()//前置--{if (_n->_left == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_right){_n = curParent;return (*this);//this指针的类型是RBTreeIterator<T>*, this指针的值是调用operator++接口的迭代器对象的地址}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return (*this);}else{Node* Lmax = _n->_left;while (Lmax->_right != nullptr){Lmax = Lmax->_right;}_n = Lmax;return (*this);}}RBTreeIterator operator--(int)//后置--{Node* temp = _n;if (_n->_left == nullptr){Node* cur = _n;Node* curParent = _n->_parent;while (curParent != nullptr)//这里本来是cur!=_root的，但_root在RBTree类中，访问不到，所以用了curParent!=nullptr替代{if (cur == curParent->_right){_n = curParent;return RBTreeIterator(temp);}else{cur = curParent;curParent = curParent->_parent;}}//如果出了while循环，说明cur走到了根节点，此时说明整棵树就已经遍历完毕了，直接return 一个【和end()函数返回的迭代器指向相同的】迭代器_n = nullptr;return RBTreeIterator(temp);}else{Node* Lmax = _n->_left;while (Lmax->_right != nullptr){Lmax = Lmax->_right;}_n = Lmax;return RBTreeIterator(temp);}}Node* _n;};template<class T>class RBTree{typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T,T> iterator;typedef RBTreeIterator<T,const T> const_iterator;RBTree<T>():_root(nullptr){}iterator begin(){if (_root == nullptr)return iterator(nullptr);else{Node* cur = _root;while (cur->_left != nullptr)cur = cur->_left;return iterator(cur);}}const_iterator begin()const{if (_root == nullptr)return const_iterator(nullptr);else{Node* cur = _root;while (cur->_left != nullptr)cur = cur->_left;return const_iterator(cur);//为什么RBTreeIterator<T1,T2>有两个模板参数T1、T2呢？//如果RBTreeIterator<T>只有一个模板参数T，本行代码就会出问题，无法通过cur构造const_iterator。因为在当前begin函数中，cur的类型是RBTreeNode<T>*，//而在const_iterator类中，即RBTreeIterator<const T>类中，const_iterator类的构造函数，即RBTreeIterator<const T>类的构造函数的参数的类型则是RBTreeNode<const T>*，//因为cur的类型RBTreeNode<T>* 和const_iterator的构造函数的参数的类型RBTreeNode<const T>*不同，所以构造函数就会出现问题，所以RBTreeIterator<T>只有一个模板参数T是不行的。 }}iterator end(){return iterator(nullptr);}const_iterator end()const{return const_iterator(nullptr);}bool Erase(const T& x){if (_root == nullptr){cout << "树中已经不存在节点了，无法继续删除" << endl;return false;}Node* cur = _root;Node* curParent = cur->_parent;while (cur != nullptr){if (x < cur->_data){curParent = cur;cur = cur->_left;}else if (x > cur->_data){curParent = cur;cur = cur->_right;}//找到了要删除的目标节点，开始删除else{//第一种情况，如果目标节点没有孩子节点if (cur->_left == nullptr && cur->_right == nullptr){//对应文中的1.1 —— 如果删除的节点是红色叶子节点if (cur->_col == red){if (cur == curParent->_left)curParent->_left = nullptr;//删除cur前，记得断开curParent与cur的连接关系elsecurParent->_right = nullptr;//删除cur前，记得断开curParent与cur的连接关系delete cur;return true;}//对应文中的1.2 —— 如果删除的节点是黑色，且没有孩子节点，则删除后需要调整平衡else{//情形1：要删除的目标节点cur是根节点，所以删除后无需调整平衡if (cur == _root){delete cur;_root = nullptr;return true;}// 情形2：被删除节点不是根节点，需要进行调整平衡，注意，在向上调整时，不管cur这个黑色节点的是否存在孩子节点，我们都把cur当作没有孩子节点int flag = 0;//用于在向上迭代调整的时候，控制不要把cur删除while (cur != _root){//情形2.2：如果cur是curParent的右孩子if (cur == curParent->_right){Node* curBrother = curParent->_left;//无需判空，因为cur不是根节点，所以curParent一定不为空//情形2.2.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.2.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//情形2.2.1.3：说明一下，如果兄弟有两个红色子节点，也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curParent节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewL->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支else if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curBrother节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curBrother);RotateR(curParent);curNephewR->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4：如果cur的兄弟没有子节点走这里 //说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.2.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把他删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}//情形2.2.2：如果cur的兄弟curBrother是红色节点，则说明curBrother一定有左右孩子节点，并且都是黑色else{//当前情况cur是curParent的右孩子，curBrother是curParent的左孩子，所以直接对curParent右单旋RotateR(curParent);swap(curBrother->_col, curParent->_col);//旋转完毕后，关系可能会乱，所以更新curBrother与curParent指针的指向,这里我们根据示例图可以知道只有curBrother指针需要更新curBrother = curParent->_left;//走到这里，情况会转换成2.2.1：cur和curBrother都是黑色节点，此时直接拷贝上面2.2.1的代码//情形2.2.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.2.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//情形2.2.1.3：说明一下，如果兄弟有两个红色子节点，也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curParent节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewL->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支else if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curBrother节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curBrother);RotateR(curParent);curNephewR->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4：如果cur的兄弟没有子节点走这里 //说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.2.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把他删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}}}//情形2.1：如果cur是curParent的左孩子else{Node* curBrother = curParent->_right;//无需判空，因为cur不是根节点，所以curParent一定不为空//情形2.1.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.1.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//情形2.1.1.3：如果兄弟有两个红色子节点，我们也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curParent节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewR->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支else if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curBrother节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curBrother);RotateL(curParent);curNephewL->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4：如果cur的兄弟没有子节点走这里//说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.1.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把cur删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}//情形2.1.2：如果cur的兄弟是红色节点else{//当前情况cur是curParent的左孩子，所以curBrother一定是curParent的右孩子，所以直接对curParent左单旋RotateL(curParent);swap(curBrother->_col, curParent->_col);//旋转完毕后，关系可能会乱，所以更新curBrother与curParent指针的指向,这里我们根据示例图可以知道只有curBrother指针需要更新curBrother = curParent->_right;//走到这里，情况会转换成2.1.1：cur和curBrother都是黑色节点，此时直接拷贝上面2.1.1的代码//情形2.1.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.1.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//情形2.1.1.3：如果兄弟有两个红色子节点，我们也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curParent节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewR->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支else if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curBrother节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curBrother);RotateL(curParent);curNephewL->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4：如果cur的兄弟没有子节点走这里//说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.1.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把cur删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}}}}//走到这里,即走出了用于向上调整的循环，说明是向上调整到了根节点，此时直接return true即可return true;}}//第二种情况，如果目标节点只有左孩子else if (cur->_left != nullptr && cur->_right == nullptr){if (cur == _root){_root = cur->_left;_root->_parent = nullptr;//不要忘了修改新根节点的parent指针的指向_root->_col = black;//如果要删除的目标节点是整棵树的根节点，并且还只有左孩子，则说明左孩子一定为红，此时一定不要忘了的修改新根节点的颜色，把他从红色变成黑色delete cur;return true;}else{if (cur == curParent->_left){curParent->_left = cur->_left;cur->_left->_parent = curParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}else{curParent->_right = cur->_left;cur->_left->_parent = curParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}cur->_left->_col = black;delete cur;return true;}}//第三种情况，如果目标节点只有右孩子else if (cur->_left == nullptr && cur->_right != nullptr){if (cur == _root){_root = cur->_right;_root->_parent = nullptr;//不要忘了修改新根节点的parent指针的指向_root->_col = black;//如果要删除的目标节点是整棵树的根节点，并且还只有右孩子，则说明右孩子一定为红，此时一定不要忘了的修改新根节点的颜色，把他从红色变成黑色delete cur;return true;}else{if (cur == curParent->_left){curParent->_left = cur->_right;cur->_right->_parent = curParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}else{curParent->_right = cur->_right;cur->_right->_parent = curParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}cur->_right->_col = black;delete cur;return true;}}//第四种情况，如果目标节点既有左孩子，又有右孩子else if (cur->_left != nullptr && cur->_right != nullptr){Node* Rmin = cur->_right;Node* RminParent = cur;while (Rmin->_left != nullptr){RminParent = Rmin;Rmin = Rmin->_left;}cur->_data = Rmin->_data;//走到这里，替死鬼节点Rmin就被找到了,Rmin只有两种可能，第一：只有右孩子，第二：没有孩子节点//如果只有右孩子,则套用上面的第三种情况的思路即可。if (Rmin->_right != nullptr){//注意Rmin不可能是整棵树的根节点，所以不必一板一眼的套用第三种情况的思路if (Rmin == RminParent->_left){RminParent->_left = Rmin->_right;Rmin->_right->_parent = RminParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}else{RminParent->_right = Rmin->_right;Rmin->_right->_parent = RminParent;//别忘了更新每个节点的_parent指针，这点坑死我了，调试死我了}Rmin->_right->_col = black;delete Rmin;return true;}//替死鬼节点Rmin没有孩子节点,此时直接套用第一种情况的思路即可，但注意，因为第一种情况的代码量太大了，这里我们就不套用思路了，而是直接拷贝第一种情况的代码else{//先把Rmin和RminParent指针的值赋给cur与curParent，这样我们就可以直接拷贝第一种情况的代码并复用了cur = Rmin;curParent = RminParent;//以下所有代码都是拷贝的第一种情况的代码//对应文中的1.1 —— 如果删除的节点是红色叶子节点if (cur->_col == red){if (cur == curParent->_left)curParent->_left = nullptr;//删除cur前，记得断开curParent与cur的连接关系elsecurParent->_right = nullptr;//删除cur前，记得断开curParent与cur的连接关系delete cur;return true;}//对应文中的1.2 —— 如果删除的节点是黑色，且没有孩子节点，则删除后需要调整平衡else{//情形1：要删除的目标节点cur是根节点，所以删除后无需调整平衡if (cur == _root){delete cur;_root = nullptr;return true;}// 情形2：被删除节点不是根节点，需要进行调整平衡，注意，在向上调整时，不管cur这个黑色节点的是否存在孩子节点，我们都把cur当作没有孩子节点int flag = 0;//用于在向上迭代调整的时候，控制不要把cur删除while (cur != _root){//情形2.2：如果cur是curParent的右孩子if (cur == curParent->_right){Node* curBrother = curParent->_left;//无需判空，因为cur不是根节点，所以curParent一定不为空//情形2.2.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.2.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//情形2.2.1.3：说明一下，如果兄弟有两个红色子节点，也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curParent节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewL->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支else if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curBrother节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curBrother);RotateR(curParent);curNephewR->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4：如果cur的兄弟没有子节点走这里 //说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.2.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把他删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}//情形2.2.2：如果cur的兄弟curBrother是红色节点，则说明curBrother一定有左右孩子节点，并且都是黑色else{//当前情况cur是curParent的右孩子，curBrother是curParent的左孩子，所以直接对curParent右单旋RotateR(curParent);swap(curBrother->_col, curParent->_col);//旋转完毕后，关系可能会乱，所以更新curBrother与curParent指针的指向,这里我们根据示例图可以知道只有curBrother指针需要更新curBrother = curParent->_left;//走到这里，情况会转换成2.2.1：cur和curBrother都是黑色节点，此时直接拷贝上面2.2.1的代码//情形2.2.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.2.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//情形2.2.1.3：说明一下，如果兄弟有两个红色子节点，也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curParent节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewL->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支else if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curBrother节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curBrother);RotateR(curParent);curNephewR->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4：如果cur的兄弟没有子节点走这里 //说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.2.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}return true;}//情形2.2.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_right = nullptr;//cur是curParent的右孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur不需要被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把他删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}}}//情形2.1：如果cur是curParent的左孩子else{Node* curBrother = curParent->_right;//无需判空，因为cur不是根节点，所以curParent一定不为空//情形2.1.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.1.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//情形2.1.1.3：如果兄弟有两个红色子节点，我们也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curParent节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewR->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支else if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curBrother节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curBrother);RotateL(curParent);curNephewL->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4：如果cur的兄弟没有子节点走这里//说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.1.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把cur删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}//情形2.1.2：如果cur的兄弟是红色节点else{//当前情况cur是curParent的左孩子，所以curBrother一定是curParent的右孩子，所以直接对curParent左单旋RotateL(curParent);swap(curBrother->_col, curParent->_col);//旋转完毕后，关系可能会乱，所以更新curBrother与curParent指针的指向,这里我们根据示例图可以知道只有curBrother指针需要更新curBrother = curParent->_right;//走到这里，情况会转换成2.1.1：cur和curBrother都是黑色节点，此时直接拷贝上面2.1.1的代码//情形2.1.1：如果cur的兄弟是黑色节点if (curBrother->_col == black){//情形2.1.1.2：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色右子节点。//情形2.1.1.3：如果兄弟有两个红色子节点，我们也走这里，因为这个分支不用双旋，更好//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为黑，右孩子为红。因为文中说过我们要把它当作左孩子为空，右孩子为红，所以才需要走这个if分支if (curBrother->_right != nullptr && curBrother->_right->_col == red){/*下面的curNephewR表示cur的侄子节点，有个R说明是curBrother的右孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewR节点的地址，方便在对curParent节点旋转后还能找到curBrother的右孩子节点，为什么找它呢？需要对curBrother的右孩子节点变色调整。*/Node* curNephewR = curBrother->_right;RotateL(curParent);curBrother->_col = curParent->_col;curParent->_col = black;curNephewR->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.1：如果cur的兄弟有子节点，则只有可能为红色，当前情况就是兄弟只有红色左子节点。//说明一下，还有一种只存在于向上调整时的特殊情况也要走这里，就是curBrother的左孩子为红，右孩子为黑。因为文中说过我们要把它当作左孩子为红，右孩子为空，所以才需要走这个if分支else if (curBrother->_left != nullptr && curBrother->_left->_col == red){/*下面的curNephewL表示cur的侄子节点，有个L说明是curBrother的左孩子；为什么要设置该指针呢？因为这里有一个巨坑，因为对某个节点旋转，可能会修改该节点的结构，比如导致儿子节点不再是儿子节点，关系会乱，所以如果在发生旋转后还通过该节点来找它的孩子或者父亲节点，就不一定能找到，所以这里提前记录了curNephewL节点的地址，方便在对curBrother节点旋转后还能找到curBrother的左孩子节点，为什么找它呢？需要对curBrother的左孩子节点变色调整。*/Node* curNephewL = curBrother->_left;RotateR(curBrother);RotateL(curParent);curNephewL->_col = curParent->_col;curParent->_col = black;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4：如果cur的兄弟没有子节点走这里//说明一下，还有一种只存在于向上调整时的特殊情况也走这里，就是cur的兄弟存在两个子节点，但子节点必须全是黑色节点，不能有红色存在else if ((curBrother->_left == nullptr && curBrother->_right == nullptr)|| ((curBrother->_left != nullptr && curBrother->_left->_col == black) && (curBrother->_right != nullptr && curBrother->_right->_col == black))){//情形2.1.1.4.1：如果父亲节点是红色if (curParent->_col == red){curParent->_col = black;curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}return true;}//情形2.1.1.4.2：如果父亲节点是黑色，则需要向上迭代调整else{curBrother->_col = red;if (flag == 0){delete cur;curParent->_left = nullptr;//cur是curParent的左孩子，删除cur后，记得把链接关系断开，写在if语句里就是为了防止向上调整的时候出现cur没有被删除，但连接被断开的情况}flag = 1;//用于在向上迭代调整的时候，控制不要把cur删除，这里设置成1后，说明已经删除了目标节点，后序cur指向的节点只是在调整颜色，不需要真的把cur删除cur = curParent;curParent = curParent->_parent;//别忘了把curParent也向上调整，这个坑调试死我了，我屮}}}}}}//走到这里,即走出了用于向上调整的循环，说明是向上调整到了根节点，此时直接return true即可return true;}}}}}//没有在树中找到目标节点，说明目标节点不存在，直接return falsecout << "你要删除的节点不存在" << endl;return false;}bool Insert(const T& x){if (_root == nullptr){_root = new Node(x, black);return true;}else{Node* cur = _root;Node* curParent = nullptr;while (cur != nullptr){if (x > cur->_data){curParent = cur;cur = cur->_right;}else if (x < cur->_data){curParent = cur;cur = cur->_left;}else{return false;}}//找到了nullptr空位置，开始插入if (x > curParent->_data){cur = new Node(x, red);curParent->_right = cur;cur->_parent = curParent;}else{cur = new Node(x, red);curParent->_left = cur;cur->_parent = curParent;}//插入新节点成功，开始控制平衡Node* parent = nullptr;Node* grandParent = nullptr;while (cur->_col == red)//如果调整到根节点来了，就不能再调整了。因为根节点的颜色必须是黑色，所以这里拿cur的颜色是红色作为继续循环的条件{parent = cur->_parent;//父亲节点不可能为nullptr，因此下一行代码无需判空grandParent = parent->_parent;//注意grandParent可能为nullptr//如果cur的爷爷节点存在，并且cur和parent是连续红色节点，此时才需要变色控制平衡;否则不需要控制平衡，此时插入新节点成功,直接就可以结束Insert函数了if (grandParent != nullptr && (cur->_col == red && parent->_col == red)){//当cur与parent节点都在grandParent的左子树上时走这里if (parent == grandParent->_left){Node* uncle = grandParent->_right;//第一种情况，此时无所谓cur与parent和grandParent是否为一条直线，但要求parent为红，uncle存在且为红//g// p u// cif (parent->_col == red && uncle != nullptr && uncle->_col == red){parent->_col = black;uncle->_col = black;if (grandParent != _root)grandParent->_col = red;cur = grandParent;}else if ((parent->_col == red && uncle == nullptr) || (parent->_col == red && uncle != nullptr && uncle->_col == black)){//第二种情况，此时cur与parent和grandParent是一条直线，parent为红，uncle不存在或者存在且为黑//g// p u // cif (cur == parent->_left){RotateR(grandParent);parent->_col = black;grandParent->_col = red;return true;}//第三种情况，此时cur与parent和grandParent是一条折线，parent为红，uncle不存在或者存在且为黑//g// p u //celse if (cur == parent->_right){//先对以p为根节点的树进行左单旋，旋转完毕后将parent指针和cur指针的指向交换，此时节点之间就形成了和第二种情况完全一致的形状，接下来就照着第二种情况的做法去做即可控制平衡。//先左单旋RotateL(parent);swap(parent, cur);//注意一定要交换两个指针的指向，否则本行下面第4行和第5行的代码（即变色的代码）会出问题，会给节点变错颜色。//然后按照第二种情况的做法去做RotateR(grandParent);parent->_col = black;grandParent->_col = red;return true;}}}//当cur与parent节点都在grandParent的右子树上时走这里else if (parent == grandParent->_right){Node* uncle = grandParent->_left;//第一种情况，此时无所谓cur与parent和grandParent是否为一条直线，但要求parent为红，uncle存在且为红//g// u p//cif (parent->_col == red && uncle != nullptr && uncle->_col == red){parent->_col = black;uncle->_col = black;if (grandParent != _root)grandParent->_col = red;cur = grandParent;}else if ((parent->_col == red && uncle == nullptr) || (parent->_col == red && uncle != nullptr && uncle->_col == black)){//第二种情况，此时cur与parent和grandParent是一条直线，parent为红，uncle不存在或者存在且为黑//g// u p //cif (cur == parent->_right){RotateL(grandParent);parent->_col = black;grandParent->_col = red;return true;}//第三种情况，此时cur与parent和grandParent是一条折线，parent为红，uncle不存在或者存在且为黑// g// u p // celse if (cur == parent->_left){//先对以p为根节点的树进行右单旋，旋转完毕后将parent指针和cur指针的指向交换，此时节点之间就形成了和第二种情况完全一致的形状，接下来就照着第二种情况的做法去做即可控制平衡。//先右单旋RotateR(parent);swap(parent, cur);//注意一定要交换两个指针的指向，否则本行下面第4行和第5行的代码（即变色的代码）会出问题，会给节点变错颜色。//然后按照第二种情况的做法去做RotateL(grandParent);parent->_col = black;grandParent->_col = red;return true;}}}}//如果cur的爷爷节点不存在，或者爷爷节点存在但cur和parent节点不同时为红色，此时不需要变色控制平衡,插入函数直接就可以结束了else//(grandParent == nullptr||(grandParent != nullptr && (cur->_col == black || parent->_col == black))){return true;}}//如果cur指针一直向上调整到了根节点，根节点被调整完毕后就会走出循环，出了循环后也要return true，不要忘记了return true;}}private:void RotateR(Node* p){if (p != _root){Node* subL = p->_left;Node* subLR = subL->_right;Node* p_parent = p->_parent;subL->_right = p;subL->_parent = p_parent;if (p == p_parent->_right)p_parent->_right = subL;elsep_parent->_left = subL;p->_left = subLR;p->_parent = subL;if (subLR != nullptr)subLR->_parent = p;}else{Node* subL = p->_left;Node* subLR = subL->_right;_root = subL;subL->_right = p;subL->_parent = nullptr;p->_left = subLR;p->_parent = subL;if (subLR != nullptr)subLR->_parent = p;}}void RotateL(Node* p){if (_root != p){Node* subR = p->_right;Node* subRL = subR->_left;Node* p_parent = p->_parent;subR->_left = p;subR->_parent = p_parent;p->_parent = subR;p->_right = subRL;if (p == p_parent->_right)p_parent->_right = subR;elsep_parent->_left = subR;if (subRL != nullptr)subRL->_parent = p;}else{Node* subR = p->_right;Node* subRL = subR->_left;_root = subR;subR->_left = p;subR->_parent = nullptr;p->_right = subRL;p->_parent = subR;if (subRL != nullptr)subRL->_parent = p;}}public:bool isbalance(){//检验性质2是否被破坏if (_root != nullptr && _root->_col == red){cout << "根节点不是黑色" << endl;return false;}//检验性质3和4是否被破坏，这俩性质都通过子函数_isbalance检验else{int benchmark = 0;Node* cur = _root;while (cur != nullptr){if (cur->_col == black){benchmark++;}cur = cur->_left;}return _isbalance(_root, 0, benchmark);}}private:bool _isbalance(Node* root, int blackNum, int benchmark){//检测性质3if (root == nullptr){if (blackNum != benchmark){cout << "某条路径上的黑色节点的数量和基准值benchmark不相等，性质3被破坏了" << endl;return false;}elsereturn true;}if (root->_col == black)blackNum++;//检测性质4if (root->_col == red && root->_parent->_col == red)//这里root->_parent不可能为nullptr，因为root的颜色是红色，所以root不可能为整棵树的根节点，所以root->_parent不可能为nullptr。{cout << "存在连续红色节点，性质4被破坏" << endl;return false;}bool x = _isbalance(root->_left, blackNum, benchmark);bool y = _isbalance(root->_right, blackNum, benchmark);return x && y;}public:void Inorder(){_Inorder(_root);}private:void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_data << ' ';_Inorder(root->_right);}private:Node* _root;};

test.cpp文件的代码如下。

#include"RBTree.h"void test1(){RBTree<int>t1;int a[5] = { 18,23.11,14,12 };t1.Insert(18);t1.Insert(23);t1.Insert(11);t1.Insert(14);t1.Insert(12);t1.Inorder();}void test2(){RBTree<int>t1;int a[] = { 4,2,6,1,3,5,15,7,16,14 };for (auto e : a){t1.Insert(e);}cout<<t1.isbalance();}void test3(){int a[100000];srand(time(0));for (int i = 0; i < 100000;i++){a[i] = rand();}RBTree<int>t1;for (auto e : a){cout <<"插入值为：" << e << endl;t1.Insert(e);}cout <<"（1表示平衡，0表示不平衡）插入结束后平衡性是：" << t1.isbalance() << endl;}void test4(){srand(time(0));RBTree<int>t1;int a[20000];for (int i = 0; i < 20000; i++){a[i] = rand();}for (int i = 0; i < (sizeof(a) / sizeof(int)); i++){t1.Insert(a[i]);}cout << "（1表示平衡，0表示不平衡）插入结束后平衡性是：" << t1.isbalance() << endl;cout << "——开始删除——" << endl;for (int i = 0; i < (sizeof(a) / sizeof(int)); i++){cout << "现在循环的次数的是:" <<i<< " 现在删除的是:" << a[i] << endl;t1.Erase(a[i]);cout << "平衡性是：" << t1.isbalance() << endl;}cout << "——所有节点删除完毕——" << endl;cout << "平衡性是：" << t1.isbalance() << endl;}void main(){test4();}

中

如果觉得《红黑树（RBTree）的模拟实现》对你有帮助，请点赞、收藏，并留下你的观点哦！