最新公告
  • 欢迎您光临欧资源网，本站秉承服务宗旨 履行“站长”责任，销售只是起点 服务永无止境！立即加入我们
    • 3年
    专注建站行业优质资源供应商
    技术交流群
    升级SVIP
    站长资源平台

    【知识点】C语言实现红黑树详细步骤+代码

    2022-06-15 欧资源网 9 已收录
    正文概述 评论

    C语言实现红黑树详细步骤+代码、节点、红黑、黑、路径、父

    C语言+代码实现红黑树详细步骤

    轻松拿站长站，站长之家为你整理了C语言实现红黑树的详细步骤+代码。

    目录红黑树的概念红黑树的性质红黑树的定义和树结构新节点的插入插入后维护红黑树属性的主要逻辑反汇编讨论：红黑树的旋转验证与AVl树的比较红黑树的应用总结了红黑树的概念

    红黑树是二叉搜索树，只是在每个节点上增加了一个存储位来表示节点的颜色，可以是红色也可以是黑色。通过限制从根到叶的任何路径上的每个节点如何着色红黑树 c语言实现，红黑树确保没有路径是其他路径的两倍，因此几乎是平衡的

    在这里插入图片描述

    概念总结：

    红黑树是二叉搜索树的升级版。节点中存储的成员col标记了当前节点的颜色，它的最长路径是最最短路径的两倍。红黑树通过每个节点的着色方式的限制接近平衡二叉树，但与AVL不同的是，AVL是高度平衡的二叉树，红黑树只是接近平衡

    红黑树的性质

    每个节点不是红色就是黑色根节点是黑色如果一个节点是红色的，它的两个子节点是黑色的。对于每个节点，从该节点到其所有后代叶子节点的简单路径包含相同数量的黑色节点。每个叶子节点都是黑色的（这里的叶子节点指的是一个空节点）

    红黑树的属性总结：

    1、红黑树节点的颜色只能是红色或黑色

    2、红黑树根节点必须是黑色的

    3、红黑树没有连续的红色节点

    4、红黑树中从根到叶的每条路径都包含相同的黑色节点

    5、叶子是黑色的，表示空的位置

    最长路径和最短路径概念：

    最短路径：从根节点到叶子节点的每条路径的节点颜色为黑色，不包括红色

    最长路径：红黑交替，黑节点数和红节点数相等

    思考：为什么上面的性质满足红黑树：最长路径的节点数不会超过最短路径的节点数的两倍？

    假设节点数为N，则最短路径为logN，最长路径为2 * logN，且不存在最长路径超过最短路径2倍的情况

    红黑树的定义及树结构

    //枚举红黑颜色
