【C++】红黑树迭代版

目录

前言：

一：什么是红黑树？

二：插入什么颜色节点？

三：定义树

四：左单旋和右单旋

1.右单旋 

2.左单旋

五：调整树 

1.当parent节点为黑色时

2.当parent节点为红色时

2.1 uncle节点存在且为红色时

2.2 uncle节点不存在或者为黑时 

2.2.1 cur == parent->_left && parent == grandfather->_left

2.2.2 cur == parent->_right && parent == grandfather->_left

2.2.3 cur == parent->_right && parent == grandfather->_right

2.2.4 cur == parent->_left && parent == grandfather->_right 

六：验证红黑树 

七：红黑树的删除

八：其他方法的补充(拷贝构造)

九：全部代码

总结：

---

前言：

如果大家看过之前的文章，已经了解并实现了AVL树，那么接下来，我们就要完成红黑树的实现了，在此之前，依旧是推荐各位先去看b站up主 蓝不过海呀 的红黑树章节(红黑树 - 定义, 插入, 构建_哔哩哔哩_bilibili)。

一：什么是红黑树？

各位是否感觉我已经会了AVL树了，AVL树已经很强了，难道还有比AVL树更强的树？有的。

这里先说明：AVL树是一颗高度平衡得树，而红黑树不是。但它们都是二叉搜索树。

既然红黑树不是高度平衡，那它的性能怎么可能比AVL树还好呢？对，没错，在搜索方面确实不如AVL树，但是大家有没有想过，AVL会频繁地调整树，这也是一种消耗。

而红黑树不是高度平衡意味着不需要进行频繁地旋转，所以在插入和删除的效率上高于AVL树。

红黑树顾名思义，它是由红色节点和黑色节点组成的树，这里有一下几个性质：

1. 树的根节点始终为黑色。
2. 所有叶子节点（即空子节点）均为黑色。---->根叶黑
3. 如果某个节点为红色，则其两个子节点必然是黑色（即不允许连续的红色节点）。---->不红红
4. 对于任意一个节点而言，从该节点到其后代叶节点的所有路径上包含相同数量的黑色节点。这句有点抽象，说人话就是每一条路径上的黑色节点数量都是相同的。---->黑路同
5. 最长路径不超过最短路径的两倍。---->最长路径 <= 最短路径 * 2

对于最后一个性质来说，其实最短路径一定是节点全部为黑色的路径。这里先给出一张图：

以上是一颗红黑树。但是下面的不是红黑树： 

乍一看，满足所有红黑树的性质，但是我们说空节点也是黑色节点，所以我们把空节点显示出来就会发现问题：

其违反了黑路同的性质。

二：插入什么颜色节点？

我们插入节点的时候，应该插入什么颜色节点呢？

好比你考试考得不好，告诉爸爸，爸爸绝对会打你，甚至可能拉上妈妈一起混合双打；而告诉妈妈，妈妈有概率会打你。

因为黑路同的性质，如果我们插入黑色节点，意味着每一条路径都需要调整(也就是爸妈混合双打)；而插入红色节点，可能调整一小部分甚至无需调整。

我们使用枚举定义树的颜色：

//定义颜色
enum Colour
{RED,   //红BLACK  //黑
};

所以我们应该插入红色节点，所以这里给出树节点的定义(这里和AVL定义类似，但无需平衡因子，多了颜色)：

//定义树节点
template<class K, class V>
struct RBTreeNode
{//让编译器生成默认构造RBTreeNode() = default;//写一个构造RBTreeNode(const pair<K, V>& kv): _kv(kv){}pair<K, V> _kv;RBTreeNode* _left = nullptr;   RBTreeNode* _right = nullptr;RBTreeNode* _parent = nullptr;  //父节点Colour _col = RED;     //默认为红色
};

这里说明一下，每个树节点存储的数据是键值对，是为了后面封装map和set，不过各位不用着急，继续追剧即可。 

三：定义树

