功能比较完整的红黑树

2009-03-24 16:08

//key code


#define RED true
#define BLACK false

struct Node{
       int key;
       Node *p,*left,*right;
       bool color;
      
       Node(){
           p = left = right = 0;
           color = RED;
       }
};

class RBT{
      public:
         RBT();
        
         Node* TreeSearch(int key);
         Node* TreeMax(Node* x);
         Node* TreeMin(Node* x);
         Node* TreeSuc(Node* x);
         Node* TreePre(Node* x);
        
         void LeftRotate(Node* x);
         void RightRotate(Node* x);
        
         void TreeInsert(int key);
         Node* TreeDel(Node* x);
        
         void TreeInsertFix(Node* x);
         void TreeDelFix(Node* x);
        
         void MidOrder();
         void PreOrder();
     
      private:
         void MidOrder(Node* cur);
         void PreOrder(Node* cur);
        
         Node* Root;
         Node* nil;
};

RBT::RBT(){
     nil = new Node;
     nil->color = BLACK;
     Root = nil;
}

Node* RBT::TreeSearch(int key){
      if(Root==nil) return 0;
     
      Node* t = Root;
      while(t!=nil){
           if(t->key==key) break;
           if(t->key>=key) t = t->left;
           else t = t->right;
      }
     
      return t;
}

Node* RBT::TreeMax(Node* x){
      while(x->right!=nil) x = x->right;
      return x;
}
     
Node* RBT::TreeMin(Node* x){
      while(x->left!=nil) x = x->left;
      return x;
}

Node* RBT::TreeSuc(Node* x){
      if(x->right!=nil) return TreeMin(x->right);
     
      Node* y = x->p;
      while(y!=nil){
           if(x == y->left) break;
           x = y;
           y = y->p;
      }
     
      return y;
}
     
Node* RBT::TreePre(Node* x){
      if(x->left!=nil) return TreeMax(x->left);
     
      Node* y = x->p;
      while(y!=nil){
           if(x == y->right) break;
           x = y;
           y = y->p;
      }
     
      return y;
}

void RBT::LeftRotate(Node* x){
     Node* y = x->right;
    
     if(x->p==nil) Root = y;
     else if(x == x->p->left) x->p->left = y;
     else x->p->right = y;
    
     y->p = x->p;
     x->p = y;
    
     x->right = y->left;
     if(y->left!=nil)
        y->left->p = x;
     y->left = x;
}
    
void RBT::RightRotate(Node* x){
     Node* y = x->left;
    
     if(x->p==nil) Root = y;
     else if(x == x->p->left) x->p->left = y;
     else x->p->right = y;
    
     y->p = x->p;
     x->p = y;
    
     x->left = y->right;
     if(y->right!=nil)
        y->right->p = x;
     y->right = x;
}

void RBT::TreeInsert(int key){
     if(Root==nil){
        Root = new Node;
        Root->key = key;
        Root->left = Root->right = nil;
        Root->p = nil;
        Root->color = BLACK;
        return;
     }
    
     Node* x;
     Node* t = Root;
     Node* p;
    
     x = new Node;
     x->key = key;
     while(t!=nil){
          p = t;
          if(x->key<=t->key) t = t->left;
          else t = t->right;
     }
    
     if(p->key>=x->key){
        p->left = x;
        x->p = p;
     }
     else{
         p->right = x;
         x->p = p;
     }
     x->left = nil;
     x->right = nil;
    
     TreeInsertFix(x);
}

void RBT::TreeInsertFix(Node* x){
     Node *y,*z;
    
     while(x->p->color==RED){
           y = x->p->p;
           if(x->p==y->left) z = y->right;
           else z = y->left;
         
           if(z->color==RED){
              x->p->color = BLACK;
              y->color = RED;
              z->color = BLACK;
              x = y;
           }
           else if(z==y->right){
                   if(x==x->p->right){
                      LeftRotate(x->p);
                      x = x->left;
                   }
             
                   RightRotate(y);
                   y->p->color = BLACK;
                   y->color = RED;
           }
           else{
               if(x==x->p->left){
                  RightRotate(x->p);
                  x = x->right;
               }
              
               LeftRotate(y);
               y->p->color = BLACK;
               y->color = RED;
           }
     }
     Root->color = BLACK;
}

Node* RBT::TreeDel(Node* x){
      Node *y,*z;
     
      if(x->left==nil||x->right==nil)
         y = x;
      else y = TreeSuc(x);
     
      if(y->right!=nil)
         z = y->right;
      else z = y->left;
           
      z->p = y->p;
        
      if(y->p==nil) Root = z;
      else if(y==y->p->left) y->p->left = z;
      else y->p->right = z;
     
      x->key = y->key;
      if(y->color==BLACK) TreeDelFix(z);
     
      return y;
}

void RBT::TreeDelFix(Node* x){
     Node* w;
     while(x!=Root&&x->color==BLACK){
          
           if(x==x->p->left){
              w = x->p->right;
             
              if(w->color==RED){
                 LeftRotate(x->p);
                 x->p->color = RED;
                 w->color = BLACK;
                 w = x->p->right;
              }
              if(w->right->color==BLACK&&w->left->color==BLACK){
                   w->color = RED;
                   x = x->p;
              }
              else{
                  if(w->left->color==RED){
                     RightRotate(w);
                     w->p->color = BLACK;
                     w->color = RED;
                     w = w->p;
                  }
                  LeftRotate(x->p);
                  w->color = w->left->color;
                  w->left->color = BLACK;
                  w->right->color = BLACK;
                  x = Root;
              }
           }
          
           else{
               w = x->p->left;
             
               if(w->color==RED){
                 RightRotate(x->p);
                 x->p->color = RED;
                 w->color = BLACK;
                 w = x->p->right;
               }
               if(w->right->color==BLACK&&w->left->color==BLACK){
                   w->color = RED;
                   x = x->p;
               }
               else{
                   if(w->right->color==RED){
                     LeftRotate(w);
                     w->p->color = BLACK;
                     w->color = RED;
                     w = w->p;
                   }
                   RightRotate(x->p);
                   w->color = w->right->color;
                   w->right->color = BLACK;
                   w->left->color = BLACK;
                   x = Root;
               }
           }
              
     }
     x->color = BLACK;
}

void RBT::MidOrder(){
     if(Root==nil) return;
     MidOrder(Root);
}
    
void RBT::PreOrder(){
     if(Root==nil) return;
     PreOrder(Root);
}

void RBT::MidOrder(Node* cur){
     if(cur==nil) return;
    
     MidOrder(cur->left);
     cout<<cur->key<<" "<<cur->color<<" ";
     MidOrder(cur->right);
}
    
void RBT::PreOrder(Node* cur){
     if(cur==nil) return;
    
     cout<<cur->key<<" "<<cur->color<<" ";
     PreOrder(cur->left);
     PreOrder(cur->right);
}


注：当时我写的想吐血。。。。。。太难写了。。。。。。