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;
}
#include "rb_tree.h"
int rbtree_key_cmp(rbtree_key x,rbtree_key y){
return y.value-x.value;
}
void rbtree_node_cpy(rbtree_node *source,rbtree_node *dest){
dest->key.value = source->key.value;
dest->data.value = source->data.value;
}
void rbtree_init_nil(){
if(!rb_nil_inited){
rb_nil = (rbtree_node *)malloc(sizeof(rbtree_node));
rb_nil->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