#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;? // 默認(rèn)空樹(shù)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 ;
}