【C++】红黑树的插入分析及验证

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

1. 红黑树概念

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

【C++】红黑树的插入分析及验证

2. 红黑树性质

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

3. 结构定义

【C++】红黑树的插入分析及验证

使用枚举来记录红色与黑色,用_col表示当前节点颜色


但是在构造函数中为什么默认是红色呢?为什么不能是黑色呢?

关于默认节点为红/黑色的讨论

【C++】红黑树的插入分析及验证

若在红框中插入黑色节点则违反规则4 即每条路径上都有相同数量的黑色节点,还需要再次将不同路径上都添加黑色节点,影响太大


【C++】红黑树的插入分析及验证

若在红框中插入红色节点,则有可能违反规则3(存在两个连续的红色节点)
当前情况违反规则3


【C++】红黑树的插入分析及验证

若插入红色节点后,父节点为黑色,则不违反规则3


所以默认节点为红色更利于去解决问题

4. insert

grandfather节点省略为g ,uncle节点省略为u ,parent节点省略为p,cur节点省略为c

情况1—— uncle节点存在且为红色(g p c左斜形成一条直线)

【C++】红黑树的插入分析及验证

当插入红色节点后,与父节点形成连续的红色节点
把parent节点变成黑色,uncle节点置为黑色,并将grandfather节点置为红色
若grandfather节点的父节点为黑色,则不需要继续处理
若grandfather节点的父节点为红色,把当前的grandfather节点作为新增节点cur,继续向上调整


【C++】红黑树的插入分析及验证

情况2——uncle节点不存在/存在且为黑色(g p c 左斜形成直线 右单旋)

uncle节点不存在
【C++】红黑树的插入分析及验证

当uncle节点不存在时,则cur作为新增节点,
因为红黑树也是一种二叉搜索树,因为左边高,所以进行右单旋

uncle节点存在并且为黑色
【C++】红黑树的插入分析及验证

首先进行变色,将新增节点的上面两个节点置为黑色,再将cur节点置为红色
同时需要进行右旋转


【C++】红黑树的插入分析及验证
将c作为g的左子树,将g作为p的右子树
将g置为红色
将p置为黑色

【C++】红黑树的插入分析及验证

RotateR/RotateL的实现,与AVL树的类似,只需把原来的代码的平衡因子去掉即可
不懂查看:AVL树的实现

情况3——uncle节点不存在/存在且为黑色(g p c 形成左折线 双旋)

因为 grandfather(g) parent( p) cur( c) 节点为一条折线,所以为双旋

uncle节点不存在
【C++】红黑树的插入分析及验证

作为这样的折线存在,所以要进行双旋,先对p进行右单旋,在对旋转后的根进行左单旋

uncle节点存在并且为黑色
【C++】红黑树的插入分析及验证

首先进行变色,将新增节点上面的两个节点由红色置为黑色
再将cur节点由黑色置为红色


【C++】红黑树的插入分析及验证

在进行左单旋,将cur的左子树节点 作为p的右子树,将p作为cur的左子树


【C++】红黑树的插入分析及验证
进行右单旋,将cur的右子树节点作为g的左子树,将g作为cur的右子树
最终cur变为黑色,g变为红色


【C++】红黑树的插入分析及验证

情况1—— uncle节点存在且为红色(g p c右斜形成一条直线)

【C++】红黑树的插入分析及验证

当插入红色节点后,与父节点形成连续的红色节点
把parent节点变成黑色,uncle节点置为黑色,并将grandfather节点置为红色


【C++】红黑树的插入分析及验证

若grandfather节点的父节点为红色,把当前的grandfather节点作为新增节点cur,继续处理


与上述左斜形成直线的写法相同

情况2——uncle节点不存在/存在且为黑色(g p c 右斜形成直线 左单旋)

【C++】红黑树的插入分析及验证

这里以节点不存在举例


