treap的方法与应用

《treap的方法与应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Treap的方法与应用河南省实验中学郭家宝Treap的方法与应用河南省实验中学郭家宝关键词Treap数据结构平衡树动态统计摘要Treap是一种编写容易，时间高效的一种平衡二叉查找树。本文分析了Treap的平衡性，介绍了Treap的构造方法与技巧，并与其他各种平衡树进行了比较，体现了Treap的优越性，并通过例题介绍了Treap在信息学竞赛中广泛的应用。说明本文写作的目的Treap作为被广泛应用的一种平衡树数据结构，一直以来许多人都在研究或想要研究。但笔者经历多番查找资料，很难找到一个关于Treap的系统性、总结性而又简明易懂，适合初学者阅读的

2、论文。本文想通过对Treap的介绍，起到抛砖引玉的作用。欢迎大家指正和批评。本文适合的读者·信息学奥林匹克选手·计算机或相关专业的大学生·对计算机算法、数据结构感兴趣的读者阅读本文所需掌握的预备知识·基础的数学知识·计算机操作方法·程序设计语言·基本算法·基本数据结构(堆栈、队列、二叉树)·目录1.一.序言1.我们为什么要排序2.基于比较的排序1.基于比较的排序的三种手段3.二叉查找树2.二.二叉查找树1.二叉查找树的定义、遍历与查找1.定义2.遍历3.查找2.二叉查找树的插入与删除1.插入2.删除3.二叉查找树的平衡性问题讨论3.三.Tre

3、ap3.什么是Treap1.Treap=Tree+Heap2.为什么平衡4.如何构建Treap1.旋转2.遍历和查找3.插入4.删除5.为什么要用Treap1.Treap的特点2.Treap与其他平衡树的比较4.Treap的更多操作与技巧1.懒惰删除2.查找最值3.前驱与后继4.合并重复节点5.Treap中元素的类型与排序的规则6.维护子树大小的必要性7.查找第k小元素8.求元素的排名9.维护附加关键字2.四.Treap的应用1.Treap在动态统计问题中的应用2.Treap在搜索问题中的应用3.Treap在动态规划问题中的应用4.Treap

4、与其他数据结构的相关应用9.优先队列的实现10.数据结构的复合——树套树3.五.结语1.总结2.感谢3.参考资料一、序言1.我们为什么要排序Treap是用来排序(Sort)的一种数据结构(DataStructure)。在讨论Treap之前，让我们先讨论一下，我们为什么要排序？当我们看到世间万物的时候，是否想探究其内在的规律，是否想了解自然的顺序？也许你认为，排序当然是必要的，我给出我认为需要排序的三点理由：1.有序的事物符合人类大脑结构你可以轻易地一眼看清少于6个物体，更多的话就需要数了。在有序的事物中，你可以很快得找到需要的信息，因为有序的

5、事物符合人类大脑的认识规律，内在的排序不是人类的本能。2.有序的事物符合数学规律有序的元素之间有着递增或递减的单调性。对于探究元素的内在联系，排序是极其重要的。3.打乱顺序是容易的，建立顺序是困难的如热力学第二定律指出，对不可逆过程，系统的熵总是增加的。也就是元素就是自发的走向无序的状态，建立顺序是需要代价的，不能自发的进行，所以需要我们主动来排序。2.基于比较的排序在计算机科学中，排序是一门基础的算法技术，许多算法都要以此作为基础，不同的排序算法有着不同的时间开销和空间开销。从1959年DonaldShell发明了冲破O(N2)时间屏障的希

6、尔排序，到1962年C.A.R.Hoare发明了时间复杂度为O(NlogN)快速排序，排序已经被认为是一个已解决的问题。然而至今新的排序算法依然在不断产生，如2005年被发明的图书馆排序。排序算法已经有非常多种了，最直观的，序列中数据之间需要进行比较的排序，被称为基于比较的排序。(1)基于比较的排序的三种手段在基于比较的排序算法中，存在着两种基本的思想，即对于混乱的数据，调整或者重建。于是有三种基本手段：交换、选择、插入。交换是实现调整的最直接手段，基本方法是把逆序的数据进行交换，以实现顺序排列。以重建实现排序，考虑是每次从原序列中挑出应该取

7、的元素，还是从原序列中顺序地取出元素，考虑插入到新序列中哪个位置。前者的手段为选择，后者的手段是插入。在基于交换的排序算法中，人们最早发明了O(N2)的冒泡排序(BubbleSort)。这种算法十分简单，而且只需要常数的额外的空间，所有一直以来是初学者一定要了解的排序算法。后来有人发明了基于交换的快速排序(QuickSort)，它的平均时间界为O(NlogN)。迄今为止，快速排序是一般实际应用中效果最好的算法。在基于选择的排序算法中，人们最早发明了O(N2)的选择排序(SelectionSort)。选择排序的算法更为容易理解和实现，就是每次都

8、从原序列中顺序查找出最小的元素，放入新的序列的下一个位置。在这种思想的引导下堆排序(HeapSort)被发明了。与选择排序一样，对排序仍然是每次从原序列中取出最小的