赤黒ツリーソース実装
12845 ワード
前回の『思考赤黒樹』に続いて、自分で赤い黒い木を自動的に実現し、理論が実際のコードに変換することに成功したのか、それとも少し難しいのか、困難点は主にいくつかの境界点の確定にある.2時間かかってやっとすべてのものを融通して、やはり更に自分のCの功力を高める必要があります.
直接コードを貼ってください.必要なものがあれば持って行ってください.私自身も残してから遊びに来ます.
このコードは実际の环境に合わせて修正する必要があるに违いありません.先日、『Linuxカーネルの赤と黒の木』のコードをスキャンしましたが、自分が书いたコードのレベルと大神が书いたのとは少し差があることに気づきました.頑張りましょう.
//rb_tree.h
rb_tree.c
//テストコードt.c
直接コードを貼ってください.必要なものがあれば持って行ってください.私自身も残してから遊びに来ます.
このコードは実际の环境に合わせて修正する必要があるに违いありません.先日、『Linuxカーネルの赤と黒の木』のコードをスキャンしましたが、自分が书いたコードのレベルと大神が书いたのとは少し差があることに気づきました.頑張りましょう.
//rb_tree.h
#include <stdio.h>
#include <stdlib.h>
#ifndef RB_TREE
#define RB_TREE
typedef struct{int value;}rbtree_key;
typedef struct{int value;}rbtree_data;
typedef enum rbtree_color{RB_RED,RB_BLACK}rbtree_color;
int rbtree_key_cmp(rbtree_key x,rbtree_key y);
typedef struct rbtree_node rbtree_node;
//rb tree node
struct rbtree_node{
rbtree_key key;
rbtree_color color;
rbtree_data data;
rbtree_node *parent;
rbtree_node *left;
rbtree_node *right;
};
rbtree_node * rb_nil;
static int rb_nil_inited;
void rbtree_init_nil();
void rbtree_destroy_nil();
void rbtree_node_cpy(rbtree_node *source,rbtree_node *dest);
rbtree_node * rbtree_search(rbtree_node * t,rbtree_key key);
rbtree_node * rbtree_search_iterative(rbtree_node * t,rbtree_key key);
rbtree_node * rbtree_min(rbtree_node *t);
rbtree_node * rbtree_max(rbtree_node *t);
rbtree_node * rbtree_successor(rbtree_node *t);
rbtree_node * rbtree_predecessor(rbtree_node *t);
void rbtree_insert(rbtree_node **root,rbtree_node *z);
void rbtree_insert_fixup(rbtree_node **root,rbtree_node *z);
void rbtree_delete(rbtree_node **root,rbtree_node *z);
void rbtree_delete_fixup(rbtree_node **root,rbtree_node *z);
void rbtree_left_roate(rbtree_node **root,rbtree_node *z);
void rbtree_right_roate(rbtree_node **root,rbtree_node *z);
#endif
rb_tree.c
#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 != 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;
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
#include <stdio.h>
#include <stdlib.h>
#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("=================
");
}
p = rbtree_min(t);
printf("%d:%p p:%p,l:%p,r:%p
",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
",p->key.value,p,p->parent,p->left,p->right);
}
printf("
");
min = rbtree_min(t);
printf("t:%p,min:%p
",t,min);
do{
printf("--------------
");
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("
");
rbtree_delete(&t,max);
}while(t!=rb_nil);
printf("
t:%p
",t);
rbtree_destroy(t);
rbtree_destroy_nil();
return 0;
}
rbtree_node * rbtree_create(int num){
rbtree_node *p;
p = (rbtree_node *)malloc(sizeof(rbtree_node));
p->key.value = num;
p->data.value = 0;
p->color = RB_RED;
p->left = rb_nil;
p->right = rb_nil;
p->parent = rb_nil;
return p;
}
rbtree_node * rbtree_add(rbtree_node **root,int num){
rbtree_node *p;
p = rbtree_create(num);
rbtree_insert(root,p);
}
rbtree_node * rbtree_find(rbtree_node *t,int num){
rbtree_key key;
key.value = num;
return rbtree_search(t,key);
}
void rbtree_destroy(rbtree_node *t){
if(rb_nil == t) return;
rbtree_node *p;
p = t;
free(t);
if(p->left) rbtree_destroy(p->left);
if(p->right) rbtree_destroy(p->right);
}
void rbtree_print(rbtree_node * t){
if(rb_nil == t) return;
printf(" %d-%d
",t->key.value,t->color);
printf(" ↙");
printf(" ↘
");
if(t->left != rb_nil){
printf(" %d-%d",t->left->key.value,t->left->color);
}else{
printf(" nil-%d",t->left->color);
}
if(t->right != rb_nil){
printf(" %d-%d",t->right->key.value,t->right->color);
}else{
printf(" nil-%d",t->right->color);
}
printf("
");
rbtree_print(t->left);
rbtree_print(t->right);
}