墨色规则与血色节点：C++红黑树设计与实现探秘

前言

​    前几天攻克了AVL树，我们已然是平衡二叉树的强者。但旅程还未结束，下一个等待我们的，是更强大、也更传奇的**终极BOSS**——红黑树。它不仅是map和set的强大心脏，更是C++ STL皇冠上的明珠。准备好了吗？让我们一起揭开它的神秘面纱。

1.红黑树的概念

1.1.红黑树是什么

​    红黑树是一科二叉搜索树，他的每个节点增加一个存储为代表着该节点的颜色，和它的名字一样，节点的颜色可以是红色或者是黑色。通过对任何一条根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

​    红黑树是被很多条规则进行束缚的二叉搜索树，通过这些规则，可以保证红黑树没有一条路径会比其他路径长出2倍，并且保持其相对平衡，下面我来讲述一下这些规则。

1.2.红黑树的规则

​    1.每个节点不是黑色的就是红色的（这肯定，不然不会被叫做红黑树了）。

​    2.根节点必须是黑色的

​    3.如果一个节点是红色的，则它的两个孩子节点必须是黑色的，也就是说任意一条路径上并不会出现连续的红色的节点。

​    4.对于任意的一个节点，从该节点到其所有的NULL节点的简单路径上，均包含着相同数目的黑色节点。

​    以上便就是红黑树的四条规则，其实《算法导论》上也是补充了一个知识点：每个叶子节点（NULL）都是黑色的规则。他这里所指的叶子节点不是传统意义上的叶子节点，而是我们所说的空节点，有些书籍上也把NULL叫做外部节点。NULL是为了方便准确的标志处所有路径，《算法导论》在后续实现的细节中忽略了NULL节点，所以我们知道这个概念即可。下面我放几张红黑树的示意图。

1.3.红黑树如何确保最长路径不超过最短路径的两倍

​    由规则4可以知道，每条路径上有着数量相同的黑色节点，所以在极端场景下，就比如上面最后一个图，一条路上全都是黑色节点，最短路径其实就是一条路上全是黑色节点，我们将最短路径的长度记作bh。

​    在看规则2和规则三，我们可以清楚的知道，一条路上不会出现连续的红色节点，所以我们容易知道最长路径应该是一红一黑交织组成，所以最长路径的长度是2bh。

​    根据红黑树的规则，我们可以知道一般情况下的红黑树的路径是由数量不等的红黑节点组成的，一红一黑交织进行和全是黑的是不太容易出现的，所以假设红黑树一条路径的长度为h，所以bh<=h<=2bh，即红黑树的最长路径不会是最短路径的两倍。

1.4.红黑树的效率问题

​    我们假设红黑树的节点个数为N，最短路径的长度为h，所以可知：2^h - 1 <= N < 2^2*h - 1，由此可以推出h大约等于logN，也就是红黑树搜查的效率问题最差也是2 * logN，时间复杂度终归还是O（log（N））。

​    红黑树的表达相对AVL树是要更抽象一些的，AVL树可以根据高度更加直观的看出树的平衡，而红黑树则是需要根据四条规则的颜色进行约束，间接的实习了近似平衡，他们的效率都是同一档次的，但是相对而言，插入相同数量的节点，红黑树的旋转次数变的更少了，因为它对平衡的把控并不是那么的严格。

2.红黑树的实现

2.1.红黑树的结构

​    在我们书写平衡树的代码之前，通常我们需要先完善一下它的结构，就比如其中最基础的，它的每个节点应该存储什么的数据，红黑树也是一个典型的三叉链，所以它的节点需要包含它的父节点以及左右孩子节点，并且由于红黑树是通过颜色进行平衡的位置，我们还需要设置好一个联合体来确定节点的颜色，我们默认颜色就是红色，并且红黑树也是通过Key和Value进行存放数据的，Key就好比我们开车进入商场停车场的车牌号，而Value就是记录进入停车场的时间的，由此来确定需要缴纳多少钱。所以由此来看Key就是一个标记，而红黑树真正的核心应该是Value。下面我来展示一下红黑树结构相关的代码。

enum Colour { RED, BLACK }; // 这里我们默认按key/value结构实现 template<class K, class V> struct RBTreeNode //struct不用域作用限定符默认就是 { // 这里更新控制平衡也要加入parent指针 pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; //存放节点的颜色 RBTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) ,_col(RED) {} }; template<class K,class V> class RBTree { typedef RBTreeNode<K,V> Node; public: private: Node* _root = nullptr; }

