二叉排序树在查找方面提供了很大的方便，但是对worst-case查找/插入/删除/求最值 得时间复杂度都为O(n).
红黑树可以保证在worst-case下查找/插入/删除等的复杂度得到O(lgN)。红黑树保持如下特性：
1。节点不是red 就是black
2。root为black
3。所有的leaf为black
4。所有red node 的孩子为black
5。任一node通过左子树和右子树到达叶子节点的black node个数相同
可以证明 红黑树的最大高度为2lg(N+1)，所以在红黑树上的操作的时间复杂度为O(lgN)。 其插入和删除操作的时间复杂度都是O(lgN),插入最多需要2次旋转，删除最多需要3次旋转。
其插入和删除操作可能会与红黑树的特性相违背，所以需要修正。在具体的实现中 1）插入的节点都是red。如果其父节点为red,就违背了条件4 2)如果删除的节点为black，违背了条件5需要修正。3）需要一个NIL来表示叶子节点，共享该叶子节点，且为root的父节点，节省空间。
提供了查找 插入 删除 后继 最值操作。
具体实现：
//implement red-black tree
/*
*xiaopei
*06/11/24
*/
#ifndef RBTREE_H
#define RBTREE_H
template <typename Type>
struct TreeNode
{
Type key;
int color;
TreeNode *parent,*left,*right;
};
template <typename Type>
class RBTree
{
private:
enum
{
RED,BLACK
}Color;
Type key;
int color;
TreeNode<Type> *parent,*left,*right;
TreeNode<Type> *NIL;//
TreeNode<Type> *ROOT;
void left_rotate(TreeNode<Type> *&rotate);
void right_rotate(TreeNode<Type> *&rotate);
void RB_insert_fixup(TreeNode<Type>* &node);
void RB_delete_fixup(TreeNode<Type>* &node);
public:
//const static TreeNode<Type>* nil;
RBTree();
TreeNode<Type> *successor(const TreeNode<Type> *node);
TreeNode<Type>* insert(Type key);
TreeNode<Type>* search(Type key);
TreeNode<Type>* remove(Type key);
TreeNode<Type> *maxnum(TreeNode<Type>*node);
TreeNode<Type>* minnum(TreeNode<Type>*node);
TreeNode<Type>* getRoot();
void inorder(TreeNode<Type>*node);
void test()
{
this->insert(1);
this->insert(2);
left_rotate(ROOT);
}
~RBTree();
};
//template <typename Type>
//const TreeNode<Type>* RBTree<Type>::nil=NIL;
template <typename Type>
RBTree<Type>::RBTree()
{
NIL=new TreeNode<Type>;
NIL->color=BLACK;
NIL->key=123456;
NIL->left=0;
NIL->right=0;
NIL->parent=0;
ROOT=NIL;
}
template<typename Type>
RBTree<Type>::~RBTree()
{
delete NIL;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::maxnum(TreeNode<Type>*node)
{
//如果是空树怎么办？
TreeNode<Type> *max=node;
while(max->right!=NIL)
max=max->right;
return max;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::minnum(TreeNode<Type>*node)
{
//如果是空树怎么办？
TreeNode<Type> *min=node;
while(min->left!=NIL)
min=min->left;
return min;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::successor(const TreeNode<Type>* node)
{
if(node->right!=NIL)
return minnum(node->right);
const TreeNode<Type>*s=node;
const TreeNode<Type>*p=s->parent;
while(p!=NIL&&s==p->right){s=p;p=s->parent;}
return const_cast<TreeNode<Type>*>(p);
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::getRoot()
{
TreeNode<Type>*root=ROOT;
return root;
}
template<typename Type>
void RBTree<Type>::left_rotate(TreeNode<Type>*& _rotate)
{
if(_rotate->right==NIL){cout<<"没有右孩子，不能左旋";return ;}//right child is nil, so can not left rotate
TreeNode<Type>* r = _rotate->right;
TreeNode<Type>*t,*rotate=_rotate;
//deal with r->left
rotate->right=r->left;
r->left->parent=rotate;
//deal with r
// t=rotate->parent;
// r->parent=t;//rotate 被修改成了NIL 为什么？
// rotate=rotate->parent;
if(rotate->parent==NIL)
{ROOT=r;r->parent=NIL;}
else if(rotate==rotate->parent->left)
rotate->parent->left=r;
else
rotate->parent->right=r;
r->parent=rotate->parent;
//deal with rotate
rotate->parent=r;
r->left=rotate;
}
template<typename Type>
void RBTree<Type>::right_rotate(TreeNode<Type>* &_rotate)
{
TreeNode<Type>*rotate=_rotate;//不知道为什么，如果直接对_rotate操作，在过程中会改变_rotate得值
if(rotate->left==NIL)return ;//left child is NIL, so can not right rotate
TreeNode<Type>* l = rotate->left;
//deal with l->right
//cout<<"key"<<rotate->parent->key<<endl;
l->right->parent=rotate;
rotate->left=l->right;
//deal with l
l->parent=rotate->parent;
if(rotate->parent==NIL)
{ROOT=l;l->parent=NIL;}
else if(rotate==rotate->parent->left)
rotate->parent->left=l;
else
rotate->parent->right=l;
//deal with rotate
rotate->parent=l;
l->right=rotate;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::insert(Type key)
{
TreeNode<Type> *node=new TreeNode<Type>;
TreeNode<Type> *down=ROOT;
TreeNode<Type> *s=NIL;
while(down!=NIL)
{
s=down;
if(key<down->key)
down=down->left;
else
down=down->right;
}//找到合适位置
node->parent=s;
if(s==NIL)
{ROOT=node;node->parent=NIL;}
else if(key<s->key)
s->left=node;
else
s->right=node;
node->key=key;
node->left=NIL;
node->right=NIL;
node->color=RED;
RB_insert_fixup(node);
return node;
}
template<typename Type>
void RBTree<Type>::RB_insert_fixup(TreeNode<Type>*& change)
{
// TreeNode<Type>*change=node;
TreeNode<Type>*father;
TreeNode<Type>*uncle;
while(change->parent->color==RED)
{
father=change->parent;
if(father==father->parent->left)
{
uncle=father->parent->right;//父节点的兄弟
if(uncle->color==RED)//uncle同样为red
{
father->color=BLACK;
uncle->color=BLACK;
father->parent->color=RED;
change=father->parent;//进行循环
}else
{
//cout<<"uncle node color=black"<<endl;
if(change==father->right)//内插入，左旋
{
change=father;
//cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;
left_rotate(change);
father=change->parent;
//cout<<"after rotate key:"<<change->key<<" color "<<change->color<<endl;
// cout<<"内插入"<<endl;
}
//外插入
father->color=BLACK;
father->parent->color=RED;//改变颜色
// cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;
right_rotate(father->parent);
// cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;
}
}
else
{
uncle=father->parent->left;//父节点的兄弟
if(uncle->color==RED)//uncle同样为red
{
father->color=BLACK;
uncle->color=BLACK;
father->parent->color=RED;
change=father->parent;//进行循环
}else
{
if(change==father->left)//内插入
{
change=father;
right_rotate(change);
father=change->parent;
}
//外插入
father->color=BLACK;
father->parent->color=RED;
left_rotate(father->parent);
}
}
}
ROOT->color=BLACK;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::search(Type key)
{
TreeNode<Type> *p=ROOT;
while(p!=NIL&&p->key!=key)
{
if(key<p->key)
p=p->left;
else
p=p->right;
}
return p;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::remove(Type key)
{
TreeNode<Type> *p = this->search(key);
if(p==NIL)
return p;
//rn 为需要改变的节点，找到得key节点，如果只有一个孩子或者没有孩子，则需要被删除的就是该节点，否则（两个孩子）
//需要删除的是直接后继节点（首先将key节点用后继节点代替）后继节点没有左孩子
//最后rn最多只有一个孩子
TreeNode<Type> *rn=NIL;
TreeNode<Type> *act;
if(p->left==NIL || p->right==NIL)
rn=p;
else
rn = this->successor(p);
if(rn->left!=NIL)//如果被删除的节点左孩子不空，则使用act纪录(key节点只有左孩子的情况)
act=rn->left;
else//act纪录key没有孩子，有右孩子，双子情况
act=rn->right;
act->parent=rn->parent;//更新父节点
if(rn->parent==NIL)
ROOT=act;//已经将act得parent修改成NIL了
else if(rn == rn->parent->left)
rn->parent->left=act;
else
rn->parent->right=act;
if(rn!=p)//key有两个孩子时，实际删除的是p的直接后继rn节点，所以需要将后继节点的信息复制key节点中
p->key=rn->key;
if(rn->color==BLACK)
RB_delete_fixup(act);
return rn;
}
//删除一个黑色节点后导致两边的bh不同。
template<typename Type>
void RBTree<Type>::RB_delete_fixup(TreeNode<Type> *&_node)
{
TreeNode<Type>*father,*brother,*node;
node=_node;
father=node->parent;
while(node!=ROOT&&node->color==BLACK)//如果color(x)为red，只需要讲color(x)=black就行了
{
if(node=father->left)//color(node)=black,father左孩子得black nodes(m-1) =father右孩子的black nodes(m) -1
{
brother=father->right;
if(brother->color==RED)//color(father)=black,********************case 1
{
brother->color=BLACK;
father->color=RED;
left_rotate(father);//修改了树结构,这一步后brother为node得祖父节点并且brother右孩子的black nodes = m不变
brother=parent->right;//修正node得兄弟节点，现在color(father)=black right(father)=black,并且father->left得
//black nodes还为m-1,father->right得black nodes = m
}
//如果兄弟为黑，则根据兄弟的孩子来区分,color(Node)=black,color(brother)=black,color(father)未知
if(brother->left->color==BLACK&&brother->right->color==BLACK)//********************case 2
{
brother->color=RED;//fater右孩子的black nodes = m-1
node=father;//如果father为red，则循环结束，将father改为black，则整个以father为根的子树左右孩子的black nodes都为m
}
else
{
if(brother->right->color==BLACK)//右孩子为黑色********************case 3
{
brother->left->color=BLACK;
brother->color=RED;
right_rotate(brother);
brother=father->right;//brother的右孩子为red
}
//if(brother->right->color==RED)************************case 4
father->color=BLACK;
brother->right->color=BLACK;//red修改成black
brother->color=father->color;
//执行旋转后，brother为node得祖父，brother右孩子得black nodes=m,做孩子的black nodes=m(+father为黑色)
left_rotate(father);
node=ROOT;//结束
}
}
}
node->color=BLACK;
}
template<typename Type>
void RBTree<Type>::inorder(TreeNode<Type>*node)
{
if(node!=NIL)
{
inorder(node->left);
if(node->color==RED)
if(node->left->color==RED||node->right->color==RED)
cout<<"wrong"<<" ";
cout<<node->key<<" ";
inorder(node->right);
}
}
#endif
