【C++】实现红黑树

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

一、认识红黑树

1.1 概念

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

【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构

红黑树的规则:

  • 根节点是黑色的
  • 不能有连续的红色节点
  • 从某个节点出发,每条路径上的黑色节点的数量相同

1.2 定义

红黑树也是三叉链结构(左指针、右指针和父亲指针),有一个新的存储位来记录节点的颜色,这里实现的红黑树是kv模型。

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)//默认的新节点都是红色的
	{}
};

二、实现红黑树

2.1 插入

红黑树的插入的与普通二叉搜索树的插入逻辑是一样的,不同的是插入新节点后要进行变色处理,符合前面的规则才行。
红黑树的插入一共分为两大类:

  1. 新插入的节点的父节点是黑色的,插入结束
  2. 新插入的节点的父节点是红色的,要变色处理

也就是说要看新插入的节点的父节点的颜色来确定是否本次插入结束。但是有个问题,新插入的节点说什么颜色的?其实看图就可以知道,插入的新节点必须是红色的,因为如果插入的是黑色节点,那么必然会导致每条路径上的黑色节点数量不相同,违反规则。

接下来看红黑树插入节点时是怎样变色的:
首先按照前面插入的两大类,如果插入节点的父节点是黑色的,就不需要进入变色调整;反之,如果插入节点的父节点存在且是红色的,说明此时有连续的红色节点,要变色处理。

这里需要定义几个节点的名字,方便叙述和画图:

  • c(cur)——当前新插入的节点
  • p(parent)——插入节点的父节点
  • g(grandfather)——父节点的父节点
  • u(uncle)——叔叔节点,父节点的另一边的节点

【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构
这4个节点主要看叔叔节点,根据叔叔节点分为两种情况。

情况一:叔叔存在且为红
p和u要变成黑色,g变成红色。如果g不是根节点,要向上更新,把g当成c;如果g是根节点,要把g变成黑色的,因为根节点必须是黑的。

1️⃣g是根节点

【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构

注意:不管p或者u是g的左边还是右边都是一样的,c在p的左边/右边都是一样的操作,不影响。

2️⃣g不是根节点
【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构

情况二:叔叔不存在或者叔叔存在且为黑

情况二里面又有4种变色方式(其实与其说是变色方式,不如直接说是旋转方式不同然后根据旋转情况来变色)

1️⃣p是g的左孩子,c是p的左孩子
进行右单旋,p变黑,g变红
【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构
【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构
上图的c不是新增,表示的是当它的叔叔节点u存在且为黑时的c不是新增。

注意:
这里u存在或者不存在也有两种情况,第一张图的c是新增的节点,u必然是不存在的,如果存在,会导致每条路径的黑色节点数量不相同;同理,第二张图的c刚开始是黑色的节点,它有自己的子树,是通过后面的向上变色处理才变红的,所以第二张图的u是必须存在的。总之一句话,u存不存在要符合规则

后面就以u不存在的情况处理
2️⃣p是g的右孩子,c是p的右孩子
进行左单旋,p变黑,g变红
【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构

3️⃣p是g的左孩子,c是p的右孩子
先左单旋§,再右单旋(g),g变红,c变黑
【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构

4️⃣p是g的右孩子,c是p的左孩子
先右单旋§,再左单旋(g),g变红,c变黑
【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)
	{
		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->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	//调整颜色
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;//爷爷节点
		//父节点在爷爷节点的左边,那么叔叔节点在右边
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			//情况一:叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				grandfather->_col = RED;
				uncle->_col = parent->_col = BLACK;
				cur = grandfather;//爷爷不是根,向上更新
				parent = cur->_parent;
			}
			//情况二:叔叔不存在/存在且为黑
			else
			{
				//单旋
				if (cur == parent->_left)
				{
					RotateR(grandfather);//右单旋
					parent->_col = BLACK;//变色
					grandfather->_col = RED;
				}
				//左右双旋 
				// cur == parent->_right
				else
				{
					RotateL(parent);//先左单旋
					RotateR(grandfather);//再右单旋
					grandfather->_col = RED;//变色
					cur->_col = BLACK;
				}
			}
		}
		else//父节点在右边,叔叔在左边
		{
			Node* uncle = grandfather->_left;
			//情况一:叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				grandfather->_col = RED;
				uncle->_col = parent->_col = BLACK;
				cur = grandfather;//爷爷不是根,向上更新
				parent = cur->_parent;
			}
			//情况二:叔叔不存在/存在且为黑
			else
			{
				//单旋
				if (cur == parent->_right)
				{
					RotateL(grandfather);//左单旋
					parent->_col = BLACK;//变色
					grandfather->_col = RED;
				}
				//右左双旋 
				// cur == parent->_left
				else
				{
					RotateR(parent);//先右单旋
					RotateL(grandfather);//再左单旋
					grandfather->_col = RED;//变色
					cur->_col = BLACK;
				}
				break;//经过情况二后跳出
			}
		}
	}
	_root->_col = BLACK;//统一处理,根必须是黑的
	return true;
}

//左单旋
void RotateL(Node* parent)
{
	RotateSize++;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	//不为空
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subR;
	//处理parent如果为根
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	//不为根,处理与ppnode的连接
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right = subR;
		}
		subR->_parent = ppnode;
	}
}

