[数据结构与算法] C++_图解手撕红黑树的插入-查找-判断

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> C++_图解手撕红黑树的插入-查找-判断_KeyValue模型(三叉链) -> 正文阅读

[数据结构与算法]C++_图解手撕红黑树的插入-查找-判断_KeyValue模型(三叉链)

文章目录

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;
}