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;
z->parent->left->color = RB_RED;
rbtree_left_roate(root,z->parent->left);
}
//case4
z->parent->left->color = z->parent->color;
z->parent->left->left->color = RB_BLACK;
z->parent->color = RB_BLACK;
rbtree_right_roate(root,z->parent);
break;
}
}
}
}
z->color = RB_BLACK;
}
//assume that z's right child is not rb_nil
void rbtree_left_roate(rbtree_node **root,rbtree_node *z){
rbtree_node *right_child;
right_child = z->right;
//1.
z->right = right_child->left;
if(right_child->left != rb_nil){
right_child->left->parent = z;
}
//2.
right_child->left = z;
right_child->parent = z->parent;
if(right_child->parent == rb_nil){
*root = right_child;
//3.
}else if(z == z->parent->left){
z->parent->left = right_child;
}else{
z->parent->right = right_child;
}
z->parent = right_child;
}
//assume that z's left child is not rb_nil
void rbtree_right_roate(rbtree_node **root,rbtree_node *z){
rbtree_node *left_child;
left_child = z->left;
//1.
z->left = left_child->right;
if(left_child->right != rb_nil){
left_child->right->parent = z;
}
//2.
left_child->right = z;
left_child->parent = z->parent;
if(left_child->parent == rb_nil){
*root = left_child;
//3.
}else if(z == z->parent->left){
z->parent->left = left_child;
}else{
z->parent->right = left_child;
}
z->parent = left_child;
}
//测试代码 t.c
[cpp]
#include
#include
#include "lib/rb_tree.h"
rbtree_node * rbtree_create(int num);
rbtree_node * rbtree_add(rbtree_node **root,int num);
void rbtree_destroy(rbtree_node *t);
void rbtree_print(rbtree_node * t);
rbtree_node * rbtree_find(rbtree_node *t,int num);
int main(int argc,char *argv[]){
rbtree_node *t,*p,*max,*min;
int arr[] = {9,8,11,18,2,5,16,1,8};
int i;
rbtree_init_nil();
t = rbtree_create(10);
t->color = RB_BLACK;
for(i=0;i<9;i++){
rbtree_add(&t,arr[i]);
rbtree_print(t);
printf("=================\n");
}
p = rbtree_min(t);
printf("%d:%p p:%p,l:%p,r:%p\n",p->key.value,p,p->parent,p->left,p->right);
while((p=rbtree_successor(p)) != rb_nil){
printf("%d:%p p:%p,l:%p,r:%p\n",p->key.value,p,p->parent,p->left,p->right);
}
printf("\n");
min = rbtree_min(t);
printf("t:%p,min:%p\n",t,min);
do{
printf("--------------\n");
rbtree_print(t);
max = rbtree_max(t);
printf("%d ",max->key.value);
p = max;
while((p=rbtree_predecessor(p))!=rb_nil){
printf("%d ",p->key.value);
}
printf("\n");
rbtree_delete(&t,max);
}while(t!=rb_nil);
printf("\nt:%p\n",t);
rbtree_destroy(t);
rbtree_destroy_nil();
return 0;
}
rbt