C++之红黑树模拟实现

news/2024/12/26 6:26:32 标签: 开发语言, c++

目录

红黑树的概念

红黑树的性质

红黑树的查找效率

红黑树的实现 

红黑树的定义

红黑树节点的插入

红黑树的平衡调整

判断红黑树是否平衡 

红黑树整体代码 

测试代码

上期我们学习了AVL树的模拟实现，在此基础上，我们本期将学习另一个数据结构------红黑树。我们知道，AVL树的插入伴随着节点的旋转，那么红黑树是否在插入节点时也要进行旋转呢？这便是我们本期要学习的内容。

红黑树的概念

红黑树和AVL树一样，也是一种二叉搜索树，红黑树的每一个节点存储一个数据，表示该节点的颜色，为红色或者黑色。通过红黑树的性质作为约束，红黑树的最长路径的长度不会超过最短路径长度的二倍。红黑树图示如下。

红黑树的性质

  1. 红黑树的节点，不是红色就是黑色。
  2. 红黑树的根节点一定是黑色的。
  3. 红黑树中，如果一个节点是红色的，那么它的孩子节点一定是黑色的。（也就是说，红黑树中不能出现连续的两个红色节点）
  4. 红黑树的任意一个节点到其所有叶子节点的所有路径上的黑色节点的个数一定是相同的。
  5. 红黑树的叶子节点一定是黑色的。（这个叶子节点不是传统意义的叶子节点，而是如上图所示的NIL空节点）

 Q1:为什么通过红黑树的上述性质作为约束，能够保证红黑树的最长路径的长度不超过最短路径长度的2倍呢？

A1:其实决定上述条件的是红黑树性质中的3和4条。假设红黑树的每个路径的黑色节点的个数是4，极端情况下，红色树的最短路径就是4个黑色节点，最长路径就是1黑1红，总共4组，8个节点，所以就可以推出，红黑树的最长路径的长度不超过最短路径长度的2倍。

红黑树的查找效率与AVL树的比较

再学习AVL树时，我们知道了AVL树理想条件下其实就是一颗完全二叉树，所以对于有N个节点的完全二叉树，它的高度为logN，所以对于AVL树而言，它的查找效率是logN。

对于红黑树而言，假设红黑树的每条路径的黑色节点的个数为X，所以红黑树的高度h的范围为X<=h<=2X。假设红黑树的节点的个数为N，则N的范围为2^X-1<=N<=2^2X-1,从而得到X的取值范围为1/2logN<=X<=logN。所以对于具有N个节点的红黑树而言，红黑树的高度最高为2logN，红黑树也是搜索二叉树，所以红黑树的查找效率为2logN。

通过上述比较，不难看出，红黑树的查找效率远不及AVL树，所以我们应该是经常使用AVL树的。嗯？真的是我们想的这样吗，真的是AVL树的使用更为广泛吗？

实际上并不是这样，AVL树的查找效率固然很高，但是查找效率高的同时带来的代价也是很大的，因为AVL是高度平衡的二叉树，有时候插入一个元素往往需要旋转多次，但是对于红黑树而言，只要插入的节点的颜色不违反红黑树的性质，我们是不用进行旋转的。我们可以认为，AVL树和红黑树在插入节点时，AVL树中插入节点更容易违反性质，所以AVL插入元素时旋转的概率是远远比红黑树要高的，所以即使AVL树的查找效率更高，但是对于以数亿次运算的CPU看来，logN和2logN几乎是没有差异的，所以一般情况下，我们应用红黑树的场景更多。

红黑树的实现 

红黑树的定义

代码如下。

//枚举类型，代表红黑树节点的颜色。
enum Colour
{
	RED,
	BLACK
};


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(const pair<K, V>& kv)
		 :_left(nullptr)
		 ,_right(nullptr)
		 ,_parent(nullptr)
		 ,_kv(kv)
		 ,_col(RED)
	 {}

};


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


private:
	Node* _root;

};

红黑树节点的插入

查找合适的位置进行节点的插入，代码如下。

