【手撕红黑树】

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

前言

相信很多人初学者听到了红黑树后心中不免有些心慌,那你看到了这篇文章后相信会有所收获,我其实刚开始也是对红黑树抱着一种害怕甚至是恐惧,但是在老师的帮助下也终于慢慢的不在恐惧了,你想知道为什么的话就继续往下看吧。(注意本篇博客只讲解了红黑树的插入,没有讲解红黑树的删除,删除比插入还要难一些,为了更好的阅读体验,就不再讲解了)


1 红黑树的概念

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

如果说AVL树是大佬设计的话,那么红黑树就是大佬中的大佬设计出来的,为什么这么说呢,我们接下来慢慢看。


2 红黑树的性质

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

我们先不要看最后一条性质,其他性质中比较重要的就是性质三和性质四,我们可以用自己的话来解读性质三和性质四:
性质三的意思是没有连续红色结点
性质四的意思是每条路径下的黑色结点数量是相等的

大家思考一下,为什么满足了上面性质就能够保证红黑树中最长路径中节点个数不会超过最短路径节点个数的两倍

我们可以从极限的条件下来判断:
最短路径是全黑,最长路径是红黑相间,由于要满足性质三和性质四所以最长路径除以最短路径最大也不会超过二倍。

【手撕红黑树】
我们再来看看最后一个性质,有些教科书上可能会有NIL结点的定义,并且把颜色定义为黑色,注意这里的NIL结点并不是一个真正有效的节点,而是一个空结点。通过每条空结点来标识每一条路径,如在上图中就存在着11条路径。

通过红黑树的性质我们也不难发现,其实红黑树的平衡并没有AVL树那么严格,因为红黑树只需要保证最长路径的结点个数不会超过最短路径节点个数两倍即可,但是AVL树要求着所有子树高度差绝对值不超过1。这就导致了红黑树的旋转条件是比AVL树更加苛刻的,也就是在同等条件下红黑树旋转次数是有较大机率低于AVL树的,那么红黑树的性能肯定是比AVL要好上一些的(旋转是有代价的),如果还没有了解过旋转,建议先看看博主的上一篇博客:
[AVL树的旋转]


3 红黑树的模拟实现

3.1 节点的定义

这个很简单,我们已经讲解过很多次了:

#pragma once


enum Corlor
{
	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;
	Corlor _corlor;

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

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
private:
	Node* _root = nullptr;
};

这里问题就来了,新节点给的颜色是给红色还是给黑色呢?
给红色的话就可能违背性质三,给黑色结点就违背性质四。如果是你你想违背哪个性质?
这里给新节点的默认颜色为红色比较好,为什么呢?
给出红色结点的话,我们可能就只需要调整本路径下结点颜色,但是给黑色结点的话其他路径黑色结点就不相等了,调整的代价肯定更大。所以新节点的默认颜色给红色是比较合理的。

【手撕红黑树】我们观察上图,如果我们在11 或者15 下插入新节点,那么这就太好了,不需要进一步调整,插入后还是一颗红黑树,但是我们想要在6 22 27下面插入新节点的话,就要调整了,具体怎样调整我们下面会详细讲解。

3.2 分类

约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
红黑树调整分类的关键就是看叔叔

3.2.1 情况一

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

【手撕红黑树】
老规矩,我们这里画的仍然是抽象图,表示无数种情况,但是他们都可以用同一种方法来解决。
此时我们只需要将p和u置黑,将g置红,然后接着往上调整
为什么要继续往上调整呢?通过观察我们可以很容易分析出问题所在,这样一次调整了后各个路径上黑色结点数目并没有发生改变,但是有可能g结点的父亲结点是红色的,而导致又出现了连续红色结点(注意,调整了后有可能再次调整使用的方法不在是第一种情况)
【手撕红黑树】继续向上调整的话,直到不满足连续红色结点或者已经调整到了根节点。

3.2.2 情况二

cur为红,p为红,g为黑,u不存在/u存在且为黑

