红黑树(RBTree)的分析和实现

二叉排序树在查找方面提供了很大的方便，但是对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