2.2.红黑树的查找

​    红黑树的查找和二叉搜索树的查找是一样的，代码也是比较类似的，它们的效率都是log(N)，所以我就不在细讲了，看不懂的读者可以加我主页的微信询问我。

Node* Find(const K& key) { Node* cur = _root; //代替根节点去便利 while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->_right; } else { return cur; } } return NULL; }

3.红黑树的插入

​    下面我们就进入到了红黑树最难的部分（删除不算）：红黑树的插入，红黑树的插入的复杂程度还是和AVL数比较类似的，但是我个人感觉红黑树相对AVL树更加抽象一些，因为它不仅仅涉及到了旋转，还有变色的操作，依次来维持它的那四条规则，废话不多说，接下来我们进入红黑树的插入讲解。

​    在讲插入过程的时候事先说明一下：假设我们把新增的节点叫做c(cur)，c的父亲则标记为p（parent），p的父亲节点标记为g（grandfather），p的兄弟节点表姐为u（uncle）。

3.1.红黑树插入一个值的大致过程

​    插入一个值是按照二叉搜索树的规则来进行的，插入后的值我们需要让其符合红黑树的四条规则。如果是空树插入，那么插入的必然就是黑色节点，因为根节点必须是黑色的；如果是非空树插入，那么插入的节点一定是红色的，因为第四条规则约束着，如果插入的是黑色节点，那么第四条规则就被破坏了。非空树在插入的时候，插入的节点必须是红色节点，如果其父节点是黑色的，那么并没有违法规则，插入成功。如果其父节点是红色的，那么就违反了第三条规则。进一步的分析，c是红色，p也是红色，那么g必然是黑色的（如果g也是红色的那么就说明在没有插入c的时候此树已经违反规则了），这三个的颜色都已经定了，所以关键的变化还得看u的变化，分别需要分为以下四种情况讨论，在讨论之前，我先把插入的相关代码放到下面（和二叉搜索树差不多）。

bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; //根节点一定是黑色的 } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else { //cout << "重复节点不可插入" << endl; //数据少可以这么写，数据多，就会很难受，循环多次才结束 return false; } } //走到这说明插入成功了 cur = new Node(kv); cur->_col = RED; //新插入的结点一定是红色 //开始进行变色处理 //和父亲结点进行配对 if (parent->_kv.first < kv.first) { //比父亲结点大，插在右边 parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; //这个一定不可以忘掉 }

3.2.情况一：变色

1.讲解

​    如上图所示，如果c是红的，p为红，g为黑，u存在并且是红色的话，那么我们就需要进行变色处理，即将p和u都变为黑色，g变红。再把g当做新的c，继续往上进行更新。可能很多读者不晓得我这么做的原因，下面我将进行解释。

​    因为p和u均是红色，g是黑色，把p和u都变为黑色，左右子树都多增加了一个黑色节点，g变为了红色，因为着p和u所在的支路上黑色节点的个数是没有变化的，这样就没有违反规则四，并且同时解决了红色节点的孩子还是红色节点的问题；至于为何让g变为新的c，因为g的父节点我们并不知晓是什么颜色的，倘若还是黑色，那就皆大欢喜，不用在往上进行遍历了；但是如果是红色，那么我们还需进行变色处理。不过还有一种情况，就是g就是整棵树的根，那么我们就需要把g变为黑色，因为红黑树的根节点是黑色的。

​    当然，上图是属于第一种变色的特殊情况，和AVL树类似，我们还需了解抽象状态下的AVL树的变色，如下图所示。

​    上图则是对变色进行了比较抽象的表达，d，e，f代表着每条路径上有hb个黑色节点的子树，a/b则代表着每条路径上拥有hb-1个黑色节点的根为红的子树，其中hb>=0，下面这个情况就形象的代表了当我们在a或者b中进行了一次变色，传递到上面时，可能也会让上面进行变色处理。当然不，情况一仅仅设计了变色的处理，而不涉及旋转，所以左右子树都是相同的变色处理，以上就是情况一的讲解，下面我们进入代码的讲解。

2.代码

​    此时我们还需要划分此时的父亲节点是左子树还是右子树，下面我们就单拿左子树为例，因为左右子树都是差不多的，掌握了一种，另一种也是会更为轻松的掌握。

​    刚开始，我们需要先把g节点表示出来，即p节点的父亲节点，因为我们进行变色处理以后，需要往上进行更新，所以变色的操作应该是一次次循环的过程。

while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; }

