一、红黑树

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、节点

enumColor{RED,BLACK,};template<classK,classV>structRBTreeNode{RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;K_key;V_value;Color_col;RBTreeNode(constK&key,constV&value):_key(key),_value(value),_col(RED),_left(NULL),_right(NULL),_parent(NULL){}};

2、红黑树及相关实现

template<classK,classV>classRBTree{typedefRBTreeNode<K,V>Node;public:RBTree():_root(NULL){}boolInsert(constK&key,constV&value){//插入节点if(_root==NULL){_root=newNode(key,value);returntrue;}Node*cur=_root;Node*parent=NULL;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(key,value);if(parent->_key<key){parent->_right=newNode(key,value);parent->_right=parent;}else{parent->_left=newNode(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;}}}returntrue;}boolIsBlance(){if(_root==NULL)return;if(_root->_col==RED)returnfalse;intk=0;Node*cur=_root;while(cur){if(cur->_col==BLACK)++k;cur=cur->_left;}intcount=0;return_IsBlance(_root,k,count);}protected:bool_IsBlance(Node*root,constintk,intcount){if(root==NULL)returntrue;//红黑树父子节点颜色不能相同if(root->_col==RED&&root->_parent->_col==RED){cout<<"错误:出现连续红色节点"<root->_key<<endl;returnfalse;}if(root->_col==BLACK)++count;//每条路径中黑色节点数量相等if(root->_left==NULL&&root->_right==NULL&&k!=count){cout<<"错误:黑色节点数目不等"<<endl;returnfalse;}return_IsBlance(root->_left,k,count)&&_IsBlance(root->_right,k,count);}protected:Node*_root;};

3、总结:

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