算法基础 上机实验 3 学 期: 2017 (秋)

Project 3: 红黑树和顺序统计树 实验1：实现红黑树的基本算法， 对n的取值分别为 12、24、36、48、60，随机生成n 个互异的正整数（K1, K2, K3, ……, Kn）作为节点的关键字，向一棵初始空的红黑树中依次插入这n 个节点，统计算法运行所需时间 ，画出时间曲线。（红黑树采用三叉链表） 实验2：对上述生成的红黑树，找出树中的第n/3小的节点和第n/4小的节点，并删除这两个节点，统计算法运行所需时间 ， 画出时间曲线。

实验要求 1、输入输出格式: c)output： a)两个实验建立一个共同的project文件夹，每个文件夹分别包含3个文件夹： input文件夹：存放输入数据 source文件夹：源程序 output文件夹：输出数据 b)input： 实验一输入文件中每行一个随机数据，总行数大于等于60，分别读取12、24、36、48、60个正整数进行构建红黑树。 实验二不需要输入文件，直接对实验一构造的红黑树进行删除节点操作。 c)output： 为每种数据规模建立一个子文件夹，分别为size12,size24,size36,size48,size60,其输出结果数据导出到其对应子文件下面 preoreder.txt ：输出构建好的红黑树的前序遍历序列 inorder.txt: 输出构建好的红黑树的中序遍历序列 postorder.txt: 输出构建好的红黑树的后序遍历序列 time1.txt：运行时间效率的数据。测试插入操作构建树的花费的时间，要求每插入10个节点测试一下花费的时间，并记录下构建完成所花的总时间 第二个实验输出结果同样是导入到相同的对应子文件夹下面 delete_data.txt ：输出删除的两个数据 time2.txt: 测试删除掉实验要求删除掉的两个节点所花费的时间，每删除掉一个节点测试一次

实验要求 2、算法实现: a)本次实验需要实现红黑树部分基本算法主要包括如下： 1)实现红黑树左旋操作 LEFT-ROTATE(T, x) 实现右旋操作 RIGHT-ROTATE(T, x) 2)实现红黑树插入节点的操作 RB-INSERT(T, z)以及插入之后修正为红黑书的的算法 RB-INSERT-FIXUP(T, x)（在函数实现过程中对于 case1 case2 case3 的三部分代码要注释清楚） 3)实现红黑树删除节点的操作 RB-DELETE(T, z)以及插入之后修正为红黑书的的算法 RB-DELETE-FIXUP(T, x) （在函数实现过程中对于 case1 case2 case3 case4的四部分代码要注释清楚） 4)实现按要求数据构建顺序统计树的操作 5)实现遍历输出构建好的红黑树的操作 6)实现查找顺序统计树的第i小关键字的操作OS-SELECT(T.root,i) b) 为了验证第二个实验的正确性，要求编写一个检测程序，使用中位数一章的线性时间的选择算法Select(a,p,r,i)在输入数据找到找到第n/3小的节点和第n/4小节点，与OS-SELECT(T.root,i)的结果delete_data进行对比检查

实验要求 3、实验细节 a)本次实验要求实现的是附加一个x.size信息的红黑即顺序统计树 b)输入数据要求是互不相同的正整数 c)自行设计一个较方便的函数，使得在检查时能够显示树的详细信息，以便能够观察到结点插入、删除前后树的结构变化(包括结点颜色，秩,父子节点关系等信息) ，每行输出一个key的信息 d)第二个实验要求删除的第n/3小的节点和第n/4小的节点的n是动态变化的，而不是静态的，执行一次删除操作n的值减少1，例如n为12，首先删除12/3=4小节点 然后删除12/4=3小的节点 e)由于删除节点等函数代码量比较大,要注意代码可读性和条理性,注释清楚实现过程

实验要求 4、性能测试 a)用适当的方法，或工具记录排序算法在执行时所消耗的时，图表格式参考实验一给出的图表式样； b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时间曲线图,比较不同规模下时间曲线变化规律的异同，给出分析.

5、注意事项： a)实验报告中要有必要的实验过程截图和图表； b)图片要有单位，横纵坐标等信息； c)ex1,ex2目录结构严格按照实验格式的要求； d)代码中需要有必要的注释； e)实验杜绝抄袭他人代码或者实验结果，如发现代码高度相似或者实验报告雷同者算0分； f)实验报告模板另附课程主页上。（qq群也有） 算法基础--2012

6、实验提交： a)实验要求提交源码，输入输出结果，实验报告。 b)将上述文件夹严格打包成.rar格式，命名方式：学号-姓名-project3.rar。 发送邮件给邮箱：ncaa_lab508@126.com。邮箱邮件主题为“学号-姓名- project3”，助教在收到邮件后会及时发送确认邮件。 c)如果有同学在截止日期前要重复提交，邮件主题需说明重复提交。 （注：重复提交 打包命名方式： (2)学号-姓名-project3.rar (3)学号-姓名-project3.rar 等 邮件主题也相应改为：(2)学号-姓名-project3 (3)学号-姓名-project3 等 尽量一次性做好再提交，不要重复提交） d)第三次实验截止日期：12月27日晚24点，逾期提交实验成绩将作0分处 理。 算法基础--2012