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

这篇具有很好参考价值的文章主要介绍了【C++杂货铺】一文带你走进RBTree。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++杂货铺】一文带你走进RBTree,C++杂货铺,c++,开发语言

一、红黑树的概念

红黑树是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,这句话换个意思就是:红黑树中最长路径不超过最短路径的 2 倍。因而是接近平衡的,而 AVL 树是严格平衡的,这就导致,红黑树的高度会比 AVL 树高一些,但是效率并不会比 AVL 树差。
【C++杂货铺】一文带你走进RBTree,C++杂货铺,c++,开发语言

二、红黑树的性质

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

  • 根节点是黑色。

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

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

  • 每个 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,那这次插入就没有什么问题。如果新插入结点是 parentRED,此时需要对这颗红黑树稍作调整。

四、红黑树的插入操作

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

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

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

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

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

4.1 情况一:uncle 存在且为红

【C++杂货铺】一文带你走进RBTree,C++杂货铺,c++,开发语言
小Tips:此处看到的树,可能是一颗完整的树,也可能是一颗子树。

解决方式:将 parentuncle 改为黑,grandp 改成红。然后把 grandp 当成 cur,继续向上调整。

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

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

【C++杂货铺】一文带你走进RBTree,C++杂货铺,c++,开发语言

4.2 情况二:uncle 不存在

如果 uncle 结点不存在,则 cur 一定是新插入结点,因为如果 cur 不是新插入结点,则 curparent 一定有一个结点的颜色是黑色,就不满足性质四:每条路径黑色结点个数相同。
【C++杂货铺】一文带你走进RBTree,C++杂货铺,c++,开发语言
解决方法:直接进行旋转即可。

4.3 情况三:uncle 存在且为黑

【C++杂货铺】一文带你走进RBTree,C++杂货铺,c++,开发语言
叔叔存在且为黑,那么 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 内核。

  • 其它一些库。

七、结语

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

【C++杂货铺】一文带你走进RBTree,C++杂货铺,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-713413.html

到了这里,关于【C++杂货铺】一文带你走进RBTree的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++杂货铺】模板

    📖 实现一个通用的交换函数 想要实现一个通用的交换函数不难,借助函数重载就可以。函数重载小伙伴们还记得嘛👀,忘了的小伙伴可以走传送门回去复习一下。如上面代码所示,我们借助函数重载实现了三份 Swap 函数,分别用来交换两个整型变量、两个双精度浮点型变量

    2024年02月09日
    浏览(44)
  • 【C++杂货铺】引用

    前言:  相信大家在学习C语言的时候,最头疼的就是指针,经常会碰到一级指针、二级指针,这些指针使用起来,稍有不慎就会等导致程序崩溃,为了让广大程序员少掉点头发,C++中提出了 引用 这一概念。当然,在C++的代码中,仍然可以兼容C语言的指针。  在语法上 引用

    2024年02月16日
    浏览(45)
  • 【C++杂货铺】内存管理

    从用途和存储的角度来看,在C/C++程序中有 局部数据、静态数据、全局数据、常量数据、动态申请的数据 五种主要的数据,各种数据的特点如下: 局部数据 :随用随创建,存储在栈区,作用域只在局部,生命周期在局部,出了作用域就销毁。 静态数据 :存储在数据段,作

    2024年02月16日
    浏览(37)
  • 【C++杂货铺】内管管理

    目录 🌈前言🌈 📁 C/C++中内存分布 📁 new 和 delete的使用 📁 new 和 delete的优点 📁 new 和 delete的原理  📂 operator new 和 operator delete函数  📂 内置类型  📂 自定义类型 📁 内存泄漏 📁 总结         欢迎收看本期【C++杂货铺】,本期内容讲解C++内存管理。包含了C++中内存

    2024年04月14日
    浏览(42)
  • 【C++杂货铺】详解string

    目录  🌈前言🌈 📁 为什么学习string 📁 认识string(了解) 📁 string的常用接口  📂 构造函数  📂 string类对象的容量操作  📂 string类对象的访问以及遍历操作​编辑  📂 string类对象的修改操作 📁 模拟实现string 📁 总结         欢迎观看本期【C++杂货铺】,本期内容

    2024年03月20日
    浏览(41)
  • 【C++杂货铺】拷贝构造函数

    📖 定义 拷贝构造函数 是构造函数的一个重载 ,它的本质还是 构造函数 ,那就意味着,只有在创建对象的时候,编译器才会自动调用它,那他和普通的构造函数有什么区别呢? 拷贝构造函数,是创建对象的时候,用一个已存在的对象,去初始化待创建的对象 。简单来说,

    2024年02月16日
    浏览(46)
  • 【C++杂货铺】运算符重载

    本文将以日期类为基础,去探寻运算符重载的特性与使用方法,下面先给出日期类的基础定义: 备注 :拷贝构造函数和析构函数,均可以不写,因为当前日期类的三个成员变量都是内置类型,没有动态申请空间,使用浅拷贝就可以。 📖 如何比较两个日期的大小? 现如今,

    2024年02月16日
    浏览(68)
  • 【C++杂货铺】缺省参数、函数重载

     缺省参数是 声明或定义函数时为函数的参数指定一个缺省值 。在调用该函数时,如果没有指定实参则采用该形参的缺省值,否则使用指定的实参。  上面代码在 fun 函数的形参部分给了缺省值10,这意味着在调用 fun 函数的时候可以传参,也可以不传参,如果传参了那形参

    2024年02月16日
    浏览(37)
  • 【C++杂货铺】详解list容器

    目录 🌈前言🌈 📁 介绍 📁 使用  📂 构造  📂 迭代器iterator  📂 capacity  📂 modifiers  📂 迭代器失效 📁 模拟实现  📂 迭代器的实现 📂 代码展示 📁 和vector的区别 📁 总结         欢迎收看本期【C++杂货铺】,本期内容将讲解STL中关于list的内容,会分为一下几个方

    2024年04月14日
    浏览(48)
  • 【C++杂货铺】C++介绍、命名空间、输入输出

     C语言是 结构化 和 模块化 的语言,适合处理 较小规模 的程序。对于复杂的问题,规模较大的程序,需要高度的抽象和建模时,C语言则不合适。为了解决软件危机,20世纪80年代,计算机界提出了 OOP (object oriented programming: 面向对象 )思想,支持面向对象的程序设计语言应

    2024年02月16日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包