数据结构 -- 红黑树

一、红黑树

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<class K,class V> struct RBTreeNode {	RBTreeNode<K,V> *_left;	RBTreeNode<K,V> *_right;	RBTreeNode<K,V> *_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 K,class V> class RBTree {	typedef RBTreeNode<K,V> 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<<"错误：出现连续红色节点"<root->_key<<endl;	return false;	}	if(root->_col == BLACK)	++count;	//每条路径中黑色节点数量相等	if(root->_left == NULL && root->_right == NULL && k != count)	{	cout<<"错误：黑色节点数目不等"<<endl;	return false;	}	return _IsBlance(root->_left,k,count) && _IsBlance(root->_right,k,count);	} protected:	Node *_root; };

3、总结：

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