enum colour 
{
	RED,
	BLACK,
};
//定义红黑树结点结构
template
struct RBTreeNode 
{
	//构造
	RBTreeNode(const pair& kv = {0,0})
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(BLACK)
	{ }
	//定义三叉链
	RBTreeNode* _left; //左孩子
	RBTreeNode* _right;//右孩子
	RBTreeNode* _parent;  //父亲
	pair _kv;  //pair对象
	//节点的颜色
	colour _col;  //定义枚举变量
};
//定义红黑树
template
class RBTree 
{
		typedef RBTreeNode Node;
	public:
		//构造
		RBTree() 
			:_root(nullptr)
		{}
	private:
		Node* _root;  //定义树的根节点
};

    插入

    插入过程类似于搜索树的插入，重要的是要保持红黑树的属性

    pair Insert(const pair& kv)
{
	if (!_root) //空树处理
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return { _root, true };
	}
	//二叉搜索树的插入逻辑
	Node* cur = _root, * parent = nullptr;
	while (cur)
	{
		if (cur->_kv.first _right; 
		}
		else if (cur->_kv.first > kv.first) //插入结点比当前结点小 
		{
			parent = cur;
			cur = cur->_left; 
		}
		else 
		{
			return { cur, false }; //插入失败
		}
	}
	cur = new Node(kv);
	cur->_col = RED;  //新增结点颜色默认设置为RED
	//判断插入结点是否在parent的左边或者右边
	if (parent->_kv.first > kv.first)  //左边
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else     //右边	
	{

    trie树 c语言实现_c语言实现数组实现map_红黑树 c语言实现
    
		parent->_right = cur;
		cur->_parent = parent;
	}
	
	/* 红黑树性质处理：
		如果这棵树一开始是符合红黑树的性质，但在新增结点之后，
		导致失去了红黑树的性质，这里需要控制结点的颜色和限制
		每条路径上黑色结点的个数，以上情况都要处理
    */
	while (parent && parent->_col == RED) //父亲存在且父亲为红色
	{
		Node* grandfather = parent->_parent;  //祖父
		//父亲出现在祖父的左边需要考虑的情况
		if(parent == grandfather ->left)
		{
			//1、uncle存在，uncle为红色
			/*
			   如果parent和uncle都存在并且都为红色这是情况一，
			   需要将parent和uncle的颜色变成红色，祖父颜色变成黑色
			   更新cur、parent、grandfather、uncle 继续向上调整
			*/
	
	
			//2、uncle不存在
			/*  这里考虑两种旋转情况，直线单旋转，折线双旋
				/*
					cur出现在parent的左边 ,右单旋转
					经过右单旋后，parent去做树的根,祖父做为右子树
					//调节结点颜色
					parent->_col = BLACK;
					grandfather->_col = RED;
				*/
				
				/*
					cur出现在parent的右边，左右双旋
					经过双旋后，cur作为树的根，grandfather为右子树
					调节结点颜色
					cur->_col = BLACK;
					grandfather->_col = RED;  
				*/
			*/ 
			
		}
		else  //父亲出现在祖父的右边
		{
			Node* uncle = grandfather->_left; //叔叔在左子树 
			/*
			情况一：叔叔存在，且叔叔和父亲都是红色，那么就需要将父亲
			和叔叔结点的颜色变成黑色，再将祖父的颜色变成红色，
			继续向上调整，更新孩子、父亲、祖父、叔叔的位置
			*/
			/*
				情况二：叔叔不存在
				/*
				 	1、新增结点出现在父亲的右边，直线情况，左单旋处理
				 	旋转完后parent去做父亲的根，grandfather做父亲
				 	的左子树
							//调节颜色，根为黑，左右孩子为红
					2、新增结点出现在父亲的左边，会出现折现的情况，
					引发双旋，旋转完后，cur变成根，
					parent和grandfaher去做cur的左右孩子
						   //调节颜色,根结点为黑，左右孩子为红
				*/
			*/	
		}
		
	}
	//如果父亲不存在为了保证根结点是黑色的，这里一定得将根结点处理为黑色
	_root->_col = BLACK;
}

    添加新节点后维护红黑树属性的主要逻辑

    //1、父亲一定存在的情况，叔叔存在/不存在 父亲叔叔结点颜色为红色