【手撕红黑树】
我们先分析第一种情况:u不存在。
如果u不存在的话,那么cur一定是新增。此时光变色已经无法解决问题了,因为此时已经不满足最长路径中节点个数不会超过最短路径节点个数的两倍,就需要旋转处理:
【手撕红黑树】这里处理方式是:右单旋+p变黑,g变红。
也有可能p和cur都在右边且在一条直线上,所以处理方式可能是:左单旋+p变黑,g变红。
总结本次调整方法为:单旋+p变黑,g变红

同理,当u存在且为黑的时候仍然是同种处理方式:
【手撕红黑树】旋转变色完以后就不用再向上更新了

3.2.3 情况三

cur为红,p为红,g为黑,u不存在/u存在且为黑

等等,这种方式不就是第二种方式吗?
别着急,我们先来看看图:
【手撕红黑树】
从图片中我们不难发现,g p cur 三者并没有在一条直线,而是一种折线关系,这种情况我们只是单旋就处理不了了,在这张图中我们先以p点进行左单旋,在以g点进行右单旋上。
(注意,我们在b和c下面插入结点导致引起上面这种关系的都可以用这种方式处理)
【手撕红黑树】
【手撕红黑树】当然,不只是这一种情况,还可能是反着来,那么处理方式就可能是:
以p右单旋+以g左单旋+cur变黑,g变红。
所以这次情况处理方式是:双旋+cur变黑,g变红
旋转变色完以后就不用再向上更新了

3.3 代码实现

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

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_corlor == RED)
		{
			Node* grand = parent->_parent;
			assert(grand);
			assert(grand->_corlor == BLACK);

			if (grand->_left == parent)
			{
				Node* uncle = grand->_right;
				//情况一:uncle存在且为红
				if (uncle && uncle->_corlor == RED)
				{
					uncle->_corlor = parent->_corlor = BLACK;
					grand->_corlor = RED;
					//继续往上处理
					cur = grand;
					parent = cur->_parent;
				}
				else
				{
					//情况二和三:
					//1 :parent->_left==cur(右单旋+变色)
					//      g
					//   p     u
					//c
					if (parent->_left == cur)
					{
						RotateR(grand);
						parent->_corlor = BLACK;
						grand->_corlor = RED;
					}
					else
					{
						//2 :parent->_right==cur(左单旋+右单旋+变色)
						//      g
						//   p     u
						//      c
						RotateL(parent);
						RotateR(grand);
						cur->_corlor = BLACK;
						grand->_corlor = RED;

					}

					//此时已经旋转变色完成,可以break出去
					break;
				}
			}
			else//grand->_right=parent
			{
				Node* uncle = grand->_left;
				//情况一:uncle存在且为红
				if (uncle && uncle->_corlor == RED)
				{
					uncle->_corlor = parent->_corlor = BLACK;
					grand->_corlor = RED;
					//继续往上处理
					cur = grand;
					parent = cur->_parent;
				}
				else
				{
					//情况二和三:
					//1 :parent->_right==cur(左单旋+变色)
					//      g
					//   u     p
					//            c
					if (parent->_right == cur)
					{
						RotateL(grand);
						parent->_corlor = BLACK;
						grand->_corlor = RED;
					}
					else
					{
						//2 :parent->_left==cur(右单旋+左单旋+变色)
						//      g
						//   u     p
						//      c
						RotateR(parent);
						RotateL(grand);
						cur->_corlor = BLACK;
						grand->_corlor = RED;
					}

					//此时已经旋转变色完成,可以break出去
					break;
				}
			}

		}
		_root->_corlor = BLACK;
		return true;
	}

3.4 红黑树的验证

验证的话我们要从红黑树的性质开始着手,只要满足了红黑树的几个性质自然就没啥问题.

最主要的验证是性质三和性质四:

//bool prevCheck(Node* root, int blackCnt, int& benchmark)
	bool prevCheck(Node* root, int blackCnt, int benchmark)
	{
		if (root == nullptr)
		{
			/*if (benchmark == 0)
			{
				benchmark=blackCnt;
				return true;
			}*/

			if (benchmark != blackCnt)
			{
				cout << "每条路径上的黑色结点不相等" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}

		if (root->_corlor == BLACK)
		{
			++blackCnt;
		}

		if (root->_corlor == RED && root->_parent->_corlor == RED)
		{
			cout << "有连续的红色结点" << endl;
			return false;
		}

		return prevCheck(root->_left, blackCnt, benchmark)
			&& prevCheck(root->_right, blackCnt, benchmark);
	}

bool isbalance()
	{
		if (_root && _root->_corlor == RED)
		{
			cout << "根节点不是黑色" << endl;
			return false;
		}

		int benchMark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_corlor == BLACK)
				++benchMark;
			cur = cur->_left;
		}
		int blackCnt = 0;
		return prevCheck(_root, blackCnt, benchMark);
	}