此时的uncle节点处于NULL
将parent节点置为黑色,将grandfather节点置为红色
并进行旋转,将1作为6的左子树,将6作为8的左子树
相当于进行左单旋

【C++】红黑树的插入分析及验证

情况3——uncle节点不存在/存在且为黑色(g p c 形成右折线 双旋)

【C++】红黑树的插入分析及验证

首先进行变色,将新增节点上面的两个节点由红色置为黑色
再将cur节点由黑色置为红色


【C++】红黑树的插入分析及验证
在进行右单旋,将cur的右子树节点 作为p的左子树,将p作为cur的右子树


【C++】红黑树的插入分析及验证
进行左单旋,将cur的左子树节点作为g的右子树,将g作为cur的左子树
最终cur变为黑色,g变为红色

【C++】红黑树的插入分析及验证

5.判断是否为红黑树

【C++】红黑树的插入分析及验证

规则中要求根节点为黑色,所以当根为红色时就返回false

连续的红色节点
若当前节点为红时,检查儿子是否为红,但是儿子节点有可能为空
所以采用当前节点为红时,若父节点也为红,则返回false

使用blacknum用于记录每条路径的黑色节点个数
blacknum作为一个形参传值调用,下一层的++不会影响上一层
如果当前节点的颜色为黑色,则blacknum++
文章来源地址https://www.toymoban.com/news/detail-454182.html

6. 整体代码

