#include  < iostream >
using   namespace  std;

const   int  MAXSIZE  =   100 ;
const   int  R  =   0 ;
const   int  B     =   1 ;
const   int  NIL  =   0 ;

class  RBTree
{
public :
    RBTree();
     int  Root();
     int  Size();
     int  Key( int );
     int  Pointer( int );
     int  Search( int ,  int );
     int  Minimum( int );
     int  Maximum( int );
     int  successor( int );
     int  predecessor( int );
     void  LeftRotate( int );
     void  RightRotate( int );
     void  Insert( int );
     void  InsertByPointer( int );
     void  InsertFixup( int );
     void  Delete( int );
     void  DeleteByPointer( int );
     void  DeleteFixup( int );
     void  Travel( int );
private :
     int  key[MAXSIZE];
     int  left[MAXSIZE];
     int  right[MAXSIZE];
     int  color[MAXSIZE];
     int  p[MAXSIZE];
     int  stack[MAXSIZE];
     int  root;
     int  top;
     int  size;
} ;

RBTree::RBTree()
{
    root  =  NIL;  // 默认空树root为NIL;
    top  =   0 ;
    size  =   0 ;
    memset(right, NIL,  sizeof (right));
    memset(left, NIL,  sizeof (left));
    memset(p, NIL,  sizeof (p));
    color[NIL]  =  B;
}

int  RBTree::Root()
{
     return  root;
}

int  RBTree::Size()
{
     return  size;
}

int  RBTree::Key( int  x)
{
     return  key[x];
}

int  RBTree::Pointer( int  k)
{
     return  Search(Root(), k);
}

int  RBTree::Minimum( int  x)
{
     while  (left[x]  !=  NIL)
        x  =  left[x];
     return  x;
}

int  RBTree::Maximum( int  x)
{
     while  (right[x]  !=  NIL)
        x  =  right[x];
     return  x;
}

int  RBTree::Search( int  x,  int  k)
{
     while  (x  !=  NIL  &&  k  !=  key[x])
     {
         if  (k  <  key[x])
            x  =  left[x];
         else
            x  =  right[x];
    }
     return  x;
}

int  RBTree::successor( int  x)
{
     if  (right[x]  !=  NIL)
         return  Minimum(right[x]);
     int  y  =  p[x];
     while  (y  !=  NIL  &&  x  ==  right[y])
     {
        x  =  y;
        y  =  p[y];
    }
     return  y;
}

int  RBTree::predecessor( int  x)
{
     if  (left[x]  !=  NIL)
         return  Maximum(left[x]);
     int  y  =  p[x];
     while  (y  !=  NIL  &&  x  ==  left[y])
     {
        x  =  y;
        y  =  p[y];
    }
     return  y;
}


void  RBTree::LeftRotate( int  x)
{
     int  y  =  right[x];
    right[x]  =  left[y];
    p[left[y]]  =  x;
    p[y]  =  p[x];
     if  (p[x]  ==  NIL)
        root  =  y;
     else
     {
         if  (x  ==  left[p[x]])
            left[p[x]]  =  y;
         else
            right[p[x]]  =  y;
    }
    left[y]  =  x;
    p[x]  =  y;
}

void  RBTree::RightRotate( int  x)
{
     int  y  =  left[x];
    left[x]  =  right[y];
    p[right[y]]  =  x;
    p[y]  =  p[x];
     if  (p[x]  ==  NIL)
        root  =  y;
     else
     {
         if  (x  ==  left[p[x]])
            left[p[x]]  =  y;
         else
            right[p[x]]  =  y;
    }
    right[y]  =  x;
    p[x]  =  y;
}

void  RBTree::Insert( int  k)
{
     int  z;
     if  (top  >   0 )
        z  =  stack[ -- top];
     else
        z  =   ++ size;
    key[z]  =  k;
    InsertByPointer(z);
}

void  RBTree::Delete( int  k)
{
     int  z  =  Search(Root(), k);
     if  (z  !=  NIL)
     {
        stack[top ++ ]  =  z;
        size -- ;
        DeleteByPointer(z);
    }
}

void  RBTree::InsertByPointer( int  z)
{
     int  y  =  NIL;
     int  x  =  root;
     while  (x  !=  NIL)
     {
        y  =  x;
         if  (key[z]  <  key[x])
            x  =  left[x];
         else
            x  =  right[x];
    }
    p[z]  =  y;
     if  (y  ==  NIL)
        root  =  z;
     else
     {
         if  (key[z]  <  key[y])
            left[y]  =  z;
         else
            right[y]  =  z;
    }
    left[z]  =  NIL;
    right[z]  =  NIL;
    color[z]  =  R;
    InsertFixup(z);
}

