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;
rbtree_left_roate(root,z->parent);
break;
}
}
}else{
//case1
if(z->parent->left->color == RB_RED){
z->parent->color = RB_RED;
z->parent->left->color = RB_BLACK;
rbtree_right_roate(root,z->parent);
}else{
//case2
if(z->parent->left->left->color == RB_BLACK && z->parent->left->right->color == RB_BLACK){
z->parent->left->color = RB_RED;
z = z->parent;
}else{
//case3
if(z->parent->left->right->color == RB_RED){
z->parent->left->right->color = RB_BLACK;
|