#pragma once
#include<iostream>
#include<cassert>	
using namespace std;
enum colour
{
	RED,//红色 默认为0
	BLACK,//黑色 默认为1
};
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:
	   bool insert(const pair<K, V>& kv)
	   {
		   if (_root == nullptr)
		   {
			   _root = new Node(kv);
			   _root->_col = BLACK;//若刚插入一个节点,则该节点颜色是黑色
			   return true;
		   }
		   Node* parent = nullptr;//用于记录cur的前一个节点
		   Node* cur = _root;
		   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);
		   //再次判断parent当前节点值与插入值大小
		   if (parent->_kv.first > kv.first)
		   {
			   parent->_left = cur;
		   }
		   else
		   {
			   parent->_right = cur;
		   }
		   //cur的上一个节点即为 刚才的记录cur前一个节点的parent
		   cur->_parent = parent;

           //当父节点不为NULL并且父节点为红色
		   while (parent != nullptr && parent->_col == RED)
		   {
			   Node* grandfather = parent->_parent;//爷爷节点

			   //若父节点为爷爷节点的左子树,则unlce为爷爷节点的右子树
			   if (grandfather->_left == parent)
			   {
				   Node* uncle = grandfather->_right;
				   //       g
				   //    p     u
				   // c
				   //情况1:u存在并且为红,直接变色即可,并继续往上处理
				   if (uncle && uncle->_col == RED)
					   //若uncle节点为红色,将parent与uncle都置为黑色,爷爷节点置为红色
				   {
					   parent->_col = BLACK;
					   uncle->_col = BLACK;
					   grandfather->_col = RED;

					   //继续往上调整
					   cur=grandfather;
					   parent = cur->_parent;
				   }
				   //情况2+3:u不存在或者u存在且为黑,旋转+变色
				   else
				   {	 
					   //情况2
					   //g p c 作为一条直线 所以为单旋
					   //    g
					   //  p   u
	 				   //c 
					   if (cur == parent->_left)
					   {
						   //右旋转
						   RotateR(grandfather);
						    
						   //最终p作为最终的根 为黑  g为红 
						   parent->_col = BLACK;
						   grandfather->_col = RED;
					   }
					   //情况3
					   //g p c 作为一条折线 所以为双旋
					   //    g
					  //   p   u
					  //     c 
					   else
					   {
						   //左单旋
						   RotateL(parent);
						   //右单旋
						   RotateR(grandfather);
						   //最终cur作为最终的根 为黑  g为红 
						   cur->_col = BLACK;
						   grandfather->_col = RED;
						   //父节点继续保持红色
						   parent->_col = RED;
					   }
					   break; 
				   }
			   }

			   else//grandfather->_right == parent
				   若父节点为爷爷节点的右子树,则unlce为爷爷节点的左子树
			   {
				   //   g
				   // u   p
				   //       c
				   Node* uncle = grandfather->_left;

				   //情况1:u存在并且为红,直接变色即可,并继续往上处理
				   if (uncle && uncle->_col == RED)
					   //若uncle节点为红色,将parent与uncle都置为黑色,爷爷节点置为红色
				   {
					   parent->_col = BLACK;
					   uncle->_col = BLACK;
					   grandfather->_col = RED;

					   //继续往上调整
					   cur = grandfather;
					   parent = cur->_parent;
				   }

				   //情况2+3:u不存在或者u存在且为黑,旋转+变色
				   else
				   {
					   //情况2
					   //g p c 作为一条直线 所以为单旋
					   //    g
					   //  u   p
					   //        c  
					   if (cur == parent->_right)
					   {
						   //左旋转 
						   RotateL(grandfather);

						   //最终p作为最终的根 为黑  g为红 
						   parent->_col = BLACK;
						   grandfather->_col = RED;
					   }
					   //情况3
					   //g p c 作为一条折线 所以为双旋
					   //   g
					  //  u   p
					  //    c 
					   else
					   {
						   //右单旋
						   RotateR(parent);
						   //左单旋
						   RotateL(grandfather);
						   //最终cur作为最终的根 为黑  g为红 
						   cur->_col = BLACK;
						   grandfather->_col = RED;
					   }
					   break;
				   }
			   }
		   }
		   //为了避免grandfather节点正好为根时,会被更新成红色的情况
		   _root->_col = BLACK;
		   return true;
	   }

	   void inorder()//中序遍历
	   {
		   _inorder(_root);
		   cout << endl;
	   }
	   //判断一颗二叉树是否为红黑树
	   bool isbalance()
	   {
		   //检查根是否为黑
		   if (_root && _root->_col == RED)
		   {
			   cout << "根节点颜色是红色" << endl;
			   return false;
		   }
		   //连续的红色节点
		   return _check(_root,0);
	   }

	private:
		bool _check(Node* root,int blacknum)
		{
			if (root == nullptr)
			{
				//为空时,blacknum代表一条路径的黑色节点个数
				cout << blacknum << " ";
				return true;
		    }
			//blacknum代表黑色节点的个数
			if (root->_col == BLACK)
			{
				blacknum++;
			}
			//若当前节点为红 父节点也为红
			if (root->_col == RED
				&&root->_parent 
				&&root->_parent->_col==RED)
			{
				cout << "存在连续的红色节点" << endl;
				return false;
			}
			//遍历整棵树
			return	_check(root->_left,blacknum) && _check(root->_right,blacknum);
		}
		void _inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_inorder(root->_left);
			cout << root->_kv.first << " ";
			_inorder(root->_right);
		}
		   void RotateL(Node* parent)//左单旋
		   {
			   Node* subR = parent->_right;
			   Node* subRL = subR->_left;

			   parent->_right = subRL;
			   if (subRL != nullptr)
			   {
				   subRL->_parent = parent;
			   }
			   Node* ppnode = parent->_parent;//记录parent的前一个节点

			   subR->_left = parent;
			   parent->_parent = subR;

			   if (ppnode == nullptr)//说明parent是根即代表整棵树
			   {
				   _root = subR;//subR作为新的根
				   _root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
			   }
			   else//说明旋转的是一部分,所以要跟ppnode相连接
			   {
				   if (ppnode->_left == parent)//若连接在左子树上
				   {
					   ppnode->_left = subR;
				   }
				   else//若连接在右子树上
				   {
					   ppnode->_right = subR;
				   }
				   subR->_parent = ppnode;//将subR父节点置为ppnode
			   }
		   }

		   void RotateR(Node* parent)//右单旋
		   {
			   Node* subL = parent->_left;
			   Node* subLR = subL->_right;
			   parent->_left = subLR;
			   if (subLR != nullptr)
			   {
				   subLR->_parent = parent;
			   }
			   Node* ppnode = parent->_parent;//记录parent的父节点
			   subL->_right = parent;
			   parent->_parent = subL;

			   if (ppnode == nullptr)//若旋转整棵树
			   {
				   _root = subL;
				   _root->_parent = nullptr;
			   }
			   else//若旋转整棵树的部分子树
			   {
				   if (ppnode->_left == parent)
				   {
					   ppnode->_left = subL;
				   }
				   else
				   {
					   ppnode->_right = subL;
				   }
				   subL->_parent = ppnode;//使subL的父节点为ppnode
			   }

		   }
	private:
		Node* _root = nullptr;
};

