资源描述:
《红黑树源程序》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、GeneratedbyFoxitPDFCreator©FoxitSoftwarehttp://www.foxitsoftware.comForevaluationonly.文件:G:研一资料(下)算法导论RBTreeRBTree.cpp2011/4/8,16:32:30RBTreeRBTree.cpp2011/4/8,16:32:30/*作者:黄乐君学校:中国科学技术大学日期:2011-3-20*//*题目要求红黑树、二叉搜索树的实现和性能比较问题描述:实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删
2、除,搜索(指定Key值节点)。另外,红黑树实现计算树黑高的算法。实验要求:1).插入测试,输入13,8,11,17,15,6,1,22,25,27,建立红黑树,按照红黑树信息输出方式输出整棵红黑树以及黑高。2).删除测试,删除1)中红黑树中Key=15的节点,按照红黑树信息输出方式输出调整后的整棵红黑树以及黑高。3).随机产生300,000个不同自然数Key值(1-300,000,每个数出现一次,出现顺序随机),建立红黑树,查找Key=15000的节点,输出查找花费时间。用上面的数据,建立二叉搜索树,查找Key=15000的节点,输出查找
3、花费时间。4).重复3-5次3)中操作,求各自平均时间。5).在1)-4)的红黑树算法基础上修改完成P30714.1-4算法OS_Key_Rank(T,k).输入1,2,3,4,5,6,7,8建树,k=6,输出OS_Key_Rank的返回值。*/#include#include#include#include#defineRED0#defineBLACK1#defineNUM20#defineMAX_NUM300000typedefstructRBTNode{int
4、key;structRBTNode*parent,*left,*right;intcolor;intsize;//扩张红黑树}RBTNode,*RBTree;RBTreenil,root;intprintnode=0;/*记录结点的高度,在PrintRBTree函数里使用*//*构造叶子结点*/voidInitLeafNode();/*创建一个新的树结点*/第1页GeneratedbyFoxitPDFCreator©FoxitSoftwarehttp://www.foxitsoftware.comForevaluationonly.文件:
5、G:研一资料(下)算法导论RBTreeRBTree.cpp2011/4/8,16:32:30RBTreeRBTree.cpp2011/4/8,16:32:30RBTreeCreateNode(intkey,intcolor);/*找出树种最小的key并返回key的指针*/RBTreeTreeMinimum(RBTreex);/*找出中序遍历顺序下它的后继并返回它的指针*/RBTreeTreeSuccessor(RBTreex);/*二叉查找树的插入操作*/voidTreeInsert(RBTree&T,RBTreez);/*左旋
6、*/voidLeftRotate(RBTree&T,RBTreex);/*右旋*/voidRightRotate(RBTree&T,RBTreex);/*红黑树的插入操作*/voidRBTreeInsert(RBTree&T,RBTreez);/*红黑树插入后调整颜色达到红黑树*/voidRBTreeInsertFixup(RBTree&T,RBTreez);/*红黑树树的删除操作*/voidRBTreeDelete(RBTree&T,RBTreez);/*红黑树删除后调整颜色达到红黑树*/voidRBDeleteFixup(RBTree
7、&T,RBTreez);/*中序打印树结点*/voidPrintRBTree(RBTreeT);/*查找树中与key值相同的结点,返回该结点的指针*/RBTreeTreeNodeSearch(RBTreeT,intkey,int&outcome);/*红黑树的黑高度*/intBlackHeight(RBTreeT);/*计算查询key=15000所用的时间*/voidPrintSearchTime(RBTreeT,inttimes,intoutcome,intrb);voidInitLeafNode()//构造叶子结点{nil=(RBTr
8、ee)malloc(sizeof(RBTree));root=(RBTree)malloc(sizeof(RBTree));nil->color=BLACK;nil->left=NULL;ni