【C++进阶06】红黑树图文详解及C++模拟实现红黑树

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

【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言

一、红黑树的概念及性质

1.1 红黑树的概念

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

1.2 红黑树的性质

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

【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言

为啥满足上面性质的红黑树就能保证
其最长路径节点个数不会超过最短路径
节点个数的两倍?

由性质3可得出不能出现连续红色节点
由性质4可得出每条路径有相同黑色节点数量

极限情况下
最短路径:全黑
最长路径:一黑一红

由此可得出
最长路径不会超过最短路径的两倍
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言

1.3 为什么更常用红黑树而不是AVL树?

AVL树: 是一颗高度平衡的二叉树
查找效率: O ( l o g N ) O(logN) O(logN)
但是这样的效率是在插入元素时
经常性的旋转换来的

红黑树: 是一颗接近平衡的二叉树
假设全部黑节点有N个
整棵树的节点数量:[N, 2N]之间
最短路径长度: O ( l o g N ) O(logN) O(logN)
最长路径长度: O ( 2 l o g N ) O(2logN) O(2logN)
查找效率: O ( 2 l o g N ) O(2logN) O(2logN)

10亿数据AVL树最多查找30次
红黑树最多也就查找60次
对于cpu的运行速度来说几乎可以忽略不计
但红黑树的规则相对于AVL树没那么严格
在插入元素时,不会经常旋转
所以综合而言红黑树更胜一筹

如图: 对于AVL树必定旋转
红黑树则不用
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言

二、红黑树模拟实现的基本框架

2.1 红黑树节点的定义

跟AVL树一样
只是AVL树采用平衡因子
让树达到平衡
而红黑树对节点进行颜色标记
让树达到平衡
定义一个枚举表示节点颜色

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:
private:
	Node* _root = nullptr;
};

2.2 红黑树的插入

还是和AVL树一样

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

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first) // 插入节点比当前节点大往右走, 小往左走
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		// 链接
		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		// new的节点的parent还指向空
		cur->_parent = parent;

		// 插入黑色节点还是红色节点?

		return true;
	}

插入走到这里如果是AVL树
此时需要更新平衡因子

红黑树采用的是标记节点颜色
让树达到平衡
需要考虑的是插入什么颜色的节点?

  1. 插入黑色节点
    会违反规则4,影响到每条路径
  2. 插入红色节点
    如果插入节点的父节点也是红色节点
    则会违反规则3影响当前局部节点

很明显插入红色节点更划算
所有插入的节点都默认是红色
如果违反红黑树的规则,再进行调整

三、对插入节点调整的解析

如果插入节点的父节点为黑
则无需处理
如果为红,则分为三种情况

情况一:

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

cur为当前节点,p为父节点
g为祖父节点,u为叔叔节点
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言
把p和u变黑,g变红
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言
如果grandfather的parent也为红
把grandfather改为cur
继续按刚才的步骤往后迭代
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言
如果grandfather为根节点
把grandfather改为黑色
颜色调整结束
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言

情况二:

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

此树可能是完整树也可能是子树
u节点不存在
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言
p为g的左孩子,cur为p的左孩子
则进行右单旋转
相反
p为g的右孩子,cur为p的右孩子
则进行左单旋转
p、g变色–p变黑,g变红
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言

【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言
下图则是u节点存在的情况
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言
c为下面4种情况的
任意一种包含一个黑节点的红黑树
d和e可能是空或者一个红节点
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言
插入新节点,更新完后
继续往后更新
就是情况二的u存在的情况
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言

情况三:

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

跟情况二完全类似
只是情况三为双旋
情况二是单旋

p为g的左孩子,cur为p的右孩子
则针对p做左单旋转
相反
p为g的右孩子,cur为p的左孩子
则针对p做右单旋转

则转换成了情况2
此图为u不存在
u存在参考情况二
【C++进阶06】红黑树图文详解及C++模拟实现红黑树,C++,c++,开发语言

四、红黑树插入代码的全部实现