//如果当前红黑树为空，则直接插入即可
		if (_root == nullptr)
		{
			_root = new Node(pair);
			_root->_col = BLACK;
			return true;
		}

		//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入
		Node* cur = _root;
		Node* parent = _root->_parent;
		while (cur)
		{
			if (cur->_kv.first > pair.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < pair.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
				printf("插入的节点的值已经存在于红黑树中，不允许插入!\n");
			}
		}
		cur = new Node(pair);
		cur->_col = RED;
		cur->_parent = parent;
		if (cur->_kv.first > parent->_kv.first)
		{
		 parent->_right= cur ;
	
		}
		else
		{
		 parent->_left= cur ;
		}

红黑树的平衡调整

在插入一个结点时，为了对整个红黑树的影响最小，一般我们插入的都是红色节点。但是在插入红色节点时，可能会遇到很多情景，大致分为三种。

我们将插入的节点称为cur节点，将cur节点的父亲称为parent节点，将cur节点的叔叔称为uncle节点，将cur节点的祖父称为grandfather节点。在此基础上我们展开分析。

情景1：uncle节点存在且为红。

代码如下。 

情景2和3，uncle节点存在为黑色或者uncle节点不存在。

 代码如下。

	while (parent&& parent->_col == RED)
		{

			Node* grandfather = parent->_parent;
			//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡
			if (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
				{
			//2.叔叔节点不存在
			//3.叔叔节点的颜色为黑色
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}

			}
			else
			{
				Node* uncle = grandfather->_right;
				if (uncle&& uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//2.叔叔节点不存在
					//3.叔叔节点的颜色为黑色
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}
			}

判断红黑树是否平衡 

代码如下。

bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout<<"根节点的颜色是红色，不符合红黑树的性质";
			return false;
		}
		
		int banchmark = 0;
		//选取最左侧的路径的黑色节点的个数为基准值
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				banchmark++;
			}
				left = left->_left;
		 }

		int blackcount = 0;
		return _IsBalance(_root, banchmark, blackcount);
	}

	bool _IsBalance(Node* root, int banchmark, int blackcount)
	{
		if (root == nullptr)
		{
			if (banchmark != blackcount)
			{
				return false;
			}
			
				return  true;
			
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
		cout<<"出现两个连续的红节点，不符和红黑树的性质" << endl;
		return false;
		}
		if (root->_col == BLACK)
		{
			blackcount++;
		}

		return _IsBalance(root->_left, banchmark, blackcount) && _IsBalance(root->_right,banchmark, blackcount);
	}

红黑树整体代码 

 红黑树实现代码如下。

#include<time.h>
#include<iostream>
#include<vector>
using namespace std;

enum Colour
{
	RED,
	BLACK
};


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(const pair<K, V>& kv)
		 :_left(nullptr)
		 ,_right(nullptr)
		 ,_parent(nullptr)
		 ,_kv(kv)
		 ,_col(RED)
	 {}

};


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


	//红黑树节点的插入
	bool Insert(const pair<K, V>& pair)
	{
		//如果当前红黑树为空，则直接插入即可
		if (_root == nullptr)
		{
			_root = new Node(pair);
			_root->_col = BLACK;
			return true;
		}

		//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入
		Node* cur = _root;
		Node* parent = _root->_parent;
		while (cur)
		{
			if (cur->_kv.first > pair.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < pair.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
				printf("插入的节点的值已经存在于红黑树中，不允许插入!\n");
			}
		}
		cur = new Node(pair);
		cur->_col = RED;
		cur->_parent = parent;
		if (cur->_kv.first > parent->_kv.first)
		{
		 parent->_right= cur ;
	
		}
		else
		{
		 parent->_left= cur ;
		}
		

		//调整平衡
	
		while (parent&& parent->_col == RED)
		{

			Node* grandfather = parent->_parent;
			//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡
			if (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
				{
			//2.叔叔节点不存在
			//3.叔叔节点的颜色为黑色
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}

			}
			else
			{
				Node* uncle = grandfather->_right;
				if (uncle&& uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//2.叔叔节点不存在
					//3.叔叔节点的颜色为黑色
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}
			}

			
		}

		//强制性的让根节点为黑色，符合红黑树的性质
		_root->_col = BLACK;
		return true;


	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		Node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;
			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}
	}


	void InOrder()
	{
		_InOrder(_root);
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

private:
	Node* _root;

};

测试代码

void TestRBTree()
{
	RBTree<int, int> t;
	vector<int> v;
	srand(time(0));
	int N = 10;
	for (int i = 0; i < N; ++i)
	{
		v.push_back(rand());
	}

	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	
	}
	t.InOrder();
	cout<< t.IsBalance() << endl;

}

