Treap结构上的基本操作
① 用数据结构知识设计和实现treap结构以及上的基本操作:插入和删除。
② 编程实现随机二元查找树。
③ 产生若干个依次插入二元查找树的元素序列(元素个数自己设定),针对该序列分别实现三种情况:插入到一般二元查找树、插入到treap、用随机二元查找树处理。分别得出三种情况处理后的结果二元树的高度,进行实际的数据对比,从对比结果中发现一些规律。
④ 应模拟出各个操作的结果,模拟过程应该是可视的,即可以看到依次插入元素后各结构的变化情况。
⑤ 对随机二元树的高度、对treap的高度、对treap中的插入操作、对treap插入操作中旋转次数等指标进行理论分析。