【C++杂货铺】一文带你走进RBTree

news/2024/7/24 8:36:44 标签: c++, 开发语言

在这里插入图片描述

文章目录

  • 一、红黑树的概念
  • 二、红黑树的性质
  • 三、红黑树结点的定义
  • 四、红黑树的插入操作
    • 4.1 情况一：uncle 存在且为红
    • 4.2 情况二：uncle 不存在
    • 4.3 情况三：uncle 存在且为黑
    • 4.4 插入完整源码
  • 五、红黑树的验证
  • 六、红黑树与 AVL 树的比较
  • 七、结语

一、红黑树的概念

红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，这句话换个意思就是：红黑树中最长路径不超过最短路径的 2 倍。因而是接近平衡的，而 AVL 树是严格平衡的，这就导致，红黑树的高度会比 AVL 树高一些，但是效率并不会比 AVL 树差。
在这里插入图片描述

二、红黑树的性质

  • 每个结点不是红色就是黑色。

  • 根节点是黑色。

  • 如果一个结点是红色，则它的两个孩子结点必须是黑色的。

  • 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

  • 每个 NIL 叶子结点都是黑色的（此处的叶子结点指的是空节点）。

小Tips：第三点决定了一颗红黑树的任何路径没有连续的红色结点。在红黑树中计算路径一定是计算到 NIL 结点。一颗红黑树中的最短路径是全为黑结点的路径，最长路径是一黑一红相间的路径。任意一条路径上黑色结点的占比一定是大于等于 1 / 2 1/2 1/2 的。这就决定了，红黑树中其最长路径中结点个数不会超过最短路径结点个数的两倍。

三、红黑树结点的定义

//红黑树的结点
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode(const& pair<K, V> kv = pair<K, V>(), Color color = RED)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(color)
	{}

	pair<K, V> _kv;//结点中存的值
	RBTreeNode<K, V>* _left;//结点的左孩子
	RBTreeNode<K, V>* _right;//结点的右孩子
	RBTreeNode<K, V>* _parent;//结点的父亲
	Color _col;//结点的颜色
};

小Tips：新节点默认颜色是 RED。这是因为，如果新插入结点的颜色是 BLACK，那意味着当前路径上新增了一个黑色结点，为了保证二叉树的第四条性质，我们要对这颗红黑树其他的所有路径进行检查，可见新插入结点如果默认是 BLACK，会存在着牵一发而动全身的影响。而让新插入结点默认是 RED 则不会出现这样的结果。假如新插入结点的 parent 恰好是 BLACK，那这次插入就没有什么问题。如果新插入结点是 parent 是 RED，此时需要对这颗红黑树稍作调整。

四、红黑树的插入操作

红黑树是在二叉搜索树的基础上加上平衡限制条件，因此红黑树的插入可以分为两步：

  • 按照二叉搜索树的规则插入结点。

  • 检测新节点插入后，红黑树的性质是否遭到破坏。

因为新结点的默认颜色是 RED，因此：如果其双亲结点的颜色是 BLACK，没有违反红黑树任何性质，则不需要调整；但是当新插入节点的双亲结点颜色为 RED 时，就违反了性质三不能有连在一起的红色结点，此时需要对红黑树分情况来讨论：

约定：cur为当前结点，parent 为父结点，grandp 为祖父结点，uncle 为叔叔结点。如果 parent 为红那 grandp 一定为黑。所以当前唯一不确定的就是 uncle，主要分以下三种情况

4.1 情况一：uncle 存在且为红

在这里插入图片描述
小Tips：此处看到的树，可能是一颗完整的树，也可能是一颗子树。

解决方式：将 parent 和 uncle 改为黑，grandp 改成红。然后把 grandp 当成 cur，继续向上调整。

  • 如果 grandp 是根结点，将 grandp 再改成黑色，本次插入就算结束。

  • 如果 grandp 是子树，则其一定也有双亲，且 grandp 的双亲如果是红色，需要继续向上调整。

在这里插入图片描述

4.2 情况二：uncle 不存在

如果 uncle 结点不存在，则 cur 一定是新插入结点，因为如果 cur 不是新插入结点，则 cur 和 parent 一定有一个结点的颜色是黑色，就不满足性质四：每条路径黑色结点个数相同。
在这里插入图片描述
解决方法：直接进行旋转即可。

