C++之红黑树

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

红黑树的概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
C++之红黑树,c++,开发语言

红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

为什么红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍?

从性质3,4可以得出,一棵红黑树的最短可能路径就是全为黑结点,即为N:
C++之红黑树,c++,开发语言
而最长可能路径就是由一黑一红结点构成的路径,该路径当中黑色结点与红色结点的数目相同,即长度为2N ;
C++之红黑树,c++,开发语言

红黑树结点的定义

红黑树结点的定义其实和AVL树差不多,只不过红黑树结点少了平衡因子,多了颜色。

//枚举结点颜色
enum color
{
	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;

	//结点颜色
	color _col;

	//构造函数
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};

为什么构造结点时,默认将结点的颜色设置为红色?

我们可以发现,红黑树的有一条性质是所有路径黑色结点的数目都相等,如果欧姆尼新插入的结点默认为黑色,就会破坏这条性质,我们就需要对红黑树进行调整。

如果我们插入的是红结点,此时如果父结点是红结点,我们就需要进行调整,如果父结点是黑结点,我们就不需要进行调整。

红黑树的插入

红黑树的插入步骤分为以下三步:

  1. 根据二叉搜索树的性质,找到待插入位置;
  2. 在待插入位置插入新结点;
  3. 如果父结点为红色,就进行调整。

我们可以发现,前两步其实AVL树没有区别,我们只要在第三步进行调整就可以了。

那么,怎么对红黑树插入结点进行调整呢?

如果我们插入结点的父结点是黑色的,我们就不需要进行任何调整,因为这并没有破坏红黑树的性质;如果我们插入结点的父结点是红结点,我们就需要对红黑树进行调整了。

插入结点的父结点为红色,就说明祖父结点一定存在且为黑色,对红黑树的调整主要是对叔叔结点的调整。

红黑树的调整一共分为三种方式:

1.cur为红,p为红,g为黑,u存在且为红

C++之红黑树,c++,开发语言
插入结点为红,父结点为红,我们需要将父结点与叔叔结点都调整为黑色,然后将祖父结点调整为红色,如果此时g这棵树不为子树,就再将祖父结点调整为黑色;

对应的抽象图如下:
C++之红黑树,c++,开发语言
如果g不为子树,最后将g调整为黑色就完成了红黑树的调整;
C++之红黑树,c++,开发语言
如果g为子树,一次调整以后g还有双亲,双亲如果是红色,将p,u改为黑,g改为红,然后把g当成cur,继续向上调整,还要继续向上调整。

2.cur为红,p为红,g为黑,u不存在/u存在且为黑,p为g的左孩子,cur为p的左孩子或者p为g的右孩子,cur为g的右孩子

我们均已被插入结点在根结点左侧为例:

如果u节点不存在,则cur一定是新插入节点,因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色,就不满足性质:每条路径黑色节点个数相同。
C++之红黑树,c++,开发语言
此时我们只需要以p为旋转点进行右单旋,然后进行颜色调整即可:
C++之红黑树,c++,开发语言
当u存在且为黑时:

此时一定是情况一向上调整才会出现的情况,这种情况下cur不会是新插入的结点,是经过前一次调整以后的结点:
C++之红黑树,c++,开发语言
我们以新插入结点在a的左侧为例:
C++之红黑树,c++,开发语言

此时我们以g为旋转点进行右单旋,然后进行颜色调整,红黑树即可平衡;

同样,如果被插入结点在根结点右侧,我们只需要进行相应左旋在调整颜色即可实现红黑树平衡;

抽象图如下:

被插入结点在根结点左侧:
C++之红黑树,c++,开发语言
被插入结点在根结点右侧:
C++之红黑树,c++,开发语言

3.cur为红,p为红,g为黑,u不存在/u存在且为黑,p为g的左孩子,cur为p的右孩子或者p为g的右孩子,cur为p的左孩子

u不存在时:
C++之红黑树,c++,开发语言

当u存在且为黑时,我们以下面这种情况为例:
C++之红黑树,c++,开发语言
我们先已p为轴点进行左单旋,再以g为轴点进行右单旋,最后进行颜色调整,红黑树保持平衡;

抽象图如下:

