【C++】模拟实现红黑树

修修修也

发布于 2024-10-03 09:38:01

13200

代码可运行

文章被收录于专栏：修也的进阶日记修也的进阶日记

运行总次数：0

代码可运行

一.了解项目功能

在本次项目中我们的目标是实现一个红黑树类模板,还不了解红黑树概念的朋友可以先移步[【数据结构】什么是红黑树(Red Black Tree)?]其结构图示如下:

红黑树结点(RBTreeNode)需要包含五个成员:键值对_kv, 左指针域_left, 右指针域_right, 父亲指针域_parent, 颜色标识_col.结点(RBTreeNode)逻辑结构图示如下:

红黑树类模板提供的功能有:

红黑树结点类的构造函数
红黑树的构造函数
红黑树的插入函数
左单旋函数
右单旋函数
判断红黑树是否符合红黑树规则函数

二.逐步实现项目功能模块及其逻辑详解

通过第二部分对项目功能的介绍，我们已经对的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！

！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。

📌实现RBTreeNode类模板

🎏构造RBTreeNode类成员变量

我们在一开始需求分析时就已经明确了红黑树结点(RBTreeNode)需要包含五个成员:键值对_kv, 左指针域_left, 右指针域_right, 父亲指针域_parent, 颜色标识_col.结点(RBTreeNode)逻辑结构图示如下:

对于颜色标识符,我们可以设置一个枚举来标识红色和黑色,增加代码的可读性:

enum Colour
{
	RED,
	BLACK
};

这里还有一个小的点需要提一下,我们在这里实现的RBTreeNode类,后续是要给RBTree类使用的,考虑到后续我们在红黑树的操作函数中会有直接操作结点成员变量的情况,如:

cur->_left = root->_right; //相当于在RBTreeNode外部直接通过类指针访问了类成员变量_left

基于class的封装特性,class的成员变量一般都是默认为私有的,如果我们要允许其他类直接访问class的成员变量和函数,就要将其都设置为public,或者通过友元/内部类来解决成员访问问题.

既然如此,我们不妨直接使用struct定义结点成员变量和函数,因为struct定义的类的成员变量和函数默认就是公有的,完全可以满足我们的需求.

综上所述,该部分代码如下:

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;
};

🎏实现RBTreeNode类构造函数

RBTreeNode的构造函数我们实现两个即可,一个是有参构造,一个是无参构造,而无参构造又可以通过给缺省值的方式和有参构造合二为一,所以我们用初始化列表来实现一下RBTreeNode的构造函数(我在红黑树的概念中已经分析过为什么新插入的结点一定是红色,这里就不多赘述了):

//缺省值的作用是在无参调用时直接去调用模板实例化的类的无参构造函数
//这里一定不能将缺省值给0/nullptr!因为你不知道模板实例化的类具体到底是内置类型还是自定义类型(如Date)
//所以要显示调用pair<K,V>类型它自己的无参构造函数

RBTreeNode(const pair<K,V>& kv=pair<K,V>())
	:_left(nullptr)
	,_right(nullptr)
	,_parent(nullptr)
	,_kv(kv)
	,_col(RED)
{}

📌实现RBTree类模板

🎏构造RBTree类成员变量

RBTree类成员变量比较简单,就是一个根节点的指针,为了简化模板中出现的RBTreeNode<K,V>类型的名字,我们将其简化命名为:Node

该部分实现代码如下:

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K,V> Node;

private:
	Node* _root;
};

🎏实现RBTree类构造函数

RBTree类的构造函数非常简单,因为只有一个成员变量根节点指针_root,所以我们用初始化列表将该结点指针初始话为nullptr即可,代码如下:

RBTree()
	:_root(nullptr)
{}

🎏实现RBTree插入函数

RBTree类的插入函数实现思路如下:

如果我们遇到了插入后违反红黑树规则的情况,那么红黑树的调整规则如下:

插入结点是根节点(即破坏了根节点是黑色的规则)--->解决方法,直接将该节点变黑
插入结点的父节点也是红色(即破坏了红结点的孩子必须是黑色的规则),分两种情况
插入结点的叔叔结点是红色: 将叔叔和父亲变为黑色, 爷爷结点变为红色, 然后继续向上判定爷爷结点是否违反了红黑树的规则并进行调整
插入结点的叔叔结点不存在或是黑色: 根据形态进行相应的旋转操作,旋转完成后,将旋转后的根节点变黑,将祖父结点变红即可

综上所述,红黑树的插入函数代码实现如下:

