红黑树试验报告
目录:
一.试验描述
二.试验的目的
三.试验的具体实现
四.红黑树的算法描述(java 语言描述)
五.演示界面
六. 算法效率分析(重要)
1. 算法描述
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋
右旋等),删除,搜索(指定 Key 值节点)。
另外,红黑树实现计算树黑高的算法。
1).插入测试,输入 8,11,17,15,6,1,22,25,27,建立红黑
树,按照 红黑树信息输出方式 输出整棵红黑树以及黑高。
2).删除测试,删除 1)中红黑树中 Key=15 的节点,按照 红黑树信息输
出方式 输出调整后的整棵红黑树以及黑高。
3).随机产生 300,000 个不同自然数 Key 值(1-300,000),建立红黑
树,查找 Key=15000 的节点,输出查找花费时间。
随机产生 300,000 个不同自然数 Key 值(1-300,000),建立二叉搜
索树,查找 Key=15000 的节点,输出查找花费时间。
4). 重复 3-5 次 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 的返回值。
2. 试验的目的
为了提高算法实现和设计能力,更好的理解红黑树于二叉查找树
- 1
- 2
前往页