!= 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){
z = z->parent;
rbtree_right_roate(root,z);
}
//case3
z->parent->color = RB_BLACK;
z->parent->parent->color = RB_RED;
rbtree_left_roate(root,z->parent->parent);
}
}
}
(*root)->color = RB_BLACK;
}
void rbtree_delete(rbtree_node **root,rbtree_node *z){
rbtree_node *parent;
rbtree_node *inherit;
rbtree_node *delete;
//find which node to delete
if(z->left != rb_nil && z->right != rb_nil){
delete = rbtree_successor(z);
rbtree_node_cpy(delete,z);
}else{
delete = z;
}
//find the inherit node of the delete node
if(delete->left != rb_nil){
inherit = delete->left;
}else{
inherit = delete->right;
}
//connect inherit to delete node's parent
parent = delete->parent;
inherit->parent = parent;
//connect delete node's parent to inherit
if(parent == rb_nil){
*root = inherit;
}else{
if(delete == parent->left){
parent->left = inherit;
}else{
parent->right = inherit;
}
}
if(delete->color = RB_BLACK){
rbtree_delete_fixup(root,inherit);
}
free(delete);
return;
}
void rbtree_delete_fixup(rbtree_node **root,rbtree_node *z){
while(z != *root && z->color == RB_BLACK){
if(z == z->parent->left){
//case1
if(z->parent->right->color == RB_RED){
z->parent->color = RB_RED;
z->parent->right->color = RB_BLACK;
rbtree_left_roate(root,z->parent);
}else{
//case2
if(z->parent->right->left->color == RB_BLACK && z->parent->right->right->color == RB_BLACK){
z->parent->right->color = RB_RED;
z = z->parent;
}else{
//case3
if(z->parent->right->left->color == RB_RED){
z->parent->right->left->color = RB_BLACK;
z->parent->right->color = RB_RED;
rbtree_right_roate(root,z->parent->right);
}
//case4
z->parent->right->color = z->parent->color;
z->parent->right->right->color = RB_BLACK;
z->parent->color = RB_BLACK;
|