#include <stdio.h>  #define RED 1  #define BLACK 2    class Node  {  public:   static Node* Nil;   Node* left;   Node* right;   Node* p;   int data;   int color;   Node(int da,int col=RED):data(da),color(col)   {    this->left=Nil;    this->right=Nil;    this->p=Nil;   }   Node():color(BLACK),data(0)   {}  };  class Tree  {  public:   Node* root;   Tree():root(0)   {}  };  void rotate_left(Node* n)  {   auto temp=n->right->left;   n->right->left=n;   n->right->p=n->p;   if(n==n->p->left) n->p->left=n->right;   else n->p->right=n->right;   n->p=n->right;   n->right=temp;  }  void rotate_right(Node* n)  {   auto temp=n->left->right;   n->left->right=n;   if(n==n->p->left) n->p->left=n->left;   else n->p->right=n->left;   n->left->p=n->p;   n->p=n->right;   n->left=temp;  }  void fixup(Tree* tree,Node* node)  {   while(node->p->color==RED)   {    auto g=node->p->p;    if(node->p==g->left)    {     auto u=g->right;     if(u->color==RED)     {      u->color=BLACK;      node->p->color=BLACK;      g->color=RED;      node=g;     }else     {      if(node==node->p->right)       rotate_left(node->p);      g->color=RED;      node->p->color=BLACK;      rotate_right(g);     }    }else    {     auto u=g->left;     if(u->color==RED)     {      u->color=BLACK;      node->p->color=BLACK;      g->color=RED;      node=g;     }else     {      if(node==node->p->left)       rotate_right(node->p);      g->color=RED;      node->p->color=BLACK;      rotate_left(g);     }    }   }   while(tree->root->p!=Node::Nil) tree->root=tree->root->p;   tree->root->color=BLACK;  }  void insert(Tree* tree,Node* root,Node* node)  {   if(tree->root==NULL) tree->root=node;   else   {    if(root->data < node->data)    {     if(root->right!=Node::Nil) insert(tree,root->right,node);     else     {      root->right=node;      node->p=root;     }    }else    {     if(root->left!=Node::Nil)  insert(tree,root->left,node);     else     {      root->left=node;      node->p=root;     }    }   }   fixup(tree,node);  }    void print_tree(Node* node)  {   if(node==Node::Nil) return;   putchar('(');   print_tree(node->left);   putchar(')');   printf("%d",node->data);   putchar('(');   print_tree(node->right);   putchar(')');  }  Node* Node::Nil=new Node();  int main()  {   Node::Nil->left=Node::Nil;   Node::Nil->right=Node::Nil;   Node::Nil->p=Node::Nil;   Tree* tree=new Tree();   int array[]={1,2,3,4,5,6,7,8};   for(int i=0;i<sizeof(array)/sizeof(int);++i) insert(tree,tree->root,new Node(array[i],RED));    print_tree(tree->root);   return 0;    }                                      相信大家最难理解的部分就是fixup的三种case，就是为什么在这里左旋，又为什么在这里右旋，这里推荐大家看一下introduction algorithms里对RB-TREE的描述。花了3页详细介绍了RB-TREE的每个步骤。

来自： http://my.oschina.net/000quanwei/blog/593862