void  RBTree::InsertFixup( int  z)
{
     int  y;
     while  (color[p[z]]  ==  R)
     {
         if  (p[z]  ==  left[p[p[z]]])
         {
            y  =  right[p[p[z]]];
             if  (color[y]  ==  R)
             {
                color[p[z]]  =  B;
                color[y]  =  B;
                color[p[p[z]]]  =  R;
                z  =  p[p[z]];
            }
             else
             {
                 if  (z  ==  right[p[z]])
                 {
                    z  =  p[z];
                    LeftRotate(z);
                }
                color[p[z]]  =  B;
                color[p[p[z]]]  =  R;
                RightRotate(p[p[z]]);
            }
        }
         else
         {
            y  =  left[p[p[z]]];
             if  (color[y]  ==  R)
             {
                color[p[z]]  =  B;
                color[y]  =  B;
                color[p[p[z]]]  =  R;
                z  =  p[p[z]];
            }
             else
             {
                 if  (z  ==  left[p[z]])
                 {
                    z  =  p[z];
                    RightRotate(z);
                }
                color[p[z]]  =  B;
                color[p[p[z]]]  =  R;
                LeftRotate(p[p[z]]);
            }
        }
    }
    color[root]  =  B;
}

void  RBTree::DeleteByPointer( int  z)
{
     int  x, y;
     if  (left[z]  ==  NIL  ||  right[z]  ==  NIL)
        y  =  z;
     else
        y  =  successor(z);
     if  (left[y]  !=  NIL)
        x  =  left[y];
     else
        x  =  right[y];
    p[x]  =  p[y];
     if  (p[y]  ==  NIL)
        root  =  x;
     else
     {
         if  (y  ==  left[p[y]])
            left[p[y]]  =  x;
         else
            right[p[y]]  =  x;
    }
     if  (y  !=  z)
        key[z]  =  key[y];
     if  (color[y]  ==  B)
        DeleteFixup(x);
}

void  RBTree::DeleteFixup( int  x)
{
     int  y, w;
     while  (x  !=  root  &&  color[x]  ==  B)
     {
         if  (x  ==  left[p[x]])
         {
            w  =  right[p[x]];
             if  (color[w]  =  R)
             {
                color[w]  =  B;
                color[p[x]]  =  R;
                LeftRotate(p[x]);
                w  =  right[p[x]];
            }
             if  (color[left[w]]  ==  B  &&  color[right[w]]  ==  B)
             {
                color[w]  =  R;
                x  =  p[x];
            }
             else
             {
                 if  (color[right[w]]  ==  B)
                 {
                    color[left[w]]  =  B;
                    color[w]  =  R;
                    RightRotate(w);
                    w  =  right[p[x]];
                }
                color[w]  =  color[p[x]];
                color[p[x]]  =  B;
                color[right[w]]  =  B;
                LeftRotate(p[x]);
                x  =  root;
            }
        }
         else
         {
            w  =  left[p[x]];
             if  (color[w]  =  R)
             {
                color[w]  =  B;
                color[p[x]]  =  R;
                RightRotate(p[x]);
                w  =  left[p[x]];
            }
             if  (color[right[w]]  ==  B  &&  color[left[w]]  ==  B)
             {
                color[w]  =  R;
                x  =  p[x];
            }
             else
             {
                 if  (color[left[w]]  ==  B)
                 {
                    color[right[w]]  =  B;
                    color[w]  =  R;
                    LeftRotate(w);
                    w  =  left[p[x]];
                }
                color[w]  =  color[p[x]];
                color[p[x]]  =  B;
                color[left[w]]  =  B;
                RightRotate(p[x]);
                x  =  root;
            }
        }
    }
    color[x]  =  B;
}
void  RBTree::Travel( int  x)
{
     if  (x  !=  NIL)
     {
        cout  <<   ' ( ' ;
        Travel(left[x]);
        cout  <<   '   '   <<  key[x]  <<   '   ' ;
        Travel(right[x]);
        cout  <<   ' ) ' ;
    }
}

int  main()
{
    RBTree T;

     for  ( int  i = 1 ; i <= 10 ; i ++ )
        T.Insert(i * 10 );
     for  ( int  i = 1 ; i <= 10 ; i ++ )
     {
        T.Delete(i * 10 );
        T.Travel(T.Root());
        cout  <<  endl;
    }
     return   0 ;
}