- 博客(0)
- 资源 (2)
空空如也
gcc红黑树修改完整版
2. (必做题) 红黑树、二叉搜索树的实现和性能比较
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删除,搜索(指定Key值节点)。
另外,红黑树实现计算树黑高的算法。
1).插入测试,输入 8,11,17,15,6,1,22,25,27,建立红黑树,按照 红黑树信息输出方式 输出整棵红黑树以及黑高。
2).删除测试,删除1)中红黑树中Key=15的节点,按照 红黑树信息输出方式 输出调整后的整棵红黑树以及黑高。
3).随机产生300,000个不同自然数Key值(1-300,000,每个数出现一次,出现顺序随机),建立红黑树,查找Key=15000的节点,输出查找花费时间。
用上面的数据,建立二叉搜索树,查找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的返回值。
文档要点:总结红黑树和二叉搜索树在查找上的性能分析,描述此类算法的应用。
2010-02-25
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人