void test_RBTree1()
{
	int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };
	RBTree<int, int>v1;
	for (auto e : a)
	{
		v1.insert(make_pair(e, e));
	}
	v1.inorder();
	cout << v1.isbalance() << endl;
	
}

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

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

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

相关文章

  • 【数据结构】红黑树的删除(抽丝剥茧,带你理清每一种情况)

     红黑树的删除,较AVL树的删除比较抽象,同时也跟红黑树的插入的区别较大,但大体上的思路还是基于普通二叉搜索树的基础上进行讨论的。 浅浅的铺垫一下: 需要清楚普通二叉树的删除,可见AVL树的删除文章开头。 四种旋转的操作(只需操作)得熟记于心,可见AVL树的插

    2024年04月27日
    浏览(34)
  • 【C++】红黑树的模拟实现

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

    2024年02月08日
    浏览(47)
  • 【C++】红黑树插入删除

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

    2024年02月02日
    浏览(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)
  • C++【实现红黑树(核心插入)】

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

    2024年02月07日
    浏览(41)
  • 【C++】红黑树模拟实现插入功能(包含旋转和变色)

    本篇主要讲解红黑树的模拟实现,实现之后再封装成map和set。 红黑树中所用到的旋转功能均源自我的上一篇博客,本篇中不会再详谈旋转,若对于旋转不了解的同学可以先看看上一篇博客:【C++】AVL树模拟实现插入功能 前一篇的AVL树,是严格平衡的一棵二叉搜索树,也就是

    2024年02月13日
    浏览(52)
  • 【C++】如何克服红黑树的恐惧?看这篇文章足够了

    红黑树的实现会比AVL简单-.- 文章目录 判断是否是AVL树 一、红黑树 二、红黑树的实现 总结 上一篇文章我们详细介绍了AVL树并且实现了AVL树,这篇文章我们将在前言中引入判断是否是AVL树的方法,然后我们就进入红黑树的实现,如果是能自己实现AVL树的同学那么实现起红黑树

    2024年02月05日
    浏览(75)
  • 红黑树的使用场景

       

    2024年02月15日
    浏览(40)
  • 红黑树(AVL树的优化)上

    红黑树略胜AVL树 AVL树是一颗高度平衡搜索二叉树: 要求左右高度差不超过1(严格平衡) 有的大佬认为AVL树太过严格,对平衡的要求越严格,会带来更多的旋转(旋转也还是会有一定的消耗!!) 红黑树的出发点: 最长路径不超过最短路径的2倍(近似平衡) 相对而言,插

    2024年02月10日
    浏览(38)
  • 红黑树的了解以及代码实现

            红黑树是在二叉搜索树的基础上 添加颜色 , 通过对任何一条路径的颜色的限制,确保红黑树的任何一条路径不会超过其他路径的两倍 ,是一棵近似平衡的树。         红黑树的节点不是红色就是黑色,其节点的排列除了需要按二插搜索树的规则来插入之外,还

    2024年02月03日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包