#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的每个步骤。