嘿嘿，我们目前思路还不是特别清楚，不过没关系，我们先把框架搭建起来。 

这里我们先把树声明一下，存储的是树节点，树节点存储的是键值对，要传入两个模板参数，所以树也需要两个模板参数，成员变量只需要一个根节点并初始化为nullptr即可：

template<class K, class V>
class RBTree
{
public://对RBTreeNode进行重命名using Node = RBTreeNode<K, V>;private://一个_root成员变量即可Node* _root = nullptr;
};

是不是非常简单？对。之后我们写插入函数(作者不专业，叫方法或者函数都行)，这里没有上强度，我们先按照二叉搜索树的插入把框架搭起来：

//插入
bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){Node* newNode = new Node(kv);_root = newNode;_root->_col = BLACK;  //更新根节点 并置为黑色return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{//已经存在该值了 不处理return false;}}//新建节点cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent; //记得更新父节点//调整代码//...return true;
}

四：左单旋和右单旋

因为作者精力有限，希望大家理解，关于单旋这部分知识我们上一篇博客有很详细的讲解，这里只给出代码不一一进行讲解。

1.右单旋 

//旋转函数只会在类内调用 写成私有
//右旋函数
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right; //记录冲突节点subL->_right = parent;parent->_left = subLR;      //冲突的右孩变左孩//冲突右孩存在 更改_parent指向if (subLR){subLR->_parent = parent;}//先判断有没有parent->_parentNode* parentP = parent->_parent; //先记录parent->_parent = subL;          //后更改if (parentP){//有父节点 判断parent在parentP的哪边if (parent == parentP->_left){parentP->_left = subL;}else{parentP->_right = subL;}subL->_parent = parentP;}else{//此时操作_root节点_root = subL;subL->_parent = nullptr;}
}

2.左单旋

//左旋函数
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left; //记录冲突节点subR->_left = parent;parent->_right = subRL;      //冲突的左孩变右孩//冲突左孩存在 更改_parent指向if (subRL){subRL->_parent = parent;}//先判断有没有parent->_parentNode* parentP = parent->_parent; //先记录parent->_parent = subR;          //后更改if (parentP){//有父节点 判断parent在parentP的哪边if (parent == parentP->_left){parentP->_left = subR;}else{parentP->_right = subR;}subR->_parent = parentP;}else{//此时操作_root节点_root = subR;subR->_parent = nullptr;}
}

五：调整树 

我们已经把插入代码的框架搭好了，接下来如何调整呢？这里有很多种情况，这里先说最简单的。

在调整树之前，我们先来介绍几个节点，方便后面描述：

• cur：当前遍历节点
• parent：cur->_parent也就是cur的父节点
• grandfather：cur的祖父节点，也就是parent->_parent
• uncle：cur的叔叔节点，也是parent的兄弟节点(可能在grandfather左边或者右边)

以下是其中的一种情况： 

所以你也能想到有很多种情况。

1.当parent节点为黑色时

因为不能违反黑路同的性质，此时你会发现没有违反任何一个性质，所以直接插入即可。

2.当parent节点为红色时

此时应该怎么办？大家想一下，我们可以去观察uncle节点，此时uncle节点有两种情况，我们可以先考虑简单的情况。

2.1 uncle节点存在且为红色时

注意，此时cur为插入节点，是红色，为了不破坏黑路同的性质，我们是不是可以将uncle和parent变成黑色，将grandfather变成红色的呢？

对，就是这样：

这里注意，如果最开始根节点就是grandfather，我们要将其变成黑色，这里我们可以暴力一些，我们每次调整完，都在最后将根节点变黑，这样就无需在判断逻辑中修改_root节点颜色。

但是uncle节点我们并不知道位置，所以要判断一下：

//此时parent为红色
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{//此时uncle为grandfather右孩子Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) {//uncle必须存在//将grandfather parent uncle 变色grandfather->_col = RED;uncle->_col = parent->_col = BLACK;}
}
else
{//此时uncle为grandfather左孩子Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//将grandfather parent uncle 变色grandfather->_col = RED;uncle->_col = parent->_col = BLACK;}
}

 大家仔细思考一下，走到这里是什么情况？一定有grandfather节点，因为遇到了两个连续的红色的节点。