详解都在代码注释
各位友友们请耐心看完

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

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first) // 插入节点比当前节点大往右走, 小往左走
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	// 链接
	cur = new Node(kv);
	if (parent->_kv.first > kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}

	// new的节点的parent还指向空
	cur->_parent = parent;

	// 如果新插入节点破坏了红黑树规则
	// 则更新节点颜色
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		if (grandfather->_left == parent)
		{
			Node* uncle = grandfather->_right;
			// 情况1:u存在且为红,变色处理,并继续往上处理
			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else // 情况2+3:u不存在或者u存在且为黑,旋转+处理
			{
				// 如果插入节点在父节点的左,c、p、g呈一条斜线
				//     g
				//   p   u
				// c
				if (parent->_left == cur)
				{
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED; 
				}
				else
				{
					// 插入节点在父节点的右,c、p、g呈一条折线
					//      g
					//   p      u
					//     c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					// parent->_col = RED; // 父亲本就是红,变一下双重保险
					grandfather->_col = RED;
				}

				break;
			}
		}
		else // (grandfather->_right == parent)
		{
			Node* uncle = grandfather->_left;
			// 情况1:u存在且为红,变色处理,并继续往上处理
			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else // 情况2+3:u不存在或者u存在且为黑,旋转+处理
			{
				//   g
				// u    p
				//         c
				if (parent->_right == cur)
				{
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				else
				{
					//   g
					// u     p
					//     c
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
	}

	_root->_col = BLACK; // 做个双保险,无论那种情况把根都变成黑的
	return true;
}

五、红黑树全部代码模拟实现

gitee链接

✨✨✨✨✨✨✨✨
本篇博客完,感谢阅读🌹
如有错误之处可评论指出
博主会耐心听取每条意见
✨✨✨✨✨✨✨✨文章来源地址https://www.toymoban.com/news/detail-812036.html

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

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

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

相关文章

  • 【C++】 使用红黑树模拟实现STL中的map与set

    前面的文章我们学习了红黑树,也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的(而map和set的使用我们前面也学过了)。 既然红黑树我们也学习过了,那这篇文章我们就用红黑树来简单实现一下STL中的map和set,重点是学习它的框架。 上一篇文章我们实现了红黑

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

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

    2024年02月07日
    浏览(44)
  • C++语法(20)---- 模拟红黑树

    C++语法(19)---- 模拟AVL树_哈里沃克的博客-CSDN博客 https://blog.csdn.net/m0_63488627/article/details/130229501?spm=1001.2014.3001.5501 目录 1.红黑树介绍 2.模拟实现 1.枚举红黑颜色 2.节点的定义 3.树类框架 4.插入 5.检查 3.代码实现 最长路径不超过最短路径的两倍,近似平衡 最短:全黑 最长:

    2024年02月01日
    浏览(37)
  • 『 C++ 』红黑树RBTree详解 ( 万字 )

    红黑树是一棵较为复杂的树; 其与AVL树相同,也为一棵平衡搜索二叉树; 其与AVL树不同的是,在AVL树中依靠平衡因子bf(Balance Factor)来保证树的结构始终保持为一个高度平衡的状态(每个节点的左右子树高度差不超过1); 而对于红黑树来说,其在节点当中存储了一个颜色,颜色不为红则为

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

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

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

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

    2024年03月25日
    浏览(41)
  • 【数据结构】—红黑树(C++实现)

                                                            🎬 慕斯主页 : 修仙—别有洞天                                                  💜 本文前置知识:  AVL树                                                       ♈️ 今日夜电波 :

    2024年02月05日
    浏览(51)
  • 【数据结构】红黑树(C++实现)

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.概念 2.性质 3.节点的定义  4.插入 4.1情况1:叔叔u存在且为红 4.2情况2:

    2024年03月13日
    浏览(54)
  • C++【实现红黑树(核心插入)】

    概念: 红黑树,也是一种二叉搜索树,它是在每个结点上增加一个存储位表示结点的颜色,可以是红或黑,然后通过对任何一条从根到叶子的路径上各个结点着色方式的限制,保证了没有一条路径会能超过其他路径的俩倍,因而是近似平衡的。map和set的底层数据结构就是用红

    2024年02月07日
    浏览(41)
  • 【C++】红黑树的原理与实现

      文章目录 一、引言 二、红黑树的概念与性质 2、1 红黑树的概念 2、2 红黑树的性质 三、红黑树的定义与实现 3、1 红黑树的定义 3、2 插入新节点 3、2、1 默认插入红色节点 3、3 插入情况分类 3、3、1 情况一(根据颜色向上调整) 3、3、2 情况二(单次旋转+变色) 3、3、3 情

    2024年02月13日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包