几乎被这玩意弄成脑死亡。

注意：最好把class T换成typename T，自己实现特化Compare时需要单加一个.h，我对模板一知半解，如果特化Compare放在T类型定义的.h里，编译就出错，error redifinition

 

enum
{
 RB_Red,
 RB_Black,
};

template <class T>
class RBTreeNode
{
public:
 RBTreeNode* _link[2];
 T* _data;
 RBTreeNode* _parent;
 unsigned char _color;
};

template <typename T>
int Compare(T* t1, T* t2)
{
 return t1 == t2 ? 0 : (t1 < t2 ? -1 : 1);
};

template <class T>
class RBTree
{
public:
 RBTreeNode<T>* search(T* it);
 RBTreeNode<T>* insert(T* it);
 RBTreeNode<T>* probe(T* item);
 T* remove(T* item);
 RBTreeNode<T>* rebalance(RBTreeNode<T>* n);
private:
 RBTreeNode<T>* _root;
 int _count;
 int _gen;
};

template<class T> inline RBTreeNode<T> *RBTree<T>::search(T* it)
{
 int d = 0;
 RBTreeNode<T> *p = NULL, *n = NULL, *q = NULL;

 // search
 for (q = NULL, p = _root; p != NULL; q = p, p = p->_link[d])
 {
  int cmp = Compare<T>(it, p->_data);
  if(cmp == 0)
   return p;
  d = cmp > 0;
 }

 return NULL;
}

template<class T> inline RBTreeNode<T> *RBTree<T>::probe(T* it)
{
 int d = 0;
 RBTreeNode<T> *p = NULL, *n = NULL, *q = NULL;

 // search
 for (q = NULL, p = _root; p != NULL; q = p, p = p->_link[d])
 {
  int cmp = Compare<T>(it, p->_data);
  if(cmp == 0)
   return p;
  d = cmp > 0;
 }
 // insert
 n = new RBTreeNode<T>;
 if(!n)
  return NULL;

 _count++;
 n->_link[0] = n->_link[1] = NULL;
 n->_parent = q;
 n->_data = it;

 if(q != NULL)
 {
  q->_link[d] = n;
 }
 else
  _root = n;

 n->_color = RB_Red;

 // rebalance
 q = n;
 while(true)
 {
  RBTreeNode<T> *f, *g;
  if(!q->_parent)
   break;

  f = q->_parent;
  if(!f->_parent)
   break;

  g = f->_parent;

  if(g->_link[0] == f)
  {
   // rebalance left
   RBTreeNode<T>* h = g->_link[1];
   if(h != NULL && h->_color == RB_Red)
   {
    // q has a red uncle 
    h->_color = f->_color = RB_Black;
    g->_color = RB_Red;
    q = g;
   }
   else
   {
    RBTreeNode<T>* i = g->_parent;
    if(i == NULL)
     i = _root;
    if(f->_link[1] == q)
    {
     // q is right son of f
     // exchange q & f, let f become q's left son, then 
     f->_link[1] = q->_link[0];
     q->_link[0] = f;
     g->_link[0] = q;
     f->_parent = q;
     if(f->_link[1] != NULL)
      f->_link[1]->_parent = f;
     f = q;
    }

    // q is left son of f 
    // rotate right at g
    g->_color = RB_Red;
    f->_color = RB_Black;

    g->_link[0] = f->_link[1];
    f->_link[1] = g;
    i->_link[i->_link[1] == g] = f;

    f->_parent = g->_parent;
    g->_parent = f;
    if(g->_link[0] != NULL)
     g->_link[0]->_parent = g;

    break;
   }
  }
  else
  {
   // right 
   RBTreeNode<T>* h = g->_link[0];
   if(h != NULL && h->_color = RB_Red)
   {
    // case 1
    f->_color = h->_color = RB_Black;
    g->_color = RB_Red;
    q = g;
   }
   else
   {
    RBTreeNode<T>* i = g->_parent;
    if(i == NULL)
     i = _root;

    if(f->_link[0] == q)
    {
     // case 3, transform to case 2
     f->_link[0] = q->_link[1];
     q->_link[1] = f;
     g->_link[1] = q;
     f->_parent = q;
     if(f->_link[0] != NULL)
      f->_link[0]->_parent = f;
     f = q;
    }

    // case 2
    g->_color = RB_Red;
    f->_color = RB_Black;

    g->_link[1] = f->_link[0];
    f->_link[0] = g;
    i->_link[i->_link[0] == g] = f;

    f->_parent = g->_parent;
    g->_parent = f;
    if(g->_link[1] != NULL)
     g->_link[1]->_parent = g;

    break;
   }
  }
 }

 _root->_color = RB_Black;

 return n;
}

// Holy~ brain killer ...

