il->color = RB_BLACK;
rb_nil->parent = rb_nil;
rb_nil->left = rb_nil;
rb_nil->right = rb_nil;
rb_nil_inited = 1;
}
}
void rbtree_destroy_nil(){
if(rb_nil_inited){
free(rb_nil);
rb_nil=NULL;
rb_nil_inited = 0;
}
}
rbtree_node * rbtree_search(rbtree_node * t,rbtree_key key){
int cmp = rbtree_key_cmp(t->key,key);
if(rb_nil == t || 0 == cmp )
return t;
return cmp<0 rbtree_search(t->left,key):rbtree_search(t->right,key);
}
rbtree_node * rbtree_search_iterative(rbtree_node * t,rbtree_key key){
int cmp = rbtree_key_cmp(t->key,key);
while(rb_nil != t && 0!=cmp){
t = cmp<0 t->left:t->right;
}
return t;
}
rbtree_node * rbtree_min(rbtree_node *t){
while(rb_nil != t->left){
t = t->left;
}
return t;
}
rbtree_node * rbtree_max(rbtree_node *t){
while(rb_nil != t->right){
t = t->right;
}
return t;
}
rbtree_node * rbtree_successor(rbtree_node *t){
rbtree_node * parent;
if(rb_nil != t->right){
return rbtree_min(t->right);
}
parent = t->parent;
while(parent != rb_nil && t == parent->right){
t = parent;
parent = parent->parent;
}
return parent;
}
rbtree_node * rbtree_predecessor(rbtree_node *t){
rbtree_node * parent;
if(rb_nil != t->left){
return rbtree_max(t->left);
}
parent = t->parent;
while(rb_nil != parent && t == parent->left ){
t = parent;
parent = parent->parent;
}
return parent;
}
void rbtree_insert(rbtree_node **root,rbtree_node *z){
int cmp;
rbtree_node *p,*t;
if(rb_nil == *root){
*root = z;
return;
}
t = *root;
while( rb_nil != t){
p = t;
cmp = rbtree_key_cmp(t->key,z->key);
t = cmp<0 t->left:t->right;
}
if(cmp<0){
p->left = z;
}else{
p->right = z;
}
z->parent = p;
z->color = RB_RED;
if(z->parent->color == RB_RED){
rbtree_insert_fixup(root,z);
}
}
void rbtree_insert_fixup(rbtree_node **root,rbtree_node *z){
while(z->parent->color == RB_RED){
if(z->parent == z->parent->parent->left){
//case 1
if(z->parent->parent->right->color == RB_RED){
z->parent->parent->color = RB_RED;
z->parent->parent->left->color = RB_BLACK;
z->parent->parent->right->color = RB_BLACK;
z = z->parent->parent;
}else{
//case2
if(z == z->parent->right){
z = z->parent;
rbtree_left_roate(root,z);
}
//case3
z->parent->color = RB_BLACK;
z->parent->parent->color = RB_RED;
rbtree_right_roate(root,z->parent->parent);
}
}else{
//case 1
if(z->parent->parent->left->color == RB_RED){
z->parent->parent->color = RB_RED;
z->parent->parent->left->color = RB_BLACK;
z->parent->parent->right->color = RB_BLACK;
z = z->parent->parent;
}else{
//case2
if(z == z->parent->left){ |