运行结果如下。

运行结果符合预期。 

以上便是红黑树的所有内容，较于AVL树，红黑树的应用较为广泛，后续的容器map和set以及哈希结构都是使用红黑树实现的。这些都是我们下几期要重点研究的。 

本期内容到此结束^_^

 


http://www.niftyadmin.cn/n/5799952.html

相关文章

推动开源数据生态：SeaTunnel ByConity技术沙龙精彩回顾

推动开源数据生态：SeaTunnel ByConity技术沙龙精彩回顾

2024年12月15日&#xff0c;Apache SeaTunnel 和 ByConity 社区联合举办的主题为「探索数据生态协同创新」的技术沙龙在万胜广场C塔圆满落幕。 本次活动吸引了超过50位开发者、数据工程师和企业用户参与&#xff0c;技术交流氛围热烈&#xff0c;共同探讨了数据集成与仓库优化的…
阅读更多...
【机器学习】机器学习的基本分类-半监督学习（Semi-supervised Learning）

【机器学习】机器学习的基本分类-半监督学习（Semi-supervised Learning）

半监督学习是一种介于监督学习和无监督学习之间的机器学习方法。它利用少量的标注数据&#xff08;有监督数据&#xff09;和大量的未标注数据&#xff08;无监督数据&#xff09;来进行模型训练&#xff0c;从而在标注数据不足的情况下&#xff0c;提升模型的性能。 半监督学习…
阅读更多...
5.银河麒麟V10(ARM) 离线安装redis

5.银河麒麟V10(ARM) 离线安装redis

系统版本 [rootga-sit-cssjgj-db-01u ~]# nkvers ############## Kylin Linux Version ################# Release: Kylin Linux Advanced Server release V10 (Lance)Kernel: 4.19.90-52.39.v2207.ky10.aarch64Build: Kylin Linux Advanced Server release V10 (SP3) /(Lance…
阅读更多...
Flask使用的正例和反例

Flask使用的正例和反例

Flask使用的正例和反例 文章目录 Flask使用的正例和反例一 &#xff0c; 使用注册异常二 &#xff0c; 新增数据成功后要返回新增数据的id三&#xff0c; 模型查询语句抽取成函数四&#xff0c; 业务逻辑函数传递的参数不应该用字典类型&#xff0c;要传不同字段的参数&#xf…
阅读更多...
linux-21 文件管理(一）mkdir命令，创建空目录

linux-21 文件管理(一）mkdir命令，创建空目录

对linux而言&#xff0c;对一个系统管理来讲&#xff0c;最关键的还是文件管理。那所以我们接下来就来看看如何实现文件管理。当然&#xff0c;在文件管理之前&#xff0c;我们说过&#xff0c;文件通常都放在目录下&#xff0c;对吧&#xff1f;所以先了解目录&#xff0c;可能…
阅读更多...
Linux复习3——管理文件系统2

Linux复习3——管理文件系统2

修改文件权限命令 chmod 功能&#xff1a; chmod 命令主要用于修改文件或者目录的权限 只有文件所有者和超级用户可以修改文件或目录的权限 (1)使用数字表示法修改权限 所谓数字表示法是指将读取(r)、写入(w)和执行(x)分别以4、2、1来表示&#xff0c;没有授予的部分就表示…
阅读更多...
centos制作离线安装包

centos制作离线安装包

目录 1.yumdownloader与repotrack怎么选择&#xff1f; yumdownloader --resolve repotrack 总结 2.环境准备 3.安装 1.yumdownloader与repotrack怎么选择&#xff1f; yumdownloader --resolve 和 repotrack 都是与 YUM&#xff08;Yellowdog Updater Modified&#xf…
阅读更多...
学习笔记（C#基础书籍）-- C#基础篇

学习笔记（C#基础书籍）-- C#基础篇

&#xff08;12.24&#xff09; C#介绍&#xff1a;《第一章》 特点&#xff1a;语法简洁&#xff0c;面向对象&#xff0c;支持绝大部分的web标准&#xff0c;强大的安全机制&#xff08;垃圾回收器&#xff09;&#xff0c;兼容性好&#xff08;遵循.NET的公共语言规范【CL…
阅读更多...
最新文章

Copyright @ 2022~2023