算法基础 上机实验 2 学 期: 2015 (秋)
Project 2: 红黑树和顺序统计树 实验1：实现红黑树的基本算法， 分别对整数 n =20、40、60、80、100，随机生成n 个互异的正整数（K1, K2, K3, ……, Kn）, 以这 n 个正整数作为节点的关键字，向一棵初始空的红黑树中依次插入n 个节点，统计算法运行所需时间 ，画出时间曲线。（红黑树采用三叉链表） 实验2：对上述生成的红黑树，找出树中的第n/3小的节点和第2n/3小的节点，并删除这两个节点，统计算法 运行所需时间 ， 画出时间曲线。
实验要求 1、输入输出格式: c)output： a)两个实验建立一个共同的project文件夹，每个文件夹分别包含3个文件夹： input文件夹：存放输入数据 source文件夹：源程序 output文件夹：输出数据 b)input： 输入文件中每行一个随机数据，总行数大于等于100 分别读取20、40、60、80、100个正整数进行构建红黑树,插入删除节点的试验 c)output： 为每种数据规模建立一个子文件夹，分别为size20,size40,size60,size80,size100,其输出结果数据导出到其对应子文件下面 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小的节点和第2n/3小节点，与OS-SELECT(T.root,i)的结果delete_data进行对比检查
实验要求 3、实验细节 a)本次实验要求实现的是附加一个x.size信息的红黑即顺序统计树 b)输入数据要求是互不相同的正整数 c)自行设计一个较方便的函数，使得在检查时能够显示树的详细信息，以便能够观察到结点插入、删除前后树的结构变化(包括结点颜色，秩,父子节点关系等信息) ，每行输出一个key的信息 d)第二个实验要求删除的第n/3小的节点和第2n/3小的节点的n是动态变化的，而不是静态的，执行一次删除操作n的值减少1，例如n为40，首先删除n/3=13小节点 然后删除2*39/3=26小的节点 e)由于删除节点等函数代码量比较大,要注意代码可读性和条理性,注释清楚实现过程
实验要求 4、性能测试 a)用适当的方法，或工具记录排序算法在执行时所消耗的时，图表格式参考实验一给出的图表式样； b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时间曲线图,比较不同规模下时间曲线变化规律的异同，给出分析.
实验要求 5、注意事项 a) 实验报告中要有必要的实验过程截图和图表 b)project目录结构严格按照输入输出格式的要求； d) 实验杜绝抄袭他人代码或者实验结果，如发现代码高度相似或者实验报告雷同者算0分； e) 实验报告格式参照project1。 f) 实验报告请严格按照“学号-姓名-project2.rar”的方式上传到ftp服务器。 g) 实验截止时间：11月18号 24:00