bool Insert(const pair<K, V>& kv)
{
    //前期的插入逻辑就是二叉搜索树的插入逻辑
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
    //找插入位置
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			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;

	//控制红黑树的特性...控制颜色
	//插入的永远是红结点
	//插入的是根,把结点变红
	//插入时父节点是黑,就ok了

	//插入的父节点是红,看叔叔
	//	叔叔是红,把父亲叔叔都变黑,把爷爷变红(然后继续向上处理)
	//	叔叔是黑,旋转,转完父爷都变色

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

        //因为我们在红黑树中不用平衡因子但是要判断是LL/RR/LR/RL型的旋转,因此需要在这里分情况讨论
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			
            //叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				//变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续向上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else//叔叔不存在或存在且为黑,就旋转
			{
				if (cur == parent->_left)
				{
					RotateR(grandfather);
					//转完换色
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					RotateL(parent);
					RotateR(grandfather);
					//转完换色
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
			}
		}
		else//parent == grandfather->_right
		{
			Node* uncle = grandfather->_left;
				
			if (uncle && uncle->_col == RED)
			{
				//变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续向上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_left)
				{
					RotateR(parent);
					RotateL(grandfather);
					//改色
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					RotateL(grandfather);

					//祖父一定是红色,父子谁最后旋到根谁变黑
									  //单旋父黑,双旋子黑
					//单旋爷变子,双旋子变父
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
			}
		}
	}

	_root->_col = BLACK;

	return true;
}

🎏实现RBTree插入左单旋(和AVL树一样)

左单旋处理应用的情况为:

插入结点是父亲结点的右孩子
父亲结点是爷爷结点的右孩子

左单旋的处理操作步骤为:

将父亲结点的左子树链接到爷爷结点的右孩子的位置
将爷爷链接到父亲结点的左孩子位置

综上,实现代码及详解如下:

    //左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		Node* ppnode = parent->_parent;

		//将失衡结点右孩子的左子树链接到失衡结点的右孩子
		parent->_right = curleft;
		if (curleft)
		{
			curleft->_parent = parent;
		}

		//将失衡结点连接到失衡结点右孩子的左孩子位置
		parent->_parent = cur;
		cur->_left = parent;

		//处理父父结点的链接
		cur->_parent = ppnode;
		if (ppnode == nullptr)//为空代表parent就已经是root了
		{
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)//失衡结点是其父节点的左孩子
			{
				ppnode->_left = cur;
			}
			else       //失衡结点是其父节点的右孩子
			{
				ppnode->_right = cur;
			}
		}
	}

🎏实现RBTree插入右单旋(和AVL树一样)

右单旋处理应用的情况为:

插入结点是父亲结点的左
父亲结点是爷爷结点的左

右单旋的处理操作步骤为:

将父亲结点的右子树链接到爷爷结点的左孩子的位置
将爷爷结点链接到父亲结点的右孩子位置

综上,实现代码及详解如下:

    //右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		Node* ppnode = parent->_parent;

		//将失衡结点左孩子的右子树连接到失衡结点的左孩子位置
		parent->_left = curright;
		if (curright)
		{
			curright->_parent = parent;
		}

		//将失衡结点连接到失衡结点左孩子的右孩子位置
		parent->_parent = cur;
		cur->_right = parent;

		//链接父父结点
		cur->_parent = ppnode;
		if (ppnode == nullptr)//为空代表parent就已经是root了
		{
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
		}

	}

🎏判断红黑树是否符合红黑树规则函数

判断一棵树是不是红黑树,就要从红黑树的几个规则出发,看其是否满足下面这几个规则:

每个结点不是红色就是黑色
根结点是黑色
如果一个结点是红色的,则它的子结点一定是黑色
任一结点到NULL(树尾)的任何路径上,所含的黑色结点数一定相同
每个NULL(树尾)空结点都是黑色的

综上,实现代码如下:

//检查结点是否满足没有连续的两个红结点,以及所有路径的黑节点数量都相同函数
bool CheckColour(Node* root, int blacknum, int benchmark)
{
	if (root == nullptr)
	{
		if (benchmark != blacknum)
			return false;

		return true;
	}
    //计算路径黑节点数量
	if (root->_col == BLACK)
	{
		++blacknum;
	}

    //如果一个结点是红色,它的父亲也是红色,那就违反了没有两个连续红结点的规则
	if (root->_col == RED && root->_parent && root->_parent->_col == RED)
	{
		cout << root->_kv.first << "连续红结点" << endl;
		return false;
	}

	return CheckColour(root->_left,blacknum,benchmark)
		&& CheckColour(root->_right,blacknum,benchmark);
}


