文章目录
- 1.红黑树概念
- 红黑树的性质
- 2.红黑树KV模型
- 3.红黑树的插入
- ①p是g左子树 cur为红，p为红，g为黑，u存在且为红
- ②p是g的左子树 cur为红，p为红，g为黑，u不存在/u为黑(cur,p,g为一条直线)_单旋
- ③p是g的左子树 cur为红，p为红，g为黑，u不存在/u为黑(cur,p,g为折线)_双旋
- ④p是g的右子树 cur为红，p为红，g为黑，u存在且为红
- ⑤p是g的右子树 cur为红，p为红，g为黑，u不存在/u为黑(cur,p,g是一条直线)_单旋
- ⑥p是g的右子树 cur为红，p为红，g为黑，u不存在/u为黑(cur,p,g为折线)_双旋
- 红黑树的插入代码
- 4.判断一棵树是否是红黑树
- 5.红黑树通过键值key查找节点
- 6.红黑树的打印
- 7.红黑树的析构函数
- 8.红黑树插入，查找，判断完整代码
- 9.测试红黑树
- 10.代码链接
1.红黑树概念
先看AVL树：
AVL树为高度平衡二叉搜索树
AVL树插入的实现
再看红黑树：
红黑树也是二叉搜索树。但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
- 每个空节点都是黑色的。
保证上述性质后，红黑树就确保没有一条路径会比其他路径长出2倍。
原因：假设一条路径上黑色节点为3个。这颗树最短路径为全黑色3，最长路径为黑红交替6。最长路径正好为最短路径的二倍，正好符合红黑树结构。
2.红黑树KV模型
基本结构
#pragma once
#include<iostream>
using namespace std;
enum Color
{
RED = 0, BLACK,
};
template<class Key, class Value>
struct RBTreeNode
{
RBTreeNode<Key, Value>* _left;
RBTreeNode<Key, Value>* _right;
RBTreeNode<Key, Value>* _parent;
pair<Key, Value> _kv;
Color col;
RBTreeNode(const pair<Key, Value>& val)
:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(val), col(RED)//默认节点颜色
{}
};
template<class Key,class Value>
class RBTree
{
typedef RBTreeNode<Key, Value> Node;
public:
RBTree() :_root(nullptr) {}
pair<Node*, bool>Insert(const pair<Key, Value>val);//红黑树的插入
private:
Node* _root;
};
3.红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
- 按照二叉搜索的树规则插入新节点。
- 修改节点颜色，保持红黑树特性
情况一： 红黑树为空，此时插入时创建一个节点，并将节点的颜色改为黑色。
pair<Node*, bool>Insert(const pair<Key, Value>val)//红黑树的插入
{
if (_root == nullptr)
{
_root = new Node(val);
_root->col = BLACK;
return make_pair(_root, true);
}
情况二：
1.红黑树不为空，首先遍历红黑树，找到要插入的位置。同时找是否有重复的节点，如果发现有重复的节点插入失败，返回这个位置的指针和false。为了实现三叉链，还要一个parent指针指向cur的上一个节点
//二叉搜索树插入
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_kv.first < val.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > val.first)
{
parent = cur;
cur = cur->_left;
}
else//键值重复,插入失败
{
return make_pair(cur, false);
}
}
2.上面这个函数结束后，此时cur就指向nullptr，parent指向要连接的上一个位置
cur创建一个新的红色节点，根据二叉搜索树特性，还要判断cur节点和parent节点值的大小，如果cur节点值小于parent插入到parent节点的左边，否则插入到parent节点的右边。
cur = new Node(val);
cur->col = RED;
if (parent->_kv.first > val.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
3.到这里，节点的插入就算完成了，我们还要调整红黑树的节点颜色，让其符合红黑树的规则。在这之前记录插入节点的位置，方便返回pair值
其次是调整红黑树颜色
为了方便描述，记录四个节点的名称cur，parent，uncle，grandparent节点，这四者位置入下图所示，简称c p u g
如果插入的parent是黑色，不需要调整树的颜色，插入完成。
插入的parent是红色，两个红色连续。需要处理
①p是g左子树 cur为红，p为红，g为黑，u存在且为红
根据上图可以写出代码
while (parent != nullptr && parent->col == RED)//停止条件看上图分析
{
Node* GradParent = parent->_parent;//记录gradparent节点
if (parent == GradParent->_left)//关键看Uncle节点的颜色
{
Node* Uncle = GradParent->_right;
//情况1：Uncle存在且为红
if (Uncle && Uncle->col == RED)
{
parent->col = Uncle->col = BLACK;
GradParent->col = RED;
cur = GradParent;//循环向上判断
parent = cur->_parent;
}
}
else//parent=GradParent->_right
{
......
}
}
_root->col = BLACK;//将根的颜色变为黑色，防止上面的过程将根节点变为红色
return make_pair(End, true);
②p是g的左子树 cur为红，p为红，g为黑，u不存在/u为黑(cur,p,g为一条直线)_单旋
首先：出现这种情况时，cur一定不是新插入的节点。一定是在情况一向上调整颜色时出现的
理由：
处理方式：
根据上面的分析，我们可以写出如下代码
pair<Node*, bool>Insert(const pair<Key, Value>val)//红黑树的插入
{
if (_root == nullptr)
{
_root = new Node(val);
_root->col = BLACK;
return make_pair(_root, true);
}
//二叉搜索树插入
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_kv.first < val.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > val.first)
{
parent = cur;
cur = cur->_left;
}
else//键值重复,插入失败
{
return make_pair(cur, false);
}
}
cur = new Node(val);
cur->col = RED;
if (parent->_kv.first > val.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
Node* End = cur;//记录插入位置的节点
//控制路径
while (parent != nullptr && parent->col == RED)
{
Node* GradParent = parent->_parent;
if (parent == GradParent->_left)//关键看Uncle节点的颜色
{
Node* Uncle = GradParent->_right;
//情况1：Uncle存在且为红
if (Uncle && Uncle->col == RED)
{
parent->col = Uncle->col = BLACK;
GradParent->col = RED;
cur = GradParent;
parent = cur->_parent;
}
else//Uncle不存在或Uncle存在为黑色
{
if (cur == parent->_left)//右高，进行右旋
{
_Single_Right(GradParent);
GradParent->col = RED;
parent->col = BLACK;
}
break;//旋转后黑色节点个数不变，直接跳出循环
}
else//parent=GradParent->_right
{
......
}
}
_root->col = BLACK;//将根的颜色变为黑色，防止情况一最后到根上跳出根变成红色
return make_pair(End, true);
}
右单旋代码与AVL树的右旋转类似，根据下图旋转图写出代码即可
void _Single_Right(Node* parent)//右单旋根据图把对应关系连接起来
{
//记录要移动的节点
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
//连接
parent->_left = SubLR;
if (SubL->_right != nullptr)//修改父指针
{
SubLR->_parent = parent;
}
//连接
SubL->_right = parent;
Node* GradParent = parent->_parent;//记录这个节点的父节点，为了修改根节点
parent->_parent = SubL;//修改父指针
//调整根节点
if (parent == _root)//要旋转的节点为根节点
{
_root = SubL;
SubL->_parent = GradParent;
}
else//要旋转的节点是子树，修改GradParent指针
{
if (GradParent->_left == parent)
{
GradParent->_left = SubL;
}
else
{
GradParent->_right = SubL;
}
SubL->_parent = GradParent;
}
}
③p是g的左子树 cur为红，p为红，g为黑，u不存在/u为黑(cur,p,g为折线)_双旋
处理方式：
根据上图写出代码
pair<Node*, bool>Insert(const pair<Key, Value>val)//红黑树的插入
{
if (_root == nullptr)
{
_root = new Node(val);
_root->col = BLACK;
return make_pair(_root, true);
}
//二叉搜索树插入
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_kv.first < val.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > val.first)
{
parent = cur;
cur = cur->_left;
}
else//键值重复,插入失败
{
return make_pair(cur, false);
}
}
cur = new Node(val);
cur->col = RED;
if (parent->_kv.first > val.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
Node* End = cur;//记录插入位置的节点
//控制路径
while (parent != nullptr && parent->col == RED)
{
Node* GradParent = parent->_parent;
if (parent == GradParent->_left)//关键看Uncle节点的颜色
{
Node* Uncle = GradParent->_right;
//情况1：Uncle存在且为红
if (Uncle && Uncle->col == RED)
{
parent->col = Uncle->col = BLACK;
GradParent->col = RED;
cur = GradParent;
parent = cur->_parent;
}
else//Uncle不存在或Uncle存在为黑色
{
if (cur == parent->_left)//右高，进行右旋
{
_Single_Right(GradParent);
GradParent->col = RED;
parent->col = BLACK;
}
else//折线形状，左右双旋
{
_Single_Left(parent);
_Single_Right(GradParent);
cur->col = BLACK;
parent->col = GradParent->col = RED;
}
break;//旋转后黑色节点个数不变，直接跳出循环
}
else//parent=GradParent->_right
{
......
}
}
_root->col = BLACK;//将根的颜色变为黑色，防止上面的过程将根节点变为红色
return make_pair(End, true);
}
左单旋与AVL树的左单旋类似，旋转原理与右单旋图片相同，不在赘述
void _Single_Left(Node* parent)//左旋转
{
//记录要移动的节点
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
//连接
parent->_right = SubRL;
if (SubRL != nullptr)
{
SubRL->_parent = parent;
}
SubR->_left = parent;
Node* GradParent = parent->_parent;//记录这个节点的父节点，为了修改根节点
parent->_parent = SubR;
//调整根节点
if (parent == _root)
{
_root = SubR;
SubR->_parent = GradParent;
}
else //要旋转的节点是子树，修改GradParent指针
{
if (GradParent->_left == parent)//旋转的是左子树，连接到左边
{
GradParent->_left = SubR;
}
else
{
GradParent->_right = SubR;//反之
}
SubR->_parent = GradParent;
}
}
④p是g的右子树 cur为红，p为红，g为黑，u存在且为红
这种情况与①相同，不在赘述
⑤p是g的右子树 cur为红，p为红，g为黑，u不存在/u为黑(cur,p,g是一条直线)_单旋
⑥p是g的右子树 cur为红，p为红，g为黑，u不存在/u为黑(cur,p,g为折线)_双旋
根据上图可以写出红黑树插入的下半逻辑
红黑树的插入代码
pair<Node*, bool>Insert(const pair<Key, Value>val)//红黑树的插入
{
if (_root == nullptr)
{
_root = new Node(val);
_root->col = BLACK;
return make_pair(_root, true);
}
//二叉搜索树插入
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_kv.first < val.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > val.first)
{
parent = cur;
cur = cur->_left;
}
else//键值重复,插入失败
{
return make_pair(cur, false);
}
}
cur = new Node(val);
cur->col = RED;
if (parent->_kv.first > val.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
Node* End = cur;//记录插入位置的节点
//控制路径
while (parent != nullptr && parent->col == RED)
{
Node* GradParent = parent->_parent;
if (parent == GradParent->_left)//关键看Uncle节点的颜色
{
Node* Uncle = GradParent->_right;
//情况1：Uncle存在且为红
if (Uncle && Uncle->col == RED)
{
parent->col = Uncle->col = BLACK;
GradParent->col = RED;
cur = GradParent;
parent = cur->_parent;
}
else//Uncle不存在或Uncle存在为黑色
{
if (cur == parent->_left)//右高，进行右旋
{
_Single_Right(GradParent);
GradParent->col = RED;
parent->col = BLACK;
}
else//折线形状，左右双旋
{
_Single_Left(parent);
_Single_Right(GradParent);
cur->col = BLACK;
parent->col = GradParent->col = RED;
}
break;//旋转后黑色节点个数不变，直接跳出循环
}
}
else//parent=GradParent->_right
{
Node* Uncle = GradParent->_left;
if (Uncle != nullptr && Uncle->col == RED)
{
Uncle->col = parent->col = BLACK;
GradParent->col = RED;
cur = GradParent;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//左高，左旋
{
_Single_Left(GradParent);
GradParent->col = RED;
parent->col = BLACK;
}
else//折线,右左双旋
{
_Single_Right(parent);
_Single_Left(GradParent);
cur->col = BLACK;
GradParent->col = RED;
}
break;
}
}
}
_root->col = BLACK;//将根的颜色变为黑色，防止第一种情况循环到根节点跳出循环根节点变红色
return make_pair(End, true);
}
//私有:旋转代码
void _Single_Right(Node* parent)//右单旋根据图把对应关系连接起来
{
//记录要移动的节点
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
//连接
parent->_left = SubLR;
if (SubL->_right != nullptr)//修改父指针
{
SubLR->_parent = parent;
}
//连接
SubL->_right = parent;
Node* GradParent = parent->_parent;//记录这个节点的父节点，为了修改根节点
parent->_parent = SubL;//修改父指针
//调整根节点
if (parent == _root)//要旋转的节点为根节点
{
_root = SubL;
SubL->_parent = GradParent;
}
else//要旋转的节点是子树，修改GradParent指针
{
if (GradParent->_left == parent)
{
GradParent->_left = SubL;
}
else
{
GradParent->_right = SubL;
}
SubL->_parent = GradParent;
}
}
void _Single_Left(Node* parent)//左旋转
{
//记录要移动的节点
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
//连接
parent->_right = SubRL;
if (SubRL != nullptr)
{
SubRL->_parent = parent;
}
SubR->_left = parent;
Node* GradParent = parent->_parent;//记录这个节点的父节点，为了修改根节点
parent->_parent = SubR;
//调整根节点
if (parent == _root)
{
_root = SubR;
SubR->_parent = GradParent;
}
else //要旋转的节点是子树，修改GradParent指针
{
if (GradParent->_left == parent)//旋转的是左子树，连接到左边
{
GradParent->_left = SubR;
}
else
{
GradParent->_right = SubR;//反之
}
SubR->_parent = GradParent;
}
}
4.判断一棵树是否是红黑树
bool CheckRBTree()
{
if (_root == nullptr)
{
return true;
}
else if(_root->col == RED)
{
cout << "根节点为红" << endl;
return false;
}
//先记录最左节点黑的数量，拿这个数量作为基准检查其他路
int NumBack = 0;
Node* LeftBack = _root;
while (LeftBack != nullptr)
{
if (LeftBack->col == BLACK)
{
NumBack++;
}
LeftBack = LeftBack->_left;
}
int Num = 0;//检查其他路的黑节点个数的变量
return _CheckRBTree(_root, NumBack, Num);
}
//私有:
bool _CheckRBTree(Node* root, const int NumBack, int Num)
{
if (root == nullptr)//为空表示遍历到红黑树的最底端，跳出循环的条件
{
//检测这条路上黑节点个数和NumBack
if (NumBack != Num)
{
cout << "黑色节点个数不相同" << endl;
return false;
}
else
{
return true;
}
}
//前序遍历
if (root->col == RED && root->_parent->col == RED)
{
cout << "红色节点连续" << endl;
return false;
}
else if (root->col == BLACK)
{
Num++;
}
return _CheckRBTree(root->_left, NumBack, Num) && _CheckRBTree(root->_right, NumBack, Num);
}
5.红黑树通过键值key查找节点
遍历一遍红黑树即可，就是简单的二叉搜索树的查找，不在赘述
Node* Find(const Key& key)//通过键值查找,返回节点指针
{
Node* cur = _root;
Node* ret = nullptr;
while (cur != nullptr)
{
if (key > cur->_kv.first)
{
cur = cur->_right;
}
else if (key < cur->_kv.first)
{
cur = cur->_left;
}
else
{
ret = cur;
break;
}
}
return ret;
}
6.红黑树的打印
中序打印红黑树
void PrintInord()
{
return _PrintInord(_root);
}
//私有:
void _PrintInord(Node* root)//中序打印
{
if (root == nullptr)
return;
_PrintInord(root->_left);
cout << root->_kv.first << "->" << root->_kv.second << endl;
_PrintInord(root->_right);
}
7.红黑树的析构函数
后序遍历析构
~RBTree()
{
_Destory(_root);//后序遍历
_root = nullptr;
}
//私有:
void _Destory(Node* root)//后序遍历
{
if (root == nullptr)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
8.红黑树插入，查找，判断完整代码
#pragma once
#include<iostream>
using namespace std;
enum Color
{
RED = 0, BLACK,
};
template<class Key, class Value>
struct RBTreeNode
{
RBTreeNode<Key, Value>* _left;
RBTreeNode<Key, Value>* _right;
RBTreeNode<Key, Value>* _parent;
pair<Key, Value> _kv;
Color col;
RBTreeNode(const pair<Key, Value>& val)
:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(val), col(RED)//默认节点颜色
{}
};
template<class Key, class Value>
class RBTree
{
typedef RBTreeNode<Key, Value> Node;
public:
RBTree() :_root(nullptr) {}
~RBTree()
{
_Destory(_root);//后序遍历
_root = nullptr;
}
bool CheckRBTree()
{
if (_root == nullptr)
{
return true;
}
else if(_root->col == RED)
{
cout << "根节点为红" << endl;
return false;
}
//先记录最左节点黑的数量
int NumBack = 0;
Node* LeftBack = _root;
while (LeftBack != nullptr)
{
if (LeftBack->col == BLACK)
{
NumBack++;
}
LeftBack = LeftBack->_left;
}
int Num = 0;//记录此时黑节点的个数
return _CheckRBTree(_root, NumBack, Num);
}
Node* Find(const Key& key)//通过键值查找,返回节点指针
{
Node* cur = _root;
Node* ret = nullptr;
while (cur != nullptr)
{
if (key > cur->_kv.first)
{
cur = cur->_right;
}
else if (key < cur->_kv.first)
{
cur = cur->_left;
}
else
{
ret = cur;
break;
}
}
return ret;
}
//打印红黑树
void PrintInord()
{
return _PrintInord(_root);
}
pair<Node*, bool>Insert(const pair<Key, Value>val)//红黑树的插入
{
if (_root == nullptr)
{
_root = new Node(val);
_root->col = BLACK;
return make_pair(_root, true);
}
//二叉搜索树插入
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_kv.first < val.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > val.first)
{
parent = cur;
cur = cur->_left;
}
else//键值重复,插入失败
{
return make_pair(cur, false);
}
}
cur = new Node(val);
cur->col = RED;
if (parent->_kv.first > val.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
Node* End = cur;//记录插入位置的节点
//控制路径
while (parent != nullptr && parent->col == RED)
{
Node* GradParent = parent->_parent;
if (parent == GradParent->_left)//关键看Uncle节点的颜色
{
Node* Uncle = GradParent->_right;
//情况1：Uncle存在且为红
if (Uncle && Uncle->col == RED)
{
parent->col = Uncle->col = BLACK;
GradParent->col = RED;
cur = GradParent;
parent = cur->_parent;
}
else//Uncle不存在或Uncle存在为黑色
{
if (cur == parent->_left)//右高，进行右旋
{
_Single_Right(GradParent);
GradParent->col = RED;
parent->col = BLACK;
}
else//折线形状，左右双旋
{
_Single_Left(parent);
_Single_Right(GradParent);
cur->col = BLACK;
parent->col = GradParent->col = RED;
}
break;//旋转后黑色节点个数不变，直接跳出循环
}
}
else//parent=GradParent->_right
{
Node* Uncle = GradParent->_left;
if (Uncle != nullptr && Uncle->col == RED)
{
Uncle->col = parent->col = BLACK;
GradParent->col = RED;
cur = GradParent;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//左高，左旋
{
_Single_Left(GradParent);
GradParent->col = RED;
parent->col = BLACK;
}
else//折线,右左双旋
{
_Single_Right(parent);
_Single_Left(GradParent);
cur->col = BLACK;
GradParent->col = RED;
}
break;
}
}
}
_root->col = BLACK;//将根的颜色变为黑色，防止上面的过程将根节点变为红色
return make_pair(End, true);
}
private:
Node* _root;
void _PrintInord(Node* root)
{
if (root == nullptr)
return;
_PrintInord(root->_left);
cout << root->_kv.first << "->" << root->_kv.second << endl;
_PrintInord(root->_right);
}
bool _CheckRBTree(Node* root, const int NumBack, int Num)
{
if (root == nullptr)
{
//检测这条路上黑节点个数和NumBack
if (NumBack != Num)
{
cout << "黑色节点个数不相同" << endl;
return false;
}
else
{
return true;
}
}
//前序遍历
if (root->col == RED && root->_parent->col == RED)
{
cout << "红色节点连续" << endl;
return false;
}
else if (root->col == BLACK)
{
Num++;
}
return _CheckRBTree(root->_left, NumBack, Num) && _CheckRBTree(root->_right, NumBack, Num);
}
void _Destory(Node* root)//后序遍历
{
if (root == nullptr)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
void _Single_Right(Node* parent)//右单旋根据图把对应关系连接起来
{
//记录要移动的节点
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
//连接
parent->_left = SubLR;
if (SubL->_right != nullptr)//修改父指针
{
SubLR->_parent = parent;
}
//连接
SubL->_right = parent;
Node* GradParent = parent->_parent;//记录这个节点的父节点，为了修改根节点
parent->_parent = SubL;//修改父指针
//调整根节点
if (parent == _root)//要旋转的节点为根节点
{
_root = SubL;
SubL->_parent = GradParent;
}
else//要旋转的节点是子树，修改GradParent指针
{
if (GradParent->_left == parent)
{
GradParent->_left = SubL;
}
else
{
GradParent->_right = SubL;
}
SubL->_parent = GradParent;
}
}
void _Single_Left(Node* parent)//左旋转
{
//记录要移动的节点
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
//连接
parent->_right = SubRL;
if (SubRL != nullptr)
{
SubRL->_parent = parent;
}
SubR->_left = parent;
Node* GradParent = parent->_parent;//记录这个节点的父节点，为了修改根节点
parent->_parent = SubR;
//调整根节点
if (parent == _root)
{
_root = SubR;
SubR->_parent = GradParent;
}
else //要旋转的节点是子树，修改GradParent指针
{
if (GradParent->_left == parent)//旋转的是左子树，连接到左边
{
GradParent->_left = SubR;
}
else
{
GradParent->_right = SubR;//反之
}
SubR->_parent = GradParent;
}
}
};
9.测试红黑树
#include"RBTree.h"//红黑树的头文件
#include<stdlib.h>
#include<time.h>
void Test()//测试插入打印红黑树，判断红黑树
{
int arr[] = { 3,2,5,1,7,11,6,15 };
RBTree<int, int>t;
for (const auto& e : arr)
{
t.Insert(make_pair(e, e));
}
t.PrintInord();
if (t.CheckRBTree())
{
cout << "Is RedBlackTree" << endl;
}
else
{
cout << "Is Not RedBlackTree" << endl;
}
}
//随机插入红黑树
void Test2()
{
int n = 20;
RBTree<int, int>t;
srand((unsigned int)time(0));
for (int i = 0; i < n; i++)
{
int tmp = rand();
t.Insert(make_pair(tmp,tmp));
}
t.PrintInord();
if (t.CheckRBTree())
{
cout << "Is RedBlackTree" << endl;
}
else
{
cout << "Is Not RedBlackTree" << endl;
}
}
int main()
{
Test();
Test2();
return 0;
}
运行结果为：
10.代码链接
gitee红黑树代码链接