C++_图解手撕红黑树的插入-查找-判断_KeyValue模型(三叉链)

admin • 2021-11-25 20:34 • C/C++

文章目录

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红黑树代码链接

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c++后端开发语言数据结构与算法

二维码

C语言每日一练——第62天：选美比赛

< <上一篇

)">

用c语言写三子棋游戏

下一篇>>

搜索内容