但是大家再看下面这张图，这样调整并没有结束：

这个时候怎么办呢？对，向上迭代！

我们将cur复制到grandfather上，parent是修改后cur->_parent。所以这个步骤是循环的。

我们不能向上面那样写。当然，parent可能会为空所以当向上面那样变色时，判断parent为不为空并且不为黑时跳出循环：

while (parent && parent->_col != BLACK)
{//此时parent为红色Node* grandfather = parent->_parent;if (parent == grandfather->_left){//此时uncle为grandfather右孩子Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//uncle必须存在//将grandfather parent uncle 变色grandfather->_col = RED;uncle->_col = parent->_col = BLACK;//向上迭代cur = grandfather;parent = cur->_parent;}}else{//此时uncle为grandfather左孩子Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//将grandfather parent uncle 变色grandfather->_col = RED;uncle->_col = parent->_col = BLACK;//向上迭代cur = grandfather;parent = cur->_parent;}}
}

2.2 uncle节点不存在或者为黑时 

因为nullptr也是黑色，但是就是另外一种情况，此时就需要用到之前的知识了，LL/RR/LR/RL型旋转了。

此时先判断cur在parent的哪一侧，之后确定是什么旋转。

2.2.1 cur == parent->_left && parent == grandfather->_left

此时就是LL型，我们右旋即可。之后这里要记得变色，规则是旋转节点和旋转中心节点变色。

和AVL一样，旋转完之后就跳出循环，也就是说，进行一次旋转操作，就会符合红黑树性质！

//此时要判断cur在parent的哪边
if (cur == parent->_left)
{//最外面大条件为parent == grandfather->_left//所以此时是LL型 右旋RotateR(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;
}//最后都要跳出循环
break;

2.2.2 cur == parent->_right && parent == grandfather->_left

此时就是LR型，也就是要进行双旋，但是和AVL不一样的是，我们可以不用考虑平衡因子，所以我们可以直接先左旋parent，之后右旋grandfather。记住，这里旋转了两次，只有最后一次时需要变色！所以这里cur是最后一次旋转的中心节点！

所以此时我们可以完善parent == grandfather->_left的情况了：

//此时要判断cur在parent的哪边
if (cur == parent->_left)
{//最外面大条件为parent == grandfather->_left//所以此时是LL型 右旋RotateR(grandfather);//变色grandfather->_col = RED;parent->_col = BLACKE;
}
else
{//在parent的右边//LR双旋 RotateL(parent);     //先左旋parentRotateR(grandfather);//后右旋grandfather//变色grandfather->_col = RED;cur->_col = BLACK; //注意是cur是最后旋转中心节点
}//最后都要跳出循环
break;

2.2.3 cur == parent->_right && parent == grandfather->_right

我们上一个大条件是parent == grandfather->_left，里面两种类型已经完善了。一共四种类型，现在我们要说parent == grandfather->_right了。

此时cur在parent的右边，所以是RR型，左旋即可。

2.2.4 cur == parent->_left && parent == grandfather->_right 

这里就是RL型，记住最后是grandfather和cur变色即可！

以上两种类型代码如下：

if (cur == parent->_right)
{RotateL(grandfather); //左旋//变色grandfather->_col = RED;parent->_col = BLACK;
}
else
{//对parent右旋RotateR(parent);RotateL(grandfather); //对grandfather左旋//变色grandfather->_col = RED;cur->_col = BLACK;
}
break;

所以完整插入代码如下：