while (parent && parent->_col == RED) //父亲存在且父亲为红色
{
	Node* grandfather = parent->_parent;  //祖父
	//如果父亲和叔叔结点颜色都是红色
	if (parent == grandfather->_left)  
	{
		Node* uncle = grandfather->_right;  
		if (uncle && uncle->_col == RED)  //对应情况：uncle存在且为红
		{
			//处理：父亲和叔叔变成黑色，祖父变成红色，继续向上调整
			uncle->_col = parent->_col = BLACK; 
			grandfather->_col = RED;
			//向上调整
			cur = grandfather;  //调整孩子
			parent = cur->_parent;//调整父亲
			
		}
		else   //uncle不存在，uncle存在且为黑
		{
			//直线情况(cur在parent的左边)：只考虑单旋，以grandfather为旋转点进行右单旋转，
			//旋转完后将祖父的颜色变成红色，将父亲的颜色变成黑色
			if (parent->_left == cur) 
			{
				RotateR(grandfather);
				parent->_col = BLACK;
				grandfather->_col = RED;
			}

    trie树 c语言实现_红黑树 c语言实现_c语言实现数组实现map
    
			else  //parent->_right == cur 
			{	
				//折线情况(cur在parent的右边)：这里会引发双旋
				RotateL(parent);  //以parent为旋转点进行左单旋
				RotateR(grandfather); //以grandfather为旋转点进行右单旋转
				//旋转完后cur会去做树的根，那么设置为黑色，
				//为了保证每条路径的黑色结点个数相同，grandfather结点颜色设置为红
				cur->_col = BLACK;
				grandfather->_col = RED;  //黑色	结点个数相同
			}
		}
	}
	else //父亲在右子树
	{
			Node* uncle = grandfather->_left; //叔叔在左子树 
			if (uncle&& uncle->_col == RED)  //情况一处理：叔叔存在，且叔叔的颜色是红色的（包含了父亲的颜色是红色的情况）
			{
				//根据情况一处理即可：叔叔和父亲变黑，
				//祖父变红(目的是为了每条路径的黑色结点个数相同)，继续向上
				cur = grandfather;  //孩子
				parent = cur->_parent;//父亲
				
			}
			else //叔叔不存在 
			{
				if (cur == parent->_right)  //新增结点在父亲的右边，直线情况左单旋处理
				{
					//左单旋转，以grandfather为旋转点，旋转完后parent去做新的根，grandfather去做左子树
					RotateL(grandfather);
					//调节颜色
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				else //新增结点在父亲的左边，折线情况，引发双旋
				{
					//处理：以parenrt为旋转点做右单旋，再以grandfather为旋转点做左单旋
					RotateR(parent);  //右旋
					RotateL(grandfather); //左旋
					parent->_col = grandfather->_col = RED;
					cur->_col = BLACK;
				}
				break;
			}
			
		}
	_root->_col = BLACK;
}

    拆解讨论：

    下面只列出了父母在祖父左侧的情况，而父母在祖父右侧的情况只是颠倒过来的。

    Node* uncle = grandfather->_right;  
if (uncle && uncle->_col == RED)  //对应情况：uncle存在且为红
{
	//处理：父亲和叔叔变成黑色，祖父变成红色，继续向上调整
	uncle->_col = parent->_col = BLACK; 
	grandfather->_col = RED;
	//向上调整
	cur = grandfather;  //调整孩子
	parent = cur->_parent;//调整父亲
		
}

    在这里插入图片描述

    else   //uncle不存在，uncle存在且为黑
{
	//直线情况(cur在parent的左边)：只考虑单旋，以grandfather为旋转点进行右单旋转，
	//旋转完后将祖父的颜色变成红色，将父亲的颜色变成黑色
	if (parent->_left == cur) 
	{
		RotateR(grandfather);
		parent->_col = BLACK;
		grandfather->_col = RED;
	}
	else  //parent->_right == cur 
	{	
		//双旋转
	}
}

    在这里插入图片描述

    //折线情况(cur在parent的右边)：这里会引发双旋
RotateL(parent);  //以parent为旋转点进行左单旋
RotateR(grandfather); //以grandfather为旋转点进行右单旋转
//旋转完后cur会去做树的根，那么设置为黑色，
//为了保证每条路径的黑色结点个数相同，grandfather结点颜色设置为红
cur->_col = BLACK;
grandfather->_col = RED;

    在这里插入图片描述

    旋转

    void RotateR(Node* parent) //右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR) subLR->_parent = parent;  //防止subLR为nullptr
		subL->_right = parent;
		Node* parent_parent = parent->_parent; //指针备份
		parent->_parent = subL;
		if (_root == parent) //如果parent就是树的根 

    c语言实现数组实现map_trie树 c语言实现_红黑树 c语言实现
    
		{
			_root = subL;  //subL取代parent
			_root->_parent = nullptr;
		}
		else  //如果parent并不是树的根
		{
			if (parent_parent->_left == parent) parent->_left = subL;
			else parent_parent->_right = subL;
			subL->_parent = parent_parent; //subL去做parent_parent的孩子
		}
	}
	
	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL) subRL->_parent = parent;
		subR->_left = parent;
		Node* parent_parent = parent->_parent;
		parent->_parent = subR;
		if (_root == parent)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent_parent->_left == parent) parent_parent->_left = subR;
			else parent_parent->_right = subR;
			subR->_parent = parent_parent;
		}
	}

    验证

    /*
	红黑树的几点性质在于：
	1、根结点必须是红色的
	2、不会出现连续的红色结点
	3、所有路径的黑色结点个数是相同的
*/
bool _CheckBlance(Node* root, int isBlackNum, int count) 
{
	if (!root) 
	{
		if (isBlackNum != count) 
		{
			printf("黑色结点个数不均等n");
			return false;
		}
		return true; //遍历完整棵树，如果以上列举的非法情况都不存在就返回true
	}
	//检查是否出现连续的红色结点
	if (root->_col == RED && root->_parent->_col == RED) 
	{
		printf("出现了连续的红色结点n");
		return false;
	} 
	//走前序遍历的过程中记录每一条路径黑色结点的个数
	if (root->_col == BLACK) count++;
	
	//递归左右子树
	return _CheckBlance(root->_left, isBlackNum, count) && 
			_CheckBlance(root->_right, isBlackNum, count);
}
//验证红黑树
bool CheckBlance()
{
	if (!_root) return true;  //树为null
	//根结点是黑色的
	if (_root->_col != BLACK) 
	{
		printf("根结点不是黑色的n");
		return false;
	}
	//每一条路径黑色结点的个数必须是相同的，
	int isBlcakNum = 0;
	Node* left = _root; 
	while (left) 
	{
		if (left->_col == BLACK) isBlcakNum++; // 统计某一条路径的所以黑色结点个数
		left = left->_left;
	}
	//检查连续的红色结点，检查每一条路径的黑色结点个数是否相等
	return _CheckBlance(_root, isBlcakNum ,0);
}

    红黑树与AVl树的比较

    红黑树与AVL树的比较

    红黑树 树和 AVL 树都是高效的平衡二叉树。增删改查的时间复杂度为O(log n)。红黑树不追求绝对的平衡。只需要保证最长路径不超过最短路径的2倍，相对来说减少了插入和旋转的次数，所以在频繁增删的结构中性能优于AVL树，实现红黑树比较简单红黑树 c语言实现，所以实际使用的红黑树比较多。 .

    红黑树的应用

    C++ STL 库 – map/set、mutil_map/mutil_setJava 库 linux 内核和其他一些库

    完整的代码博主已经放在了git上，读者可以参考

    红黑树的实现。

    总结

    C语言实现红黑树的详细步骤+代码就到这里了。更多C语言红黑树相关内容，请搜索第一财经站长站往期文章或继续浏览下方相关文章。希望大家以后多多支持第一财经站长站！

    以上是C语言实现红黑树的详细步骤+代码的详细介绍。欢迎大家对C语言实现红黑树的详细步骤+代码内容提出宝贵意见

    站内大部分资源收集于网络，若侵犯了您的合法权益，请联系我们删除！
    欧资源网 » 【知识点】C语言实现红黑树详细步骤+代码

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用？
    本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了？
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。若排除这种情况，可在对应资源底部留言，或 联络我们.。
    找不到素材资源介绍文章里的示例图片？
    对于PPT，KEY，Mockups，APP，网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台
    欧资源网

    欧资源网 钻石

    分享到：

    相关推荐

    发表评论