template<class T> inline T *RBTree<T>::remove(T *item)
{
 RBTreeNode<T> *p, *q, *f;
 T* it = NULL;
 int d;

 // find target
 if(!_root)
  return NULL;

 for (q = NULL, p = _root; p != NULL; q = p, p = p->_link[d])
 {
  int cmp = Compare<T>(it, p->_data);
  if(cmp == 0)
   break;
  d = cmp > 0;
 }

 if(!p)
  return NULL;

 it = p->_data;
 q = p->_parent;
 if(q == NULL)
 {
  q = (RBTreeNode<T>*)&_root; // c pointer trick: q->_link[0] = root, _link[1] is _count
  d = 0;
 }

 // delete target
 if(p->_link[1] == NULL)
 {
  // no right son.
  q->_link[d] = p->_link[0];
  if(q->_link[d] != NULL)
   q->_link[d]->_parent = p->_parent;
  f = q;
 }
 else
 {
  unsigned char c;
  RBTreeNode<T>* r = p->_link[1];

  if(r->_link[0] == NULL)
  {
   // right son doesn't have a left son 
   r->_link[0] = p->_link[0];
   q->_link[d] = r;
   r->_parent = p->_parent;
   if(r->_link[0] != NULL)
    r->_link[0]->_parent = r;
   c = p->_color;
   p->_color = r->_color;
   r->_color = c;

   f = r;
   d = 1;
  }
  else
  {
   // right son has a left son ...
   RBTreeNode<T>* s = r->_link[0];
   while(s->_link[0] != NULL)
   {
    s = s->_link[0]; // find the successor
   }
   r = s->_parent;
   r->_link[0] = s->_link[1];
   s->_link[0] = p->_link[0];
   s->_link[1] = p->_link[1];
   q->_link[d] = s;
   if(s->_link[0] != NULL)
   {
    s->_link[0]->_parent = s;
   }
   s->_link[1]->_parent = s;
   s->_parent = p->_parent;

   if(r->_link[0] != NULL)
    r->_link[0]->_parent = r;

   c = p->_color;
   p->_color = s->_color;
   s->_color = c;

   f = r;
   d = 0;
  }
 }

 // rebalance
 if(p->_color = RB_Black)
 {
  while(true)
  {
   RBTreeNode<T> *x, *g, *y;

   x = f->_link[d];
   if(x != NULL && x->_color == RB_Red)
   {
    x->_color = RB_Black;
    break;
   }

   if(f == (RBTreeNode<T>*) &_root)
    break;

   g = f->_parent;
   if(g == NULL)
    g = (RBTreeNode<T>*) &_root;

   if(d == 0)
   {
    // left side rebalance
    RBTreeNode<T>* w = f->_link[1];
    if(w->_color == RB_Red)
    {
     // w is black

     w->_color = RB_Black;
     f->_color = RB_Red;

     f->_link[1] = w->_link[0];
     w->_link[0] = f;
     g->_link[g->_link[0] != f] = w;

     w->_parent = f->_parent;
     f->_parent = w;

     g = w;
     w->_parent = f;
    }
    if( (w->_link[0] == NULL || w->_link[0]->_color == RB_Black)
      && (w->_link[1] == NULL || w->_link[1]->_color == RB_Black))
    {
     // left side rebalance
     w->_color = RB_Red;
    }
    else
    {
     if(w->_link[1] == NULL
       || w->_link[1]->_color == RB_Black)
     {
      // transform left-side rebalancing
      RBTreeNode<T>* y = w->_link[0];
      y->_color = RB_Black;
      w->_color = RB_Red;
      w->_link[0] = y->_link[1];
      y->_link[1] = w;

      if(w->_link[0] != NULL)
       w->_link[0]->_parent = w;
      w = f->_link[1] = y;
      w->_link[1]->_parent = w;
     }

     w->_color = f->_color;
     f->_color = RB_Black;
     w->_link[1]->_color = RB_Black;

     f->_link[1] = w->_link[0];
     w->_link[0] = f;
     g->_link[g->_link[0] != f] = w;

     w->_parent = f->_parent;
     f->_parent = w;
     if(f->_link[1] != NULL)
      f->_link[1]->_parent = f;
     break;
    }
   }
   else
   {
    // right side rebalance
    RBTreeNode<T>* w = f->_link[0];
    if(w->_color == RB_Red)
    {
     w->_color = RB_Black;
     f->_color = RB_Red;

     f->_link[0] = w->_link[1];
     w->_link[1] = f;
     g->_link[g->_link[0] != f] = w;

     w->_parent = f->_parent;
     f->_parent = w;

     g = w;
     w = f->_link[0];

     w->_parent = f;
    }

    if( (w->_link[0] == NULL || w->_link[0]->_color = RB_Black)
      && (w->_link[1] == NULL || w->_link[1]->_color == RB_Black))
    {
     w->_color = RB_Red;
    }
    else
    {
     if(w->_link[0] == NULL || w->_link[0]->_color = RB_Black )
     {
      RBTreeNode<T>* y = w->_link[1];
      y->_color = RB_Black;
      w->_color = RB_Red;
      w->_link[1] = y->_link[0];
      y->_link[0] = w;
      if(w->_link[1] != NULL)
       w->_link[1]->_parent = w;
      w = f->_link[0] = y;
      w->_link[0]->_parent = w;
     }

     w->_color = f->_color;
     f->_color = RB_Black;
     w->_link[0]->_color = RB_Black;

     f->_link[0] = w->_link[1];
     w->_link[1] = f;
     g->_link[g->_link[0] != f] = w;

     w->_parent = f->_parent;
     f->_parent = w;
     if(f->_link[0] != NULL)
      f->_link[0]->_parent = f;
     break;
    }
   }

   y = f;
   f = f->_parent;
   if(f == NULL)
    f = (RBTreeNode<T>*) &_root;
   d = f->_link[0] != y;
  }
 }

 //

 return p ? p->_data : NULL;
}