//插入
bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){Node* newNode = new Node(kv);_root = newNode;_root->_col = BLACK;  //更新根节点 并置为黑色return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{//已经存在该值了 不处理return false;}}//新建节点cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent; //记得更新父节点if (parent->_col == BLACK){return true;}else{while (parent && parent->_col != BLACK){//此时parent为红色Node* grandfather = parent->_parent;if (parent == grandfather->_left){//此时uncle为grandfather右孩子Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//uncle必须存在//将grandfather parent uncle 变色grandfather->_col = RED;uncle->_col = parent->_col = BLACK;//向上迭代cur = grandfather;parent = cur->_parent;}else{//此时要判断cur在parent的哪边if (cur == parent->_left){//最外面大条件为parent == grandfather->_left//所以此时是LL型 右旋RotateR(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}else{//在parent的右边//LR双旋 RotateL(parent);     //先左旋parentRotateR(grandfather);//后右旋grandfather//变色grandfather->_col = RED;cur->_col = BLACK; //注意是cur是最后旋转中心节点}//最后都要跳出循环break;}}else{//此时uncle为grandfather左孩子Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//将grandfather parent uncle 变色grandfather->_col = RED;uncle->_col = parent->_col = BLACK;//向上迭代cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather); //左旋//变色grandfather->_col = RED;parent->_col = BLACK;}else{//对parent右旋RotateR(parent);RotateL(grandfather); //对grandfather左旋//变色grandfather->_col = RED;cur->_col = BLACK;}break;}}}}//最后都时 _root->_col = BLACK 即可_root->_col = BLACK;return true;
}

六：验证红黑树 

已经到达最后一步，此时要验证红黑树，我们这样验证：统计一条路径上的黑色节点数量，之后利用递归看每一条路径上的黑色节点数量是否相同。