4.3 情况三：uncle 存在且为黑

在这里插入图片描述
叔叔存在且为黑，那么 cur 一定不是新插入的结点，并且 cur 结点原来的颜色一定是黑色，现在看到是红色的原因是因为 cur 的子树在调整的过程中将 cur 结点的颜色由黑色改成了红色。

4.4 插入完整源码

public:
	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 (kv.first < cur->_kv.first)//小于往左走
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)//大于往右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else//相等插入不了
			{
				return false;
			}
		}

		//找到待插入位置了，进行插入
		cur = new Node(kv);
		cur->_col = RED;
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		cur->_parent = parent;

		//检测新结点插入后，红黑树的性质是否遭到破坏
		while (parent && parent->_col == RED)
		{
			Node* grandp = parent->_parent;
			if (parent == grandp->_left)
			{
				Node* uncle = grandp->_right;
				if (uncle && uncle->_col == RED)//叔叔存在且为红
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandp->_col = RED;

					//继续向上处理
					cur = grandp;
					parent = cur->_parent;
				}
				else //uncle不存在或者存在为黑
				{
					if (cur == parent->_left)
					{
						RotateR(grandp);
						parent->_col = BLACK;//parent当了根
						grandp->_col = RED;
					}
					else if (cur == parent->_right)
					{
						RotateLR(grandp);
						cur->_col = BLACK;//cur当了根节点
						grandp->_col = RED;
					}

					break;
				}
			}
			else if (parent == grandp->_right)
			{
				Node* uncle = grandp->_left;
				if (uncle && uncle->_col == RED)//叔叔存在且为红
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandp->_col = RED;

					//继续向上处理
					cur = grandp;
					parent = cur->_parent;
				}
				else //uncle不存在或者存在为黑
				{
					if (cur == parent->_right)
					{
						RotateL(grandp);
						parent->_col = BLACK;//parent当了根
						grandp->_col = RED;
					}
					else if (cur == parent->_left)
					{
						RotateRL(grandp);
						cur->_col = BLACK;//cur当了根节点
						grandp->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;//根结点始终变黑
		return true;
	}
private:
	//左单旋
	void RotateL(Node* parent)
	{
		++_rotatecount;
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		parent->_right = curleft;
		cur->_left = parent;

		if (curleft)
		{
			curleft->_parent = parent;
		}

		Node* ppnode = parent->_parent;
		parent->_parent = cur;

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

	}

	//右单旋
	void RotateR(Node* parent)
	{
		++_rotatecount;
		Node* cur = parent->_left;
		Node* curright = cur->_right;//此时的情况是curright比cur大，比parent小

		parent->_left = curright;
		cur->_right = parent;

		if (curright)
		{
			curright->_parent = parent;
		}

		Node* ppnode = parent->_parent;
		parent->_parent = cur;

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

	//右左双旋
	void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		RotateR(parent->_right);
		RotateL(parent);

	}

	//左右双旋
	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;

		RotateL(cur);
		RotateR(parent);

	}

五、红黑树的验证

红黑树的检测分为两步：

  • 检测其是否满足二叉搜索树（中序遍历是否为有序序列）。

  • 检测其是否满足红黑树的性质（主要是性质三和性质四）。

public:
	bool Isblance()
	{
		if (_root == nullptr)
			return true;

		//根节点如果不是黑色说明就不是红黑树
		if (_root->_col != BLACK)
		{
			return false;
		}

		//计算红黑树中任意一条路径上黑色结点的个数作为一个基准值
		Node* cur = _root;
		int count = 0;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++count;
			}
			cur = cur->_left;
		}

		return CheckColour(_root, 0, count);
	}
private:
	//检查颜色
	bool CheckColour(Node* root, int blacknum, int stand)
	{
		if (root == nullptr)
		{
			//到这里说明一条路径结束，那么这条路径上的黑色结点数也一定统计出来了
			if (blacknum != stand)
			{
				cout << "当前路径上黑色结点的个数有问题" << endl;
				return false;
			}

			return true;
		}

		//检查是否出现连续的红色结点
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << ":为红色节点，并且孩子结点也是红色" << endl;
		}

		//统计一条路径上黑色结点个数
		if (root->_col == BLACK)
		{
			++blacknum;
		}

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

