红黑树的完整C语言实现

#include "rbtree.h" #include <stdlib.h> #include <stdio.h> #include <time.h> #include <assert.h> //=========================================================== // initialize a rbtree //=========================================================== void rbtree_init(rbtree_t *rbtree) { rbtree->nil=(rbtreenode_t *)malloc(sizeof(rbtreenode_t)); rbtree->nil->value=0; rbtree->nil->color=BLACK; rbtree->nil->left=NULL; rbtree->nil->right=NULL; rbtree->nil->parent=NULL; rbtree->root=rbtree->nil; } //=========================================================== // rb_search_node // return a rbtreenode_t pointer base on the value //=========================================================== rbtreenode_t *rb_search_node(rbtree_t *rbtree,int value) { rbtreenode_t *x=NULL; x=rbtree->root; while(x!=rbtree->nil) { if(value>x->value) x=x->right; else if(value<x->value) x=x->left; else if(value==x->value) return x; } x=NULL; return x; } //============================================================= // left_rotate // make sure x->right!=NULL //============================================================= void left_rotate(rbtree_t *rbtree,rbtreenode_t *x) { rbtreenode_t *y; y=x->right; x->right=y->left; if(y->left!=rbtree->nil) y->left->parent=x; if(x!=rbtree->nil) y->parent=x->parent; if(x->parent==rbtree->nil) rbtree->root=y; else { if(x->parent->left==x) x->parent->left=y; else x->parent->right=y; } y->left=x; if(x!=rbtree->nil) x->parent=y; } //========================================================== // right_rotate // just same as left_rotate //========================================================== void right_rotate(rbtree_t *rbtree,rbtreenode_t *x) { rbtreenode_t *y; y=x->left; x->left=y->right; if(y->right!=rbtree->nil) y->right->parent=x; if(x!=rbtree->nil) y->parent=x->parent; if(x->parent==rbtree->nil) rbtree->root=y; else { if(x->parent->left==x) x->parent->left=y; else x->parent->right=y; } y->right=x; if(x!=rbtree->nil) x->parent=y; } //================================================================ // rb_insert_fixup // z is the new child //================================================================ void rb_insert_fixup(rbtree_t *rbtree,rbtreenode_t *z) { rbtreenode_t *y; while((z->parent!=NULL)&&(z->parent->color==RED)) { if(z->parent==z->parent->parent->left) { y=z->parent->parent->right; if((y!=NULL)&&(y->color==RED)) { z->parent->color=BLACK; y->color=BLACK; z->parent->parent->color=RED; z=z->parent->parent; } else { if(z==z->parent->right) { z=z->parent; left_rotate(rbtree,z); } z->parent->color=BLACK; z->parent->parent->color=RED; right_rotate(rbtree,z->parent->parent); } } else { y=z->parent->parent->left; if((y!=NULL)&&(y->color==RED)) { z->parent->color=BLACK; y->color=BLACK; z->parent->parent->color=RED; z=z->parent->parent; } else { if(z==z->parent->left) { z=z->parent; right_rotate(rbtree,z); } z->parent->color=BLACK; z->parent->parent->color=RED; left_rotate(rbtree,z->parent->parent); } } } rbtree->root->color=BLACK; rbtree->nil->color=BLACK; } //============================================================ // rbtree_insert //============================================================ void rbtree_insert(rbtree_t *rbtree,int value) { rbtreenode_t *x,*y,*z; x=rbtree->root; y=rbtree->nil; z=(rbtreenode_t *)malloc(sizeof(rbtreenode_t)); assert(z); z->color=RED; z->value=value; z->parent=NULL; z->left=NULL; z->right=NULL; while(x!=rbtree->nil) { y=x; if(z->value<x->value) x=x->left; else if(z->value>x->value) x=x->right; else if(z->value==x->value) { free(z); return; } } z->parent=y; if(y!=rbtree->nil) { if(z->value>y->value) y->right=z; else if(z->value<y->value) y->left=z; } else { rbtree->root = z; } z->left=rbtree->nil; z->right=rbtree->nil; rb_insert_fixup(rbtree,z); } //======================================================================== // rb_delete_fixup // fixup the rbtree when free a blacknode //======================================================================== void rb_delete_fixup(rbtree_t *rbtree,rbtreenode_t *x) { rbtreenode_t *w; while((x!=rbtree->root)&&(x->color==BLACK)) { if(x==x->parent->left) { w=x->parent->right; if(w->color==RED) { w->color=BLACK; x->parent->color=RED; left_rotate(rbtree,x->parent); w=x->parent->right; } if(w->left->color==BLACK&&w->right->color==BLACK) { w->color=RED; x=x->parent; } else { if(w->right->color==BLACK) { w->left->color=BLACK; w->color=RED; right_rotate(rbtree,w); w=x->parent->right; } w->color=w->parent->color; x->parent->color=BLACK; w->right->color=BLACK; left_rotate(rbtree,x->parent); x=rbtree->root; } } else { w=x->parent->left; if(w->color==RED) { w->color=BLACK; x->parent->color=RED; right_rotate(rbtree,x->parent); w=x->parent->left; } if(w->right->color==BLACK&&w->left->color==BLACK) { w->color=RED; x=x->parent; } else { if(w->left->color==BLACK) { w->right->color=BLACK; w->color=RED; left_rotate(rbtree,w); w=x->parent->left; } w->color=w->parent->color; x->parent->color=BLACK; w->left->color=BLACK; right_rotate(rbtree,x->parent); x=rbtree->root; } } } x->color=BLACK; } //======================================================================= // rb_delete // delete z from rbtree //======================================================================= void rb_delete(rbtree_t *rbtree,rbtreenode_t *z) { rbtreenode_t *y,*x; if(z->left==rbtree->nil||z->right==rbtree->nil) y=z; else { y=z->right; while(y->left!=rbtree->nil) y=y->left; } if(y->left!=rbtree->nil) x=y->left; else x=y->right; x->parent=y->parent; if(y->parent==rbtree->nil) rbtree->root=x; else { if(y->parent->left==y) y->parent->left=x; else y->parent->right=x; } if(y!=z) z->value=y->value; if(y->color==BLACK) rb_delete_fixup(rbtree,x); free(y); } //================================================================= // rb_inorder //================================================================= static int level = 0; int rb_inorder(rbtreenode_t *rbtnode,rbtreenode_t *nil) { int i,l = 0,r = 0,h = 0; if(!level) printf("\n 输出信息："); printf("\n"); for(i = 0;i < level;i++) printf("\t"); if(rbtnode==nil) { printf("NIL,"); return 0; } else { printf("(%d %c",rbtnode->value,(rbtnode->color==RED)?'R':'B'); level++; if(rbtnode->color==RED&&rbtnode->parent->color==RED) { printf("error RED duped<%d, %d>",rbtnode->value,rbtnode->parent->value); exit(0); } l=rb_inorder(rbtnode->left,nil); r=rb_inorder(rbtnode->right,nil); level--; for(i=0;i<level;i++) printf("\t"); printf(")\n"); } h=(rbtnode->color==RED)?0:1; h+=(l > r)?l:r; if(level) ; else { printf("\n 黑高度为：%d\n",h); } return h; } void swap(int *pm,int *pn) //必须用指针进行交换 { int temp; temp=*pm; *pm=*pn; *pn=temp; }