被插入结点在根结点左侧:
C++之红黑树,c++,开发语言
被插入结点在根结点右侧:
C++之红黑树,c++,开发语言
代码实现:

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)
	{
		//如果插入key值小于根结点key值
		if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		//如果插入key值大于根结点key值
		else if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		//相等,返回false
		else
		{
			return false;
		}
	}

	//创建cur结点
	cur = new Node(kv);
	//颜色初始化为红色
	cur->_col = RED;

	//如果插入key值小于parent结点key值
	if (parent->_kv.first > kv.first)
	{
		//在左边插入
		parent->_left = cur;
	}
	//如果插入key值大于parent结点key值
	else
	{
		//在右边插入
		parent->_right = cur;
	}
	//跟父结点连接起来
	cur->_parent = parent;

	while (parent && parent->_col == RED)
	{
		//定义祖父节点
		Node* grandfather = parent->_parent;
		assert(grandfather);
		assert(grandfather->_col == BLACK);

		//如果父结点在祖父节点左边
		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);
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				//插入结点在父结点左边
				else
				{
					//左右双旋+颜色调整
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
		//如果父结点在祖父节点右边
		else
		{
			//定义叔叔结点在祖父结点左边
			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->_right)
				{
					//左单旋+颜色调整
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				//插入结点在父结点左边
				else
				{
					//右左双旋+颜色调整
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
	}
	//根结点变为黑色
	_root->_col = BLACK;
	return true;
}

红黑树的验证

我们可以判断每条路径的黑节点数量是否相等来判断该二叉树是否为红黑树:

void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

bool IsBalance()
{
	//如果根结点为空,返回true;
	if (_root == nullptr)
	{
		return true;
	}
	//如果根结点为红色,则返回false;
	if (_root->_col == RED)
	{
		cout << "根结点不是黑色" << endl;
		return false;
	}
	//定义一个黑色结点数量的基准值,为最左边路径黑色结点数量
	int benchmark = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			benchmark++;
		}
		cur = cur->_left;
	}
	//黑色结点数量
	int BlackNum = 0;
	return PrevCheck(_root, BlackNum, benchmark);
}
bool PrevCheck(Node* root, int BlackNum, int benchmark)
{
	//说明此时路径已经走完了
	if (root == nullptr)
	{
		//如果基准值不等于黑色结点数量,返回false
		if (benchmark != BlackNum)
		{
			cout << " 某条黑色结点数量不相等" << endl;
			return false;
		}
		//否则返回true
		return true;
	}
	//根结点为黑色,黑色结点数量++
	if (root->_col == BLACK)
	{
		BlackNum++;
	}
	//存在连续红色节点,返回false
	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << "存在连续的红色结点" << endl;
		return false;
	}
	//递归进行判断
	return PrevCheck(root->_left, BlackNum, benchmark)
		&& PrevCheck(root->_right, BlackNum, benchmark);
}

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(log N),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单。文章来源地址https://www.toymoban.com/news/detail-704168.html

到了这里,关于C++之红黑树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

    今天,带来无数人的噩梦——红黑树的讲解。文中不足错漏之处望请斧正! 如果还没看过AVLTree讲解的一定要去看看,看完才能更好理解红黑树! 红黑树是自平衡的二叉搜索树。 红黑树的规则: 每个结点非黑即红 根结点为黑 叶子结点为黑(此处的叶子结点指空结点) 不能有

    2024年02月07日
    浏览(42)
  • C++中的红黑树

    搜索二叉树的概念:二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 简单

    2024年02月09日
    浏览(43)
  • C++【红黑树】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎃操作环境: Visual Studio 2019 版本 16.11.17 红黑树是平衡二叉搜索树中的一种,红黑树性能优异,广泛用于实践中,比如 Linux 内核中的 CFS 调度器就用到了红黑树,由此可见红黑树的重要性。红黑树在实现时仅仅依靠 红 与 黑 两

    2024年02月10日
    浏览(33)
  • 【C++】红黑树

    正文开始前给大家推荐个网站,前些天发现了一个巨牛的 人工智能 学习网站, 通俗易懂,风趣幽默 ,忍不住分享一下给大家。 点击跳转到网站。 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的

    2024年01月16日
    浏览(44)
  • C++ 实现红黑树

    红黑树 ,是一种二叉搜索树,但 在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black 。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍 ,因而是 接近平衡 的。 红黑树的性质 每个结点不是红色就

    2024年02月05日
    浏览(39)
  • C++红黑树

    前置说明: 需要学习AVL树的旋转之后再来看红黑树的旋转 因为红黑树的旋转是复用的AVL树的旋转的: 大家可以看我的这篇博客,里面详细介绍了AVL树的四种旋转 C++ AVL树(四种旋转,插入) 对于颜色我们采用枚举类型定义 对于红黑树节点,依旧采用Key-Value模型存储pair 1.共识 首先我们

    2024年02月04日
    浏览(36)
  • 【C++】实现红黑树

    红黑树是一个二叉搜索树,与AVL树相比,红黑树不再使用平衡因子来控制树的左右子树高度差,而是用颜色来控制平衡,颜色为红色或者黑色。控制任意一条从根到叶子节点的路径的节点颜色,就可以确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 红黑树的规

    2024年03月25日
    浏览(39)
  • C++手撕红黑树

    概念 和AVL树一样,红黑树也是一种二叉搜索树,是解决二叉搜索树不平衡的另一种方案,他在每个节点上增加一个存储位,用于表示节点的颜色,是Red或者Black 红黑树的核心思想是通过一些着色的条件限制,达到一种最长路径不超过最短路径的两倍的状态 所以说红黑树并不

    2024年04月12日
    浏览(41)
  • 【C++】手撕红黑树

    作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等 座右铭:松树千年终是朽,槿花一日自为荣。 目标:能直接手撕红黑树。 毒鸡汤:行到水穷处,坐看云起时。。 望小伙伴们点赞👍收藏✨加关注哟💕💕  相信大家肯定听过在C++大名鼎鼎的两颗树,这两颗树分别

    2024年03月23日
    浏览(35)
  • C++ 红黑树

    红黑树,是一种 二叉搜索树 ,但 在每个结点上增加一个存储位表示结点的颜色 , 可以是Red或 Black 。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。 1. 每个结点不是红色就是黑色 2. 根节

    2024年02月05日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包