​    我们需要通过if语句确认p节点是在左边的，之后我们需要把u节点表示出来，如果此时u节点存在并且u节点就是红色的，那么就符合情况一，之后我们先把p和u节点都染成黑色的，再把g节点变为红色的，做完这些操作以后，我们就需要更新一下c和p节点了更新结束，代表一次变色成功，继续往上进行更新。

if (grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { //单纯的变色处理 grandfather->_col = RED; parent->_col = BLACK; uncle->_col = BLACK; //在往上进行查询 cur = grandfather; parent = cur->_parent; } }

1.完整变色（p节点在左边）

while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; //先来节点都是左边的情况 if (grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { //单纯的变色处理 grandfather->_col = RED; parent->_col = BLACK; uncle->_col = BLACK; //在往上进行查询 cur = grandfather; parent = cur->_parent; } } }

2.完整变色（p节点在右边）

if(grandparent->_right == parent) { Node* uncle = grandfather->_left; if (uncle&& uncle->_col == RED) { grandfather->_col = RED; parent->_col = BLACK; uncle->_col = BLACK; //在往上进行查询节点是否正确 cur = grandfather; parent = cur->_parent; } }

3.3.情况二：单旋+变色

1.讲解

​    又看到了我们的老朋友：单旋了，上次我们和它见面还是AVL树，没想到到了红黑树，它又来追杀我们了（┭┮﹏┭┮），不过红黑树的单旋其实和AVL树是类似的，这意味着我们可以直接使用AVL树的单旋代码（(#^.^#)），下面我通过一个特殊的例子来给各位讲解情况二。

​    如果c是红色，p是红色，g为黑，u不存在或者u是黑色的时候，这个时候我们就不能单单依靠表变色进行红黑树的修正了，因为这样会违反规则四；如果u不存在，那么c一定就是新的节点；如果u是黑的，那么c一定不是新的节点，而是因为之前c本来就是黑色的节点，但是由于进行了变色处理，导致c变成了红色节点。

​    如果p是g的左子树，如上图所示，c是p的左子树，那么我们就以g为旋转点，先进行一次右单旋，如下图所示。

​    此时我们需要让g变为红色，p变为黑色即可。此时p变成了这棵子树新的根了，这样子树黑色节点的数量不变，没有连续的红色节点，并且还不需要往上进行更新了，因为p的父亲无论是啥都没会违反这些规则了。

​    如果p是g的右子树，c是p的右，如上图所示，那么我们还是以g为旋转点，但是是左单旋，如下图所示。

​    此时我们需要让p变为黑色，g变为红色即可，p变为了新子树的根，这样子树的黑色节点的数量并没有改变，没有连续的红色节点，并且还不需要往上进行更新了。

​    当然，我们学完了特殊情况，还需要知晓一些抽象情况，下面我就放上一张图片，希望各位读者自行阅读。

2.代码

​    首先我们需要先知晓，此时的情况二也是在循环之中的，此时我们还是以右单旋为例进行讲解，当c为p的左孩子时，意味着此时我们需要单旋进行处理（前提是u节点为黑色或者是空），那么此时我们需要进行单旋处理，单旋的话我们直接把AVL树的单旋copy过来即可（忘了的看我上一篇文章），之后在进行相应的变色处理即可。下面我把两个完整代码展示出来。

1.右单旋+变色

if(uncle -> col == black || uncle == nullptr) { if(parent -> left == cur) { //右单旋 RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; break; //无须在往上走了 } }

2.左单旋+变色

if(uncle -> col == black || uncle == nullptr) { if(parent -> right == cur) { //进行左单旋处理 RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } }

3.情况三：双旋+变色

​    既然都有单旋这种情况了，那么双旋也是必不可少的，当然，双旋的代码还是和AVL树是一样的（(#^.^#)），减少了很大部分的工作量。

1.讲解

​    情况三的颜色情况其实和情况二是类似的，它们均是c和p都是红色，g为黑色，u是不存在或者为黑色，所以下面我们进入双旋情况的讲解。

​    如果p是g的左，c是p的右，此时我们仅仅依靠单旋是不可以进行红黑树的纠正的，所以此时我们就需要通过双旋进行调整，我们先以p为旋转点进行一次左旋，在以g进行一次右旋，如下图所示。

​    此时我们仅需让c变为黑色，g变为红色即可，c变成了这棵树新的根，这样做黑色节点的数目没有改变，没有连续的红色节点了，因为g是黑色，此时无论他的父节点是什么，都不会影响结果了。

​    如果此时p是g的有孩子，c是p的左孩子，这个时候我们也是需要双旋进行处理的，先以p为旋转点进行右旋，再以g为旋转点进行左旋，之后把c变为黑色，g为红色即可。

​    以上是红黑树情况二的特殊情况，下面我们来看看一般情况，即抽象表达，看一看下图的图，我相信你会懂的。

2.代码

​    我个人认为情况三的代码比较容易，各位读者通过我上面的讲解应该就知晓代码如何书写了，所以我下面直接放代码（不会的读者可以私信询问我）。

如果p是g的左孩子

//左右双旋转 RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;

如果p是g的右孩子

RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;

4.红黑树的验证

1.如何验证

​    此时我们已经讲述完了红黑树相关知识点的讲解，可能有很多读者想知道自己写的红黑树是否是正确的，下面我将给各位讲述一下如何验证自己写的红黑树。此时我们需要检验四条规则，如果满足这四条规则，那么说明这棵树就是一颗非常棒的红黑树。

​    1.规则一枚举颜色类型，天然的实现保证了节点非红即黑。

​    2.规则二直接检查根部即可

​    3.规则三进行前序遍历检查，遇到红色节点检查孩子不太方便，因为孩子是有两个的，并且不一定就是存在的，反过来检查颜色就方便多了。

​    4.规则四进行前序遍历，遍历过程中用形参记录根到当前节点的黑色节点的数量，前序遍历遇到黑色节点就++blackNum，走到空就计算一条路径黑色节点的数量。以任意一条路径的黑色节点数量作为基准，依次比较即可。

2.相关代码

bool Check(Node* root, int blackNum, const int refNum) { if (root == nullptr) { // 前序遍历走到空时，意味着一条路径走完了 //cout << blackNum << endl; if (refNum != blackNum) { cout << "存在黑色结点的数量不相等的路径" << endl; return false; } return true; } // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了 if (root->_col == RED && root->_parent->_col == RED) { cout << root->_kv.first << "存在连续的红色结点" << endl; return false; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); }

5.红黑树的删除

​    和AVL树一样，由于我现在并没有掌握红黑树的删除，所以各位读者如果想要理解可以看一下其他博主的博文，小编目前还不会这个，希望我以后会掌握。

6.完整代码

#pragma once #include<iostream> #include<vector> #include<assert.h> #include<ctime> //这里将要进行红黑树的实现 namespace wang { using namespace std; //先设置好相应的颜色以及结点的相关属性（这里我就直接拷贝了） enum Colour { RED, BLACK }; // 这里我们默认按key/value结构实现 template<class K, class V> struct RBTreeNode //struct不用域作用限定符默认就是 { // 这里更新控制平衡也要加入parent指针 pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; //存放节点的颜色 RBTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) ,_col(RED) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; private: void RotateR(Node* parent) { //进行旋转处理 Node* subl = parent->_left; //将来要成为父亲的 Node* sublR = subl->_right; parent->_left = sublR; if (sublR) { //如果这个结点存在的话，让它的父亲结点成为parent sublR->_parent = parent; } //此时需要先把P的父亲结点保存起来 Node* ppnode = parent->_parent; subl->_right = parent; parent->_parent = subl; if (ppnode == nullptr) { _root = subl; //证明刚才要调整的parent就是根节点 subl->_parent = ppnode; } else { if (subl->_kv.first > ppnode->_kv.first) { ppnode->_right = subl; } else { ppnode->_left = subl; } subl->_parent = ppnode; } } void RotateL(Node* parent) { //左单旋处理 Node* subL = parent->_right; Node* subLL = subL->_left; Node* ppnode = parent->_parent; parent->_right = subLL; if (subLL) { subLL->_parent = parent; } //开启最复杂的一集 subL->_left = parent; parent->_parent = subL; if (ppnode == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (subL->_kv.first > ppnode->_kv.first) { ppnode->_right = subL; } else { ppnode->_left = subL; } subL->_parent = ppnode; //这个忘加了，想事要想全，这点我确实是大意了 } } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } public: //插入pair类型的结点 bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; //根节点一定是黑色的 } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else { //cout << "重复节点不可插入" << endl; //数据少可以这么写，数据多，就会很难受，循环多次才结束 return false; } } //走到这说明插入成功了 cur = new Node(kv); cur->_col = RED; //新插入的结点一定是红色 //开始进行变色处理 //和父亲结点进行配对 if (parent->_kv.first < kv.first) { //比父亲结点大，插在右边 parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; //这个一定不可以忘掉 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; //先来节点都是左边的情况 if (grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { //单纯的变色处理 grandfather->_col = RED; parent->_col = BLACK; uncle->_col = BLACK; //在往上进行查询 cur = grandfather; parent = cur->_parent; } //uncle不存在或者存在且为黑色 else { if (parent->_left == cur) { //右单旋 RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { //左右双旋转 RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } //旋转之后肯定就是一个很好的红黑树了 } //如果是父亲结点是右子树 else { Node* uncle = grandfather->_left; if (uncle&& uncle->_col == RED) { grandfather->_col = RED; parent->_col = BLACK; uncle->_col = BLACK; //在往上进行查询节点是否正确 cur = grandfather; parent = cur->_parent; } //叔叔节点要不是黑的要不就是空的 else { if (parent->_right == cur) { //进行左单旋处理 RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { //先双旋 RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } //根节点一定是黑色的 //_root->_col = BLACK; } _root->_col = BLACK; return true; //此时说明插入成功 } Node* Find(const K& key) { Node* cur = _root; //代替根节点去便利 while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->_right; } else { return cur; } } return NULL; } void InOrder() { _InOrder(_root); //复用一下就好了，遍历需要root，平常root对象是穿不了的，所以放在一个函数里面，复用一下 } bool Check(Node* root, int blackNum, const int refNum) { if (root == nullptr) { // 前序遍历走到空时，意味着一条路径走完了 //cout << blackNum << endl; if (refNum != blackNum) { cout << "存在黑色结点的数量不相等的路径" << endl; return false; } return true; } // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了 if (root->_col == RED && root->_parent->_col == RED) { cout << root->_kv.first << "存在连续的红色结点" << endl; return false; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); } bool IsBalance() { if (_root == nullptr) return true; if (_root->_col == RED) return false; // 参考值 int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refNum; } cur = cur->_left; } return Check(_root, 0, refNum); } int Height() { return _Height(_root); } int Size() { return _Size(_root); } protected: int _Size(Node* root) { if (root == nullptr) return 0; return _Size(root->_left) + _Size(root->_right) + 1; } int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } private: Node* _root = nullptr; }; void TestRBTree1() { RBTree<int, int> t; // 常规的测试用例 //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 特殊的带有双旋场景的测试用例 int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { /*if (e == 14) { int x = 0; }*/ t.Insert({ e, e }); //cout << "Insert:" << e << "->"; //cout << t.IsBalanceTree() << endl; } t.InOrder(); cout << t.IsBalance() << endl; } void TestRBTree2() { const int N = 1000000; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); } size_t begin2 = clock(); RBTree<int, int> t; for (auto e : v) { t.Insert(make_pair(e, e)); } size_t end2 = clock(); cout << t.IsBalance() << endl; cout << "RBTree Insert:" << end2 - begin2 << endl; cout << "RBTree Height:" << t.Height() << endl; cout << "RBTree Size:" << t.Size() << endl; size_t begin1 = clock(); // 确定在的值 /*for (auto e : v) { t.Find(e); }*/ // 随机值 for (size_t i = 0; i < N; i++) { t.Find((rand() + i)); } size_t end1 = clock(); cout << "RBTree Find:" << end1 - begin1 << endl << endl; } }

7.小结

​    本篇文章到这里也就结束了，这篇文章如果我没记错我前前后后大约一周才写完的，因为我好久没用C++了，导致我忘记了红黑树的相关知识点，所以我其实算是边学习边写博客，所以文章可能会有错误，希望读者不要狠狠的喷小编，小编目前就是个fw，希望我会逐渐掌握自己已经遗忘的知识点，如果文章有错误可以在评论区指出，我一定会认真更改的，一起学习的时光总是短暂的，那么各位大佬们，我们下一篇文章见啦！