//右单旋
void RotateR(Node* parent)
{
	RotateSize++;
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	//不为空
	if (subLR)
	{
		subLR->_parent = parent;
	}
	subL->_right = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subL;

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

2.2 与AVL树对比

红黑树与AVL树都是平衡二叉树,那为什么现实中绝大部分是使用红黑树,很少使用AVL树?下面我们来作数据对比,从两者的旋转次数、插入时间、平衡状态和高度来作分析。

测试代码:

RBTree<int, int> t1;
AVLTree<int, int> t2;

const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));

for (size_t i = 0; i < N; i++)
{
	v.push_back(rand() + i);
}

size_t begin1 = clock();
for (auto e : v)
{
	t1.Insert(make_pair(e, e));
}
size_t end1 = clock();

size_t begin2 = clock();
for (auto e : v)
{
	t2.Insert(make_pair(e, e));
}
size_t end2 = clock();
//旋转次数
cout << "RBTree RoateSize:" << t1.getRotateSize() << endl;
cout << "AVLTree RoateSize:" << t2.getRotateSize() << endl;
//插入时间
cout << "RBTree Insert:" << end1 - begin1 << endl;
cout << "AVLTree Insert:" << end2 - begin2 << endl;
//平衡状态
cout << "RBTree IsBalance:" << t1.IsBalance() << endl;
cout << "AVLTree IsBalance:" << t2.IsBalance() << endl;
//树的高度
cout << "RBTree Height:" << t1.Height() << endl;
cout << "AVLTree Height:" << t2.Height() << endl;
//树的节点个数
cout << "RBTree Size:" << t1.Size() << endl;
cout << "AVLTree Size:" << t2.Size() << endl;

插入一千万个数据,运行结果:
【C++】实现红黑树,C++,c++,开发语言,c语言,算法,数据结构
可以发现,红黑树的旋转次数比AVL树少,插入时间相差不大,两种树都是平衡的,红黑树的高度略高一些。

总结:
由于高度上红黑树不会高出多少,所以搜索效率影响不大。从树的高度可知,AVL树是极致追求平衡的,所以要频繁的进行旋转,这也导致旋转次数明显比红黑树多,因此在旋转上开销较大,不及红黑树的性能更优越些,同时红黑树实现比较简单,所以实际运用中红黑树更多。文章来源地址https://www.toymoban.com/news/detail-843136.html

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

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

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

相关文章

  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

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

    2024年02月09日
    浏览(46)
  • Python - 深夜数据结构与算法之 AVL 树 & 红黑树

    目录 一.引言 二.高级树的简介 1.树 2.二叉树 3.二叉搜索树 4.平衡二叉树 三.AVL 树 ◆ 插入节点 ◆ 左旋 ◆ 右旋 ◆ 左右旋 ◆ 右左旋 ◆ 一般形式 ◆ 实际操作 ◆ 总结 四.红黑树 ◆ 概念 ◆ 示例 ◆ 对比 五.总结 前面我们介绍了二叉树、二叉搜索树、多叉树等基础的树形结构,

    2024年01月19日
    浏览(42)
  • 【数据结构】二叉树---红黑树的实现

    目录 一.  红黑树的概念及性质 二.  红黑树结点结构的定义 三.  红黑树的插入操作      1. 情况一      2. 情况二        3. 情况三 四.  红黑树的验证 五.  红黑树与AVL树的比较 红黑树是一种自平衡的二叉搜索树,它在每个节点上增加了一个存储位来表示节点的颜色,

    2024年03月21日
    浏览(42)
  • Java 数据结构篇-实现红黑树的核心方法

      🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍      文章目录         1.0 红黑树的说明         2.0 红黑树的特性         3.0 红黑树的成员变量及其构造方法         4.0 实现红黑树的核心方法         4.1 红黑树内部类的核心方法         (1)判

    2024年01月24日
    浏览(43)
  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(93)
  • 红黑树数据结构

    现在JAVASE中HashMap中底层源码是由数组+链表+红黑树进行设计的,然后很多地方也是用到红黑树,这里单独对红黑树数据结构进行简单的介绍。 目录 红黑树概念 红黑树的性质 自平衡规则 代码   红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可

    2024年02月01日
    浏览(38)
  • 【数据结构-树】红黑树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(42)
  • 数据结构 | 红黑树

    节点的左边比节点的值小,右边比节点的值大。 节点要么是 红色 ,要么是 黑色 根节点 是黑色 叶子节点都是黑色的空节点 红黑树中红色节点的子节点都是黑色 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点 在添加或者删除节点的时候,如果不满足这些性质会

    2024年01月21日
    浏览(41)
  • 数据结构——红黑树

    目录 概念 性质 结点的定义  插入 调整 当p是g的左孩子时 当p为g的右孩子时 插入完整代码 红黑树的检测 红黑树完整代码(包括测试数据)   红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是RED或BLACK。 通过对任何一条从根到叶子的路径

    2023年04月09日
    浏览(42)
  • [数据结构]-红黑树

    前言 作者 : 小蜗牛向前冲 名言: 我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、红黑树的基本知识  1、红黑树的概念 2、性质  二、红黑树的模拟实

    2024年02月04日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包