数据结构--红黑树-创新互联

一、红黑树

创新互联是一家专业提供鄂托克前企业网站建设,专注与成都网站制作、网站设计、H5网站设计、小程序制作等业务。10年已为鄂托克前众多企业、政府机构等服务。创新互联专业的建站公司优惠进行中。

1、定义:红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是Red或Black。通过对任何一条从根到叶子简单路径上的颜色来约束,红黑树保证最长路径不超过最短路径的两倍,因而近似于平衡。

2、性质:

  • 每个节点,非黑即红;

  • 根节点为黑色;

  • 如果一个节点是红色的,则它的2个子节点是黑色的(没有连续的红节点);

  • 对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。(每条路径的黑色节点的数量相等);

  • 每个叶子节点都是黑色的(这里的叶子节点是指的NIL节点(空节点));

二、红黑树相关

1、红黑树保证最长路径不超过最短路径的两倍,因而近似于平衡。

    数据结构 -- 红黑树

    如图所示,插入节点后,为了保持红黑树,最长路径最多是最短路径的 2倍。

2、插入节点:

 注:cur为当前节点,parent父节点,grandpa祖父节点,uncle叔叔节点

(1)第一种情况

数据结构 -- 红黑树

cur为红,parent为红,grandpa为黑,uncle存在且为红 --->

则将parent,uncle改为黑,grandpa改为红,然后把grandpa当成cur,继续向上调整。

数据结构 -- 红黑树

(2)第二种情况

数据结构 -- 红黑树

cur为红,parent为红,grandpa为黑,uncle不存在/uncle为黑 --->

parent为grandpa的左孩子,cur为p的左孩子,则进行右单旋转;相反,p为g的右孩子,cur为p的右孩子,则进行左单旋转;

parent、grandpa变色--parent变黑,grandpa变红。

数据结构 -- 红黑树

(3)第三种情况

数据结构 -- 红黑树

cur为红,parent为红,grandpa为黑,uncle不存在/uncle为黑 -->

parent为grandpa的左孩子,cur为parent的右孩子,则针对parent做左单旋转;相反,parent为grandpa的右孩子,cur为p的左孩子,则针对parent做右单旋转,则转换成了情况2。

3、判断红黑树:根据红黑树的性质进行判定。

4、红黑树和AVL树的比较:

    红黑树和AVL树都是高效的平衡二叉树,增删查改的时间复杂度都是O(lg(N));

    红黑树的不追求完全平衡,保证最长路径不超过最短路径的2倍,相对而言,降低了旋转的要求,所以性能跟AVL树差不多,但是红黑树实现更简单,所以实际运用中红黑树更多。

三、相关实现

1、节点

enum Color
{
	RED,BLACK,
};
template
struct RBTreeNode
{
	RBTreeNode *_left;
	RBTreeNode *_right;
	RBTreeNode *_parent;
	K _key;
	V _value;
	Color _col;
	RBTreeNode(const K& key,const V& value)
		:_key(key)
		,_value(value)
		,_col(RED)
		,_left(NULL)
		,_right(NULL)
		,_parent(NULL)
	{}
};

2、红黑树及相关实现

template
class RBTree
{
	typedef RBTreeNode Node;
public:
	RBTree()
		:_root(NULL)
	{}
	
	bool Insert(const K& key,const V& value)
	{
		//插入节点
		if(_root == NULL)
		{
			_root=new Node(key,value);
			return true;
		}
		Node *cur=_root;
		Node *parent=NULL;
		while(cur)
		{
			if(cur->_key < key)
			{
				parent=cur;
				cur=cur->_right;
			}
			else if(cur->_key > key)
			{
				parent=cur;
				cur=cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur=new Node(key,value);
		if(parent->_key < key)
		{
			parent->_right=new Node(key,value);
			parent->_right=parent;
		}
		else
		{
			parent->_left=new Node(key,value);
			parent->_right=parent;
		}
		//更正信息
		while(cur != _root && parent->_col == RED)
		{
			Node *grandpa=parent->_right;
			if(grandpa->_left == parent)
			{
				Node *uncle=grandpa->_right;
				if(uncle && uncle->_col == RED) // 第1种情况
				{
					parent->_col=uncle->_col=BLACK;
					grandpa->_col=RED;
					//继续向上调
					cur=grandpa;
					parent=cur->_parent;
				}
				else
				{
					// 第3种情况:双旋转 --> 单旋转
					if(cur == parent->_right)
					{
						RotateL(parent);//左单旋
						swap(cur,parent);
					}
					//第2种情况
					parent->_col=BLACK;
					grandpa->_col=RED;
					RotateR(grandpa);//右单旋
					break;
				}
			}
			else
			{
				Node *uncle=grandpa->_left;
				if(uncle && uncle->_col == RED) // 第1种情况
				{
					parent->_col=uncle->_col=BLACK;
					grandpa->_col=RED;
					//继续向上调
					cur=grandpa;
					parent=cur->_parent;
				}
				else  
				{
					// 第3种情况:双旋转 --> 单旋转
					if(cur == parent->_left)
					{
						RotateR(parent);//左单旋
						swap(cur,parent);
					}
					//第2种情况
					parent->_col=BLACK;
					grandpa->_col=RED;
					RotateR(grandpa);//右单旋
					break;
				}
			}
		}
		return true;
	}

	bool IsBlance()
	{
		if(_root == NULL) return;
		if(_root->_col == RED) return false;
		int k=0;
		Node *cur=_root;
		while(cur)
		{
			if(cur->_col == BLACK)
				++k;
			cur=cur->_left;
		}
		int count=0;
		return _IsBlance(_root,k,count);
	}

protected:
	bool _IsBlance(Node *root,const int k,int count)
	{
		if(root == NULL) return true;
		//红黑树父子节点颜色不能相同
		if(root->_col == RED && root->_parent->_col == RED)
		{
			cout<<"错误:出现连续红色节点"_key<_col == BLACK)
			++count;
		//每条路径中黑色节点数量相等
		if(root->_left == NULL && root->_right == NULL && k != count)
		{
			cout<<"错误:黑色节点数目不等"<_left,k,count) && _IsBlance(root->_right,k,count);
	}

protected:
	Node *_root;
};

3、总结:

    红黑树也是一种平衡二叉树,通过存储节点的颜色红黑,对其进行处理,使其处于平衡状态。红黑树插入节点时,主要分三种情况,按照不同情况处理。删除时和AVL树类似,只是需要注意旋转及更该节点颜色。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


标题名称:数据结构--红黑树-创新互联
转载源于:http://scyanting.com/article/ccgiid.html