六、红黑树与 AVL 树的比较

红黑树和 AVL 树都是高效的平衡二叉树，增删查改的时间复杂度都是 O ( l o g 2 N ) O(log2^N) O(log2N)，红黑树不追求绝对平衡，其只需要保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入过程中旋转的次数，所以在经常进行增删查改的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。红黑树主要会应用在以下几个地方：

  • C++ STL 库----map、set、mutilmap、mutilset。

  • Java 库。

  • Linux 内核。

  • 其它一些库。

七、结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，春人的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！

在这里插入图片描述


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

相关文章

docker拉取镜像错误 missing signature key

docker拉取镜像错误 missing signature key

您正在尝试使用 yum 在 CentOS 或 RHEL 系统上安装 docker-ce&#xff0c;但您遇到了一些问题。根据您提供的输出&#xff0c;这里有几个需要注意的点&#xff1a; 系统未注册: "This system is not registered with an entitlement server" 指示您的系统未注册。对于…
阅读更多...
Unity_相机灵活跟随角色移动

Unity_相机灵活跟随角色移动

每日一句&#xff1a;慢慢改变&#xff0c;慢慢成长&#xff0c;慢慢适应&#xff0c;慢慢优秀 目录 角色旋转、移动类 相机跟随人物移动类 角色旋转、移动类 /*旋转刚体&#xff0c;位移的动画驱动移动*/ using System.Collections;using System.Collections.Generic;using…
阅读更多...
UEFI之DXE阶段

UEFI之DXE阶段

一、DXE阶段介绍 DXE&#xff08;Driver Execution Environment&#xff09;阶段执行大部分系统初始化工作&#xff0c;进入此阶段时&#xff0c;内存已经可以被完全使用&#xff0c;因而此阶段可以进行大量的复杂工作。 DXE可以分为以下两部分&#xff1a; DXE内核&#xff…
阅读更多...
Python字典全解析：从基础到高级应用

Python字典全解析：从基础到高级应用

更多资料获取 &#x1f4da; 个人网站&#xff1a;涛哥聊Python 字典是一种强大而多才多艺的数据类型&#xff0c;它以键-值对的形式储存信息&#xff0c;让我们能够以惊人的效率处理和管理数据。 字典能够将键和值关联在一起&#xff0c;使得数据的存储和检索变得非常高效。…
阅读更多...
css 写带三角形的对话框，空心的三角形边框

css 写带三角形的对话框，空心的三角形边框

首先&#xff0c;我们要会先实现一个小三角形&#xff1b; 思路&#xff1a;利用元素的 border 属性&#xff0c;将其三个方向的 border-color 值设为透明色&#xff08;或者和其父元素的背景色一致&#xff0c;形成视觉差&#xff0c;俗称障眼法&#xff09;&#xff0c;剩下…
阅读更多...
OSPF的原理与配置

OSPF的原理与配置

第1章 OSPF[1] 本章阐述了OSPF协议的特征、术语&#xff0c;OSPF的路由器类型、网络类型、区域类型、LSA类型&#xff0c;OSPF报文的具体内容及作用&#xff0c;描述了OSPF的邻居关系&#xff0c;通过实例让读者掌握OSPF在各种场景中的配置。 本章包含以下内容&#xff1a; …
阅读更多...
git push 错误

git push 错误

错误信息 git push origin HEAD:refs/for/master Enumerating objects: 256, done. Counting objects: 100% (256/256), done. Delta compression using up to 4 threads Compressing objects: 100% (225/225), done. Writing objects: 100% (255/255), 5.86 MiB | 18.98 MiB/…
阅读更多...
AI视频监控平台EasyCVR接入海康SDK出现异常，该如何解决？

AI视频监控平台EasyCVR接入海康SDK出现异常，该如何解决？

安防监控系统/视频集中存储/云存储/视频监控管理平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;实现视频资源的鉴权管理、按需调阅、全网分发、智能分析等。 有用户反馈&#xff0c;在使用视频监控系统EasyCVR接入…
阅读更多...
最新文章

Copyright @ 2022~2023