《红黑树源程序.pdf》由会员分享，可在线阅读，更多相关《红黑树源程序.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30/*作者：黄乐君学校：中国科学技术大学日期：2011-3-20*/*题目要求红黑树、二叉搜索树的实现和性能比较问题描述：实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋、右旋等），删除，搜索（指定Key值节点）。另外，红黑树实现计算树黑高的算法。实验要求：1).插入测试，输入13,8，11，17，15，6，1，22，25，27，建立红黑树，按照 红黑树信息输出方式 输出整棵红黑树以及黑高。2).删除测试，删除1）中
2、红黑树中Key=15的节点，按照 红黑树信息输出方式输出调整后的整棵红黑树以及黑高。3).随机产生300,000个不同自然数Key值（1300,000，每个数出现一次，出现顺序随机），建立红黑树，查找Key=15000的节点，输出查找花费时间。用上面的数据，建立二叉搜索树，查找Key=15000的节点，输出查找花费时间。4).重复35次3）中操作，求各自平均时间。5).在1)4)的红黑树算法基础上修改完成P307 14.1-4算法OS_Key_Rank(T,k).输入 1,2,3,4,5,6,7,8 建树，k=6,输出OS_Key_Rank的返回值。*/#include#include#inc
3、lude#include#define RED 0#define BLACK 1#define NUM 20#define MAX_NUM 300000typedef struct RBTNode int key;struct RBTNode*parent,*left,*right;int color;int size;/扩张红黑树RBTNode,*RBTree;RBTree nil,root;int printnode=0;/*记录结点的高度,在PrintRBTree函数里使用*/*构造叶子结点*/void InitLeafNode();/*创建一个新的树结点*/第 1 页Generated
4、 by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30RBTree CreateNode(int key,int color);/*找出树种最小的key并返回key的指针*/RBTree TreeMinimum(RBTree x);/*找出中序遍历顺序下它的后继并返回它的指针*/RBTree TreeSuccessor(RBTree x);/*二叉查找树的插
5、入操作*/void TreeInsert(RBTree&T,RBTree z);/*左旋*/void LeftRotate(RBTree&T,RBTree x);/*右旋*/void RightRotate(RBTree&T,RBTree x);/*红黑树的插入操作*/void RBTreeInsert(RBTree&T,RBTree z);/*红黑树插入后调整颜色达到红黑树*/void RBTreeInsertFixup(RBTree&T,RBTree z);/*红黑树树的删除操作*/void RBTreeDelete(RBTree&T,RBTree z);/*红黑树删除后调整颜色达到红黑树
6、*/void RBDeleteFixup(RBTree&T,RBTree z);/*中序打印树结点*/void PrintRBTree(RBTree T);/*查找树中与key值相同的结点，返回该结点的指针*/RBTree TreeNodeSearch(RBTree T,int key,int&outcome);/*红黑树的黑高度*/int BlackHeight(RBTree T);/*计算查询key=15000所用的时间*/void PrintSearchTime(RBTree T,int times,int outcome,int rb);void InitLeafNode()/构造叶子
7、结点 nil=(RBTree)malloc(sizeof(RBTree);root=(RBTree)malloc(sizeof(RBTree);nil-color=BLACK;nil-left=NULL;nil-right=NULL;nil-key=-1;nil-size=0;/红黑树扩张 root=nil;第 2 页Generated by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2
8、011/4/8,16:32:30RBTree CreateNode(int key,int color)RBTree x=(RBTNode*)malloc(sizeof(RBTNode);x-color=color;x-key=key;x-left=nil;x-right=nil;x-parent=NULL;x-size=1;/红黑树扩张 return x;RBTree TreeMinimum(RBTree x)while(x-left!=nil)x=x-left;return x;RBTree TreeSuccessor(RBTree x)RBTree y;if(x-right!=nil)r
9、eturn TreeMinimum(x-right);y=x-parent;while(y!=nil&x=y-right)x=y;y=y-parent;return y;void TreeInsert(RBTree&T,RBTree z)RBTree x,y;y=nil;x=root;while(x!=nil)y=x;if(z-key key)x=x-left;else第 3 页Generated by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011
10、/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 x=x-right;z-parent=y;if(y=nil)root=z;else if(z-key key)y-left=z;else y-right=z;/红黑树扩张，设置size的值 while(z!=root)z-parent-size=z-parent-right-size+z-parent-left-size+1;z=z-parent;void LeftRotate(RBTree&T,RBTree x)RBTree y;y=x-right;x-right=y-left;if(y-left
11、!=nil)y-left-parent=x;y-parent=x-parent;if(x-parent=nil)root=y;else if(x=x-parent-left)x-parent-left=y;else x-parent-right=y;第 4 页Generated by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 y-left=x;x-pa
12、rent=y;/红黑树扩张，设置size值 y-size=x-size;x-size=x-right-size+x-left-size+1;void RightRotate(RBTree&T,RBTree x)RBTree y;y=x-left;x-left=y-right;if(y-right!=nil)y-right-parent=x;y-parent=x-parent;if(x-parent=nil)root=y;else if(x=x-parent-left)x-parent-left=y;else x-parent-right=y;y-right=x;x-parent=y;/红黑树扩
13、张，设置size值 y-size=x-size;x-size=x-right-size+x-left-size+1;void RBTreeInsert(RBTree&T,RBTree z)TreeInsert(T,z);z-left=nil;z-right=nil;z-color=RED;RBTreeInsertFixup(T,z);void RBTreeInsertFixup(RBTree&T,RBTree z)RBTree y;while(z-parent-color=RED)第 5 页Generated by Foxit PDF Creator Foxit Softwarehttp:/
14、For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 if(z-parent=z-parent-parent-left)y=z-parent-parent-right;/*case 1*/if(y-color=RED)z-parent-color=BLACK;y-color=BLACK;z-parent-parent-color=RED;z=z-parent-parent;/*case 2*/else if(z=z-parent-right
15、)z=z-parent;LeftRotate(T,z);/*case 3*/z-parent-color=BLACK;z-parent-parent-color=RED;RightRotate(T,z-parent-parent);else y=z-parent-parent-left;/*case 1*/if(y-color=RED)z-parent-color=BLACK;y-color=BLACK;z-parent-parent-color=RED;z=z-parent-parent;/*case 2*/else if(z=z-parent-left)z=z-parent;RightRo
16、tate(T,z);/*case 3*/z-parent-color=BLACK;z-parent-parent-color=RED;LeftRotate(T,z-parent-parent);第 6 页Generated by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 root-color=BLACK;void RBTreeDelete(RBTree
17、&T,RBTree z)RBTree x,y;if(z-left=nil|z-right=nil)y=z;else y=TreeSuccessor(z);if(y-left=nil)x=y-left;else x=y-right;x-parent=y-parent;if(y-parent=nil)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)RBDeleteFixup(T,x);free(y);void RBDeleteFixup
18、(RBTree&T,RBTree x)RBTree w;while(x!=root&x-color=BLACK)if(x=x-parent-left)第 7 页Generated by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 w=x-parent-right;if(w-color=RED)/*case 1*/w-color=BLACK;x-paren
19、t-color=RED;LeftRotate(T,x-parent);w=x-parent-right;if(w-left-color=BLACK&w-right-color=BLACK)/*case 2*/w-color=RED;x=x-parent;else if(w-right-color=BLACK)/*case 3*/w-left-color=BLACK;w-color=RED;RightRotate(T,w);w=x-parent-right;/*case 4*/w-color=x-parent-color;x-parent-color=BLACK;w-right-color=BL
20、ACK;LeftRotate(T,x-parent);x=root;else w=x-parent-left;if(w-color=RED)/*case 1*/w-color=BLACK;w-parent-color=RED;RightRotate(T,x-parent);w=x-parent-left;if(w-left-color=BLACK&w-right-color=BLACK)/*case 2*/w-color=RED;x=x-parent;else if(w-left-color=BLACK)/*case 3*/w-right-color=BLACK;w-color=RED;第 8
21、 页Generated by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 LeftRotate(T,w);w=x-parent-left;/*case 4*/w-color=x-parent-color;x-parent-color=BLACK;w-left-color=BLACK;RightRotate(T,x-parent);x=root;/*whi
22、le*/RBTree TreeNodeSearch(RBTree T,int key,int&outcome)RBTree find=T;while(find!=nil)if(key=find-key)outcome=1;break;else if(key key)find=find-left;else find=find-right;if(find=nil)outcome=0;return find;void PrintRBTree(RBTree T)if(T!=nil)for(int i=0;i key);if(T-color=BLACK)printf(B,n);第 9 页Generate
23、d by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 else printf(R,n);printnode+;PrintRBTree(T-left);PrintRBTree(T-right);printnode-;for(int j=0;j=printnode;j+)printf();printf(),n);else for(int i=0;i left
24、;int height=0;while(t!=NULL)if(t-color=BLACK)height+;t=t-left;return height;void PrintSearchTime(RBTree T,int times,int outcome,int rb)RBTree find;clock_t start,end;double duration;start=clock();/*需要计算时间的代码*/for(int i=0;i key key)return OS_KEY_RANK(T-left,key);else if(T-key right,key)+T-left-size+1;
25、else return T-left-size+1;return-100000;/如果没有找到相同的key值，返回一个负数int main()RBTree nodeNUM,find;int outcome=0;/记录查询的结果,成功:1,失败:0 int num=0;/记录红黑树的结点数 int height=0;/记录树的黑高度 InitLeafNode();printf(请输入你要建立红黑树的结点数目:);scanf(%d,&num);int key=0;第 11 页Generated by Foxit PDF Creator Foxit Softwarehttp:/ For evalua
26、tion only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 printf(请依次输入%d个结点的值:,num);for(int i=0;i num;i+)scanf(%d,&key);nodei=CreateNode(key,RED);RBTreeInsert(root,nodei);/*输出插入结点后树的模型*/printf(*插入结点后树的模型*n);PrintRBTree(root);height=BlackHeight(root);printf(*n);pr
27、intf(此红黑树的黑高度是:%dn,height);/*输出删除key=15结点后树的模型*/printf(*删除key=15结点后树的模型*n);find=TreeNodeSearch(root,15,outcome);if(find!=nil&outcome!=0)RBTreeDelete(root,find);PrintRBTree(root);printf(=n);height=BlackHeight(root);printf(此红黑树的黑高度是:%dn,height);printf(=n);else printf(=查找不成功=nn);static RBTree rb_randno
28、deMAX_NUM;/一定要用static，或者定义为全局变量（存放在 全局静态区）srand(unsigned)time(NULL);/*建立300000个结点的红黑二叉树*/free(root);InitLeafNode();for(int j=0;j MAX_NUM;j+)key=rand()%MAX_NUM+1;rb_randnodej=CreateNode(key,RED);RBTreeInsert(root,rb_randnodej);int times=0;printf(请输入你要查询key关键字的次数:);scanf(%d,×);第 12 页Generated by
29、Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp 2011/4/8,16:32:30RBTreeRBTree.cpp 2011/4/8,16:32:30 PrintSearchTime(TreeNodeSearch(root,15000,outcome),times,outcome,1);/*建立300000个结点的二叉查找树*/free(root);InitLeafNode();static RBTree randnodeMAX_NUM;for(int m=0
30、;m MAX_NUM;m+)key=rand()%MAX_NUM+1;randnodem=CreateNode(key,RED);TreeInsert(root,randnodem);PrintSearchTime(TreeNodeSearch(root,15000,outcome),times,outcome,0);static RBTree os_keyNUM;/一定要用static，或者定义为全局变量（存放在全局静态 区）/*建立扩张红黑树*/free(root);InitLeafNode();int num2=0;printf(请输入你要建立红黑树的结点数目:);scanf(%d,&n
31、um2);int key2=0;printf(请依次输入%d个结点的值:,num2);for(int k=0;k num2;k+)scanf(%d,&key2);nodek=CreateNode(key2,RED);RBTreeInsert(root,nodek);int t=0,os=0;printf(请输入查找的key值:);scanf(%d,&os);t=OS_KEY_RANK(root,os);PrintRBTree(root);if(t=0)printf(key=%d在红黑树中找不到!n,os);else printf(key=%d在红黑树中的秩为:%d n,os,t);return 1;第 13 页Generated by Foxit PDF Creator Foxit Softwarehttp:/ For evaluation only.