处理方式有很多种,像每条路径下的黑色节点我们可以一次性先算出来然后传参数即可,也可以不算出来,传参数引用来修改。具体方式大家可以自行选择。
大家测试时最好多用几组随机数测测。


5 总结

大家看到了这里相信也对红黑树有了一个谱,其实说难吧,感觉还没有刚学AVL的旋转难,关键是如何把图画好,跟着图一步一步的来,大概率是不会出错的。如果该文对你有帮助的话能不能一键三联支持博主呢文章来源地址https://www.toymoban.com/news/detail-455001.html

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

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

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

相关文章

  • c++代码手撕红黑树

    企业里永远是技术驱动理论发展 比起理解红黑树的原理,更重要的是理解红黑树的应用场景,因为某些应用场景的需要,红黑树才会应运而生。 红黑树的特点: 插入,删除,查找都是O(logn)的复杂度。 红黑树的应用: epoll的实现,内核会在内存开辟一个空间存放epoll的红黑树

    2024年02月06日
    浏览(41)
  • 【高阶数据结构】手撕红黑树(超详细版本)

    (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是 Scort 目前状态:大三非科班啃C++中 🌍博客主页:张小姐的猫~江湖背景 快上车🚘,握好方向盘跟我有一起打天下嘞! 送给自己的一句鸡汤🤔: 🔥真正的大师永远怀着一颗学徒的心 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏 🎉🎉

    2024年01月17日
    浏览(42)
  • 史上最详细的红黑树讲解(一篇文章教你手撕红黑树)

           🔥🔥 欢迎来到小林的博客!!       🛰️博客主页:✈️小林爱敲代码       🛰️博客专栏:✈️数据结构与算法       🛰️欢迎关注:👍点赞🙌收藏✍️留言       今天给大家讲解红黑树,和AVL树一样,这章暂且不讲删除。

    2024年01月16日
    浏览(42)
  • 相信我,SDRAM真的不难----汇总篇 ?前言

            本文是 《相信我,SDRAM真的不难》 系列文章的汇总篇。         该系列介绍了SDRAM的基本组成,对SDRAM的操作提供了一套完整的方法,并用此方法实现了几个练手的小项目。         SDRAM具有空间存储量大、读写速度快、价格相对便宜等优点。然而由于SDRAM内部利

    2023年04月11日
    浏览(38)
  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

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

    2024年02月09日
    浏览(49)
  • AVL树,红黑树,红黑树封装map和set

    二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素, 效率低下 。因此,咱们中国的邻居俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法: 当向二叉搜索树中插入

    2023年04月25日
    浏览(61)
  • 搜索二叉树 | 红黑树 | 验证是否为红黑树 | 代码实现

    黑红树是一颗特殊的搜索二叉树,本文在前文的基础上,图解红黑树插入:前文 链接,完整对部分关键代码展示,完整的代码在gitee仓库中: 链接 文章中有错误的地方,欢迎大家指正!如果有帮助到你,也请多多点赞支持! 1.红黑树的概述 平衡二叉树要求左右子树的高度差

    2024年02月21日
    浏览(41)
  • 【C++进阶06】红黑树图文详解及C++模拟实现红黑树

    1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点着色方式的限制 红黑

    2024年01月21日
    浏览(49)
  • 红黑树是什么,为什么HashMap使用红黑树代替数组+链表?

            我们都知道在HashMap中,当数组长度大于64并且链表长度大于8时,HashMap会从数组+链表的结构转换成红黑树,那为什么要转换成红黑树呢,或者为什么不一开始就使用红黑树呢?接下来我们将去具体的去剖析一下!         红黑树是一种自平衡的二叉搜索树,它是

    2024年04月14日
    浏览(37)
  • 【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

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

    2024年02月07日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包