红黑树、二叉搜索树的实现和性能比较

#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include "rbTree.h" /*初始化红黑树 输入为空 返回值的类型为RBTree */ RBTree *Init_RBTree() { RBTree *T; T=(RBTree *)malloc(sizeof(RBTree));//动态分配空间 T->nil=(RBNode *)malloc(sizeof(RBNode)); T->nil->color=Black; T->nil->key=0; T->nil->left=NULL; T->nil->right=NULL; T->nil->parent=NULL; T->root=T->nil; return T; } /*初始化结点 返回值类型为RBNode */ RBNode *Init_RBNode(int k) { RBNode *node; node=(RBNode *)malloc(sizeof(RBNode));//动态分配空间 node->parent=NULL; node->left=NULL; node->right=NULL; node->key=k; node->color=Red; return node; } /*左旋*/ void RB_Left_Rotate(RBTree *T,RBNode *x) { RBNode *y;//创建一个新结点 y=x->right; x->right=y->left; if(y->left!=T->nil) y->left->parent=x; y->parent=x->parent; if(x->parent==T->nil) T->root=y; else if(x==x->parent->left) x->parent->left=y; else x->parent->right=y; y->left=x; x->parent=y; } /*右旋*/ void RB_Right_Rotate(RBTree *T,RBNode *y) { RBNode *x; x=y->left; y->left=x->right; if(x->right!=T->nil) x->right->parent=y; x->parent=y->parent; if(y->parent==T->nil) T->root=x; else if(y==y->parent->right) y->parent->right=x; else y->parent->left=x; x->right=y; y->parent=x; } /*查找树中关键字为k的结点，并将其返回*/ RBNode *RBTree_Search(RBTree *T, int k) { RBNode *x = T->root; while(x!=T->nil&&k!=x->key) { if(k<x->key) x=x->left; else x=x->right; } return x; } /*对树进行调整，使其符合树的性质*/ void RB_Insert_Fixup(RBTree *T,RBNode *z) { RBNode *y; while(z->parent->color==Red) { if(z->parent==z->parent->parent->left) { y=z->parent->parent->right; if(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; RB_Left_Rotate(T,z); } z->parent->color=Black; z->parent->parent->color=Red; RB_Right_Rotate(T,z->parent->parent); } } else { y=z->parent->parent->left; if(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; RB_Right_Rotate(T,z); } z->parent->color=Black; z->parent->parent->color=Red; RB_Left_Rotate(T,z->parent->parent); } } } T->root->color=Black; } /* 插入结点 以树和结点为输入 返回void */ void RB_Insert(RBTree *T,RBNode *z) { RBNode *x,*y; y=T->nil; x=T->root; while(x!=T->nil) { y=x; if(z->key<x->key) x=x->left; else x=x->right; } z->parent=y; if(y==T->nil) T->root=z; else { if(z->key<y->key) y->left=z; else y->right=z; } z->left=T->nil; z->right=T->nil; z->color=Red; RB_Insert_Fixup(T,z); } /*对树进行调整，使其符合树的性质*/ void RB_Delete_Fixup(RBTree *T,RBNode *x) { RBNode *w; while((x!=T->root)&&(x->color==Black)) { if(x==x->parent->left) { w=x->parent->right; if(w->color==Red) { w->color=Black; x->parent->color=Red; RB_Left_Rotate(T,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; RB_Right_Rotate(T,w); w=x->parent->right; } w->color=x->parent->color; x->parent->color=Black; w->right->color=Black; RB_Left_Rotate(T,x->parent); x=T->root; } } else { w=x->parent->left; if(w->color==Red) { w->color=Black; x->parent->color=Red; RB_Right_Rotate(T,x->parent); w=x->parent->right; } 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; RB_Left_Rotate(T,w); w=x->parent->left; } w->color=x->parent->color; x->parent->color=Black; w->left->color=Black; RB_Right_Rotate(T,x->parent); x=T->root; } } } x->color=Black; } /*查找结点x的最左的孩子，并将其返回*/ RBNode *RB_Tree_Minimum(RBTree *T,RBNode *x) { while(x->left!=T->nil) x=x->left; return x; } /*查找结点x的后继结点*/ RBNode *RB_Tree_Successor(RBTree *T,RBNode *x) { RBNode *y; if(x->right!=T->nil) return RB_Tree_Minimum(T,x->right); y=x->parent; while((y!=T->nil)&&(x==y->right)) { x=y; y=y->parent; } return y; } /* 删除结点 以树和结点为输入 返回void */ void RB_Delete(RBTree *T,RBNode *z) { RBNode *x,*y; if((z->left==T->nil)||(z->right==T->nil)) y=z; else y=RB_Tree_Successor(T,z); if(y->left!=T->nil) x=y->left; else x=y->right; x->parent=y->parent; if(y->parent==T->nil) T->root=x; else { if(y=y->parent->left) y->parent->left=x; else y->parent->right=x; } if(y!=z) z->key=y->key; if(y->color==Black) RB_Delete_Fixup(T,x); } /*按照规定要求打印顺序统计树 level 树的深度，初始根结点深度为0 */ int level = 0; void Print_RBTree(RBNode *node,RBNode *nil) { int i; printf("\n"); for(i=0;i<level;i++) printf(" "); if(node==nil) printf("NIL"); else { printf("(%d%c,",node->key,(node->color==Red)?'R':'B');//打印结点的关键字和颜色 level++;//到树的下一层 Print_RBTree(node->left,nil); Print_RBTree(node->right,nil); level--;//回到树的下一层 if(node->right==nil)//结点右孩子为nil，则打印 printf(")\n"); else { for(i=0;i<level;i++) printf(" "); printf(")\n"); } } } /*计算黑高度*/ void Black_Height(RBNode *node,RBNode *nil,int BH) { /* 因为任意路径从根结点到哨兵的黑高度相同 这里遍历最左的路径的结点，颜色为黑则BH自增1 */ if(node->color==Black) BH++; if(node!=nil) Black_Height(node->left,nil,BH); if(node==nil) { BH--; printf("%d",BH); } }