//RBTree验证函数递归子函数
bool _IsBalance(Node* root)
{
	if (root == nullptr)
		return true;

	//规则:根节点是黑色
	if (root->_col != BLACK)
		return false;

	//求黑节点基准值(用左路的黑节点数量来计算)
	int benchmark = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
			benchmark++;
		cur = cur->_left;
	}

	//规则:不能有连续的红结点,且每条路径黑节点数量相同
	return CheckColour(root, 0, benchmark);
}

//RBTree验证函数(嵌套的目的是为了方便传参)
bool IsBalance()
{
	return _IsBalance(_root);
}

三.项目完整代码

我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:

test.c文件

该文件主要包含一些对AVL树的功能测试代码,大家可以酌情参考或自己编写测试用例:

#include"RBTree.h"

void test1()
{
	int a[] = { 16,3,7,11,9,26,18,14,15 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
		cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
}

void test2()
{
	int a[] = { 14, 9, 5, 17, 11, 12, 7, 19, 16, 27 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
		cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
}

void test3()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
		cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
}

//随机数暴力测试
void test4()
{
	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());
	}
	cout << "数据录入完毕,开始插入" << endl;
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	cout << t.IsBalance() << endl;
	t.InOrder();
	cout << "插入结束" << endl;
}

int main()
{
	test4();

	return 0;
}

RBTree.h文件

#pragma once

#include<iostream>
#include<vector>
using namespace std;

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K,V>& kv=pair<K,V>())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	Colour _col;
};


template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K,V> Node;
public:
	RBTree()
		:_root(nullptr)
	{}

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)//查了半天是这里少写了个循环...(好在自己查到了,去比对了一下,果然...加上就好了
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				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;

		//...控制颜色
		//插入的永远是红结点
		//插入的是根,把结点变红
		//插入时父节点是黑,就ok了

		//插入的父节点是红,看叔叔
		//	叔叔是红,把父亲叔叔都变黑,把爷爷变红(然后继续向上处理)
		//	叔叔是黑,旋转,转完父爷都变色

		while ( parent && parent->_col == RED && parent->_parent)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else//叔叔不存在或存在且为黑,就旋转
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						//转完换色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						//转完换色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
				}
			}
			else//parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(parent);
						RotateL(grandfather);
						//改色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(grandfather);

						//祖父一定是红色,父子谁最后旋到根谁变黑
										//单旋父黑,双旋子黑
						//单旋爷变子,双旋子变父
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
				}
			}
		}

		_root->_col = BLACK;

		return true;
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		Node* ppnode = parent->_parent;

		//将失衡结点右孩子的左子树链接到失衡结点的右孩子
		parent->_right = curleft;
		if (curleft)
		{
			curleft->_parent = parent;
		}

		//将失衡结点连接到失衡结点右孩子的左孩子位置
		parent->_parent = cur;
		cur->_left = parent;

		//处理父父结点的链接
		cur->_parent = ppnode;
		if (ppnode == nullptr)//为空代表parent就已经是root了
		{
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)//失衡结点是其父节点的左孩子
			{
				ppnode->_left = cur;
			}
			else       //失衡结点是其父节点的右孩子
			{
				ppnode->_right = cur;
			}
		}
	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		Node* ppnode = parent->_parent;

		//将失衡结点左孩子的右子树连接到失衡结点的左孩子位置
		parent->_left = curright;
		if (curright)
		{
			curright->_parent = parent;
		}

		//将失衡结点连接到失衡结点左孩子的右孩子位置
		parent->_parent = cur;
		cur->_right = parent;

		//链接父父结点
		cur->_parent = ppnode;
		if (ppnode == nullptr)//为空代表parent就已经是root了
		{
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
		}

	}



	//中序遍历函数
	void InOrder()
	{
		_InOrder(_root);  //代替成员函数完成递归
		cout << endl;       //方便后续观察测试用例
	}
	//中序遍历子递归函数
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);       //递归访问左子树
		cout << root->_kv.first << " ";   //访问根节点
		_InOrder(root->_right);      //递归访问右子树
	}

	//验证双红结点和路径黑结点数是否相同函数
	bool CheckColour(Node* root, int blacknum, int benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark != blacknum)
				return false;

			return true;
		}

		if (root->_col == BLACK)
		{
			++blacknum;
		}


		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "连续红结点" << endl;
			return false;
		}

		return CheckColour(root->_left,blacknum,benchmark)
			&& CheckColour(root->_right,blacknum,benchmark);
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}


	//RBTree验证函数
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		//规则:根节点是黑色
		if (root->_col != BLACK)
			return false;

		//求黑节点基准值
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				benchmark++;
			cur = cur->_left;
		}


		//规则:不能有连续的红结点,且每条路径黑节点数量相同
		return CheckColour(root, 0, benchmark);
	}


private:
	Node* _root;
};