此时需要用到根节点，但是我们不能改变根节点，所以我们可以将其写为子函数。

	bool IsRBTree(){if (_root == nullptr)return true;if (_root->_col == RED)return false;//先统计黑色节点数量 因为有空指针也算黑色节点 所以初始化为1size_t len = 1;Node* cur = _root;while (cur){if (cur->_col == BLACK){++len;}cur = cur->_left; //沿着最左边路径走 统计黑色节点数量}return _IsRBTree(len, _root, 0); //第三个是其他路径黑色节点数量 }bool _IsRBTree(const size_t& len, Node* root, int tmp){if (root == nullptr){++tmp; //空节点算黑色节点 自增1if (tmp != len){cout << "违反黑路同性质！" << endl;return false;}return true;}if (root->_col == BLACK){++tmp;}//这里再判断是否违反不红红规则 一定是先判断当前节点是红色再去判断父节点//否则可能会遇到空指针异常if (root->_col == RED && root->_parent->_col == RED){cout << "违反不红红性质！" << endl;return false;}//之后遍历即可return _IsRBTree(len, root->_left, tmp) && _IsRBTree(len, root->_right, tmp);}

当然我们应该把_IsRBTree写成私有函数，但是为了方便展示，大家下去可以这样做。

七：红黑树的删除

嘿嘿，诈你一下，这里作者精力真的有限，等有时间一定研究，说到做到，敬请期待！

八：其他方法的补充(拷贝构造)

我们为了方便画出树，可以写一个前序、中序遍历，之后补充拷贝构造，析构函数，=运算符重载，Find函数，这里小编就一笔带过了，直接复制粘贴了，因为和上面的难度简直天壤之别。都会在全部代码中说明。

这里补充一下拷贝构造，我们不能无脑递归插入，因为有 _parent 和 颜色 也需要赋值，所以这里应该这样写拷贝构造：

//写一个拷贝构造
RBTree(const RBTree<K, V>& t)
{_root = Copy(t._root);
}//这里也不把Copy写成私有的了
Node* Copy(Node* root)
{if (root == nullptr)return nullptr;//用前序遍历Node* newNode = new Node(root->_kv);//这里注意修改颜色newNode->_col = root->_col;newNode->_left = Copy(root->_left);newNode->_right = Copy(root->_right);//我们这里有 _parent 所以每次我们都要记得修改parentif (newNode->_left)newNode->_left->_parent = newNode;if (newNode->_right)newNode->_right->_parent = newNode;return newNode;
}

九：全部代码

这里补充了刚才所说的方法。也方便大家运行测试。

这里先给出“RBTree.h”头文件：

#pragma once
#include<iostream>using namespace std;//定义颜色
enum Colour
{RED,   //红BLACK  //黑
};//定义树节点
template<class K, class V>
struct RBTreeNode
{//让编译器生成默认构造RBTreeNode() = default;//写一个构造RBTreeNode(const pair<K, V>& kv): _kv(kv){}pair<K, V> _kv;RBTreeNode* _left = nullptr;   RBTreeNode* _right = nullptr;RBTreeNode* _parent = nullptr;  //父节点Colour _col = RED;     //默认为红色
};template<class K, class V>
class RBTree
{
public://对RBTreeNode进行重命名using Node = RBTreeNode<K, V>;//默认构造RBTree() = default;//写一个拷贝构造RBTree(const RBTree<K, V>& t){_root = Copy(t._root);}//这里也不把Copy写成私有的了Node* Copy(Node* root){if (root == nullptr)return nullptr;//用前序遍历Node* newNode = new Node(root->_kv);//这里注意修改颜色newNode->_col = root->_col;newNode->_left = Copy(root->_left);newNode->_right = Copy(root->_right);//我们这里有 _parent 所以每次我们都要记得修改parentif (newNode->_left)newNode->_left->_parent = newNode;if (newNode->_right)newNode->_right->_parent = newNode;return newNode;}//重载=  这里省略& 也就相当于调用了拷贝构造RBTree& operator=(RBTree t){swap(_root, t._root);return *this;}//写析构~RBTree(){Destroy(_root);_root = nullptr;}//这里就不把Destroy写成私有了void Destroy(Node* root){//利用后序遍历if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}//插入bool Insert(const pair<K, V>& kv){if (_root == nullptr){Node* newNode = new Node(kv);_root = newNode;_root->_col = BLACK;  //更新根节点 并置为黑色return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{//已经存在该值了 不处理return false;}}//新建节点cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent; //记得更新父节点if (parent->_col == BLACK){return true;}else{while (parent && parent->_col != BLACK){//此时parent为红色Node* grandfather = parent->_parent;if (parent == grandfather->_left){//此时uncle为grandfather右孩子Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//uncle必须存在//将grandfather parent uncle 变色grandfather->_col = RED;uncle->_col = parent->_col = BLACK;//向上迭代cur = grandfather;parent = cur->_parent;}else{//此时要判断cur在parent的哪边if (cur == parent->_left){//最外面大条件为parent == grandfather->_left//所以此时是LL型 右旋RotateR(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}else{//在parent的右边//LR双旋 RotateL(parent);     //先左旋parentRotateR(grandfather);//后右旋grandfather//变色grandfather->_col = RED;cur->_col = BLACK; //注意是cur是最后旋转中心节点}//最后都要跳出循环break;}}else{//此时uncle为grandfather左孩子Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//将grandfather parent uncle 变色grandfather->_col = RED;uncle->_col = parent->_col = BLACK;//向上迭代cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather); //左旋//变色grandfather->_col = RED;parent->_col = BLACK;}else{//对parent右旋RotateR(parent);RotateL(grandfather); //对grandfather左旋//变色grandfather->_col = RED;cur->_col = BLACK;}break;}}}}//最后都时 _root->_col = BLACK 即可_root->_col = BLACK;return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first){cur = cur->_right;}else if (key < cur->_kv.first){cur = cur->_left;}else{return true;}}return false;}//获取树高int Height(){return _Height(_root);}//获取节点个数int Size(){return _Size(_root);}//中序遍历void Inorder(){_Inorder(_root);cout << endl;}//前序遍历void Preorder(){_Preorder(_root);cout << endl;}//判断是否为红黑树bool IsRBTree(){if (_root == nullptr)return true;if (_root->_col == RED)return false;//先统计黑色节点数量 因为有空指针也算黑色节点 所以初始化为1size_t len = 1;Node* cur = _root;while (cur){if (cur->_col == BLACK){++len;}cur = cur->_left; //沿着最左边路径走 统计黑色节点数量}return _IsRBTree(len, _root, 0); //第三个是其他路径黑色节点数量 }private:bool _IsRBTree(const size_t& len, Node* root, int tmp){if (root == nullptr){++tmp; //空节点算黑色节点 自增1if (tmp != len){cout << "违反黑路同性质！" << endl;return false;}return true;}if (root->_col == BLACK){++tmp;}//这里再判断是否违反不红红规则 一定是先判断当前节点是红色再去判断父节点//否则可能会遇到空指针异常if (root->_col == RED && root->_parent->_col == RED){cout << "违反不红红性质！" << endl;return false;}//之后遍历即可return _IsRBTree(len, root->_left, tmp) && _IsRBTree(len, root->_right, tmp);}void _Preorder(Node* root){if (!root)return;cout << root->_kv.first << " ";_Preorder(root->_left);_Preorder(root->_right);}void _Inorder(Node* root){if (!root)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}int _Size(Node* root){if (root == nullptr)return 0;int leftS = _Size(root->_left);int rightS = _Size(root->_right);return leftS + rightS + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}//旋转函数只会在类内调用 写成私有//右旋函数void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right; //记录冲突节点subL->_right = parent;parent->_left = subLR;      //冲突的右孩变左孩//冲突右孩存在 更改_parent指向if (subLR){subLR->_parent = parent;}//先判断有没有parent->_parentNode* parentP = parent->_parent; //先记录parent->_parent = subL;          //后更改if (parentP){//有父节点 判断parent在parentP的哪边if (parent == parentP->_left){parentP->_left = subL;}else{parentP->_right = subL;}subL->_parent = parentP;}else{//此时操作_root节点_root = subL;subL->_parent = nullptr;}}//左旋函数void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left; //记录冲突节点subR->_left = parent;parent->_right = subRL;      //冲突的左孩变右孩//冲突左孩存在 更改_parent指向if (subRL){subRL->_parent = parent;}//先判断有没有parent->_parentNode* parentP = parent->_parent; //先记录parent->_parent = subR;          //后更改if (parentP){//有父节点 判断parent在parentP的哪边if (parent == parentP->_left){parentP->_left = subR;}else{parentP->_right = subR;}subR->_parent = parentP;}else{//此时操作_root节点_root = subR;subR->_parent = nullptr;}}//一个_root成员变量即可Node* _root = nullptr;
};

之后就是“test.c”测试文件：

#include"RBTree.h"void test1()
{RBTree<int, int> t;//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };int a[] = { 17, 18, 23, 34, 27, 15, 9, 6, 8, 5, 25 };for (auto e : a){cout << e << " ";t.Insert({ e, e });}cout << endl;cout << t.IsRBTree() << endl;cout << "个数：" << t.Size() << " 高度：" << t.Height() << endl;cout << "前序遍历为：";t.Preorder();cout << endl << "中序遍历为：";t.Inorder();//测试Findcout << endl << "找17， 1就是找到了，结果为：" << t.Find(17) << endl;//测试拷贝构造RBTree<int, int> t1(t);if (t1.IsRBTree()){cout << "t1是平衡树" << endl;}else{cout << "t1不是平衡树" << endl;}RBTree<int, int> t2;t2.Insert({ 3,3 });t2 = t1;  //测试重载=if (t2.IsRBTree()){cout << "t2是平衡树" << endl;}else{cout << "t2不是平衡树" << endl;}
}int main()
{test1();return 0;
}

其中数组中的数据构建出的红黑树如下：

运行结果如下：

总结：

如果大家在此之前实现过作者之前的AVL树，会发现，这个红黑树的实现好像比它更简单，确实如此，我们之后会学习map和set，它们的底层都是红黑树，下一篇我会教大家实现如何使用我们的这颗红黑树代码实现map和set，内容非常劲爆，大家敬请期待！