Treap的方法及应用.doc

Treap的方法与应用 河南省实验中学 郭家宝 Treap的方法与应用河南省实验中学 郭家宝关键词Treap 数据结构 平衡树 动态统计摘要Treap是一种编写容易，时间高效的一种平衡二叉查找树。本文分析了Treap的平衡性，介绍了Treap的构造方法与技巧，并与其他各种平衡树进行了比较，体现了Treap的优越性，并通过例题介绍了Treap在信息学竞赛中广泛的应用。 说明本文写作的目的Treap作为被广泛应用的一种平衡树数据结构，一直以来许多人都在研究或想要研究。但笔者经历多番查找资料，很难找到一个关于Treap的系统性、总结性而又简明易懂，适合初学者阅读的论文。本文想通过对Treap的介绍，起到抛砖引玉的作用。欢迎大家指正和批评。本文适合的读者信息学奥林匹克选手计算机或相关专业的大学生对计算机算法、数据结构感兴趣的读者阅读本文所需掌握的预备知识基础的数学知识计算机操作方法程序设计语言基本算法基本数据结构(堆栈、队列、二叉树)目录序言我们为什么要排序基于比较的排序基于比较的排序的三种手段二叉查找树二叉查找树二叉查找树的定义、遍历与查找定义遍历查找二叉查找树的插入与删除插入删除二叉查找树的平衡性问题讨论Treap 什么是TreapTreap = Tree + Heap 为什么平衡如何构建Treap旋转遍历和查找插入删除为什么要用TreapTreap的特点Treap与其他平衡树的比较Treap的更多操作与技巧懒惰删除查找最值前驱与后继合并重复节点Treap中元素的类型与排序的规则维护子树大小的必要性查找第k小元素求元素的排名维护附加关键字Treap的应用Treap在动态统计问题中的应用Treap在有哪些信誉好的足球投注网站问题中的应用Treap在动态规划问题中的应用Treap与其他数据结构的相关应用优先队列的实现数据结构的复合——树套树结语总结感谢参考资料一、序言1. 我们为什么要排序Treap是用来排序(Sort)的一种数据结构(Data Structure)。在讨论Treap之前，让我们先讨论一下，我们为什么要排序？当我们看到世间万物的时候，是否想探究其内在的规律，是否想了解自然的顺序？也许你认为，排序当然是必要的，我给出我认为需要排序的三点理由：有序的事物符合人类大脑结构你可以轻易地一眼看清少于6个物体，更多的话就需要数了。在有序的事物中，你可以很快得找到需要的信息，因为有序的事物符合人类大脑的认识规律，内在的排序不是人类的本能。有序的事物符合数学规律有序的元素之间有着递增或递减的单调性。对于探究元素的内在联系，排序是极其重要的。打乱顺序是容易的，建立顺序是困难的如热力学第二定律指出，对不可逆过程，系统的熵总是增加的。也就是元素就是自发的走向无序的状态，建立顺序是需要代价的，不能自发的进行，所以需要我们主动来排序。2. 基于比较的排序在计算机科学中，排序是一门基础的算法技术，许多算法都要以此作为基础，不同的排序算法有着不同的时间开销和空间开销。从1959年Donald Shell发明了冲破O(N2)时间屏障的希尔排序，到1962年C. A. R. Hoare发明了时间复杂度为O(NlogN)快速排序，排序已经被认为是一个已解决的问题。然而至今新的排序算法依然在不断产生，如2005年被发明的图书馆排序。排序算法已经有非常多种了，最直观的，序列中数据之间需要进行比较的排序，被称为基于比较的排序。(1) 基于比较的排序的三种手段在基于比较的排序算法中，存在着两种基本的思想，即对于混乱的数据，调整或者重建。于是有三种基本手段：交换、选择、插入。交换是实现调整的最直接手段，基本方法是把逆序的数据进行交换，以实现顺序排列。以重建实现排序，考虑是每次从原序列中挑出应该取的元素，还是从原序列中顺序地取出元素，考虑插入到新序列中哪个位置。前者的手段为选择，后者的手段是插入。在基于交换的排序算法中，人们最早发明了O(N2)的冒泡排序(Bubble Sort)。这种算法十分简单，而且只需要常数的额外的空间，所有一直以来是初学者一定要了解的排序算法。后来有人发明了基于交换的快速排序(Quick Sort)，它的平均时间界为O(NlogN)。迄今为止，快速排序是一般实际应用中效果最好的算法。在基于选择的排序算法中，人们最早发明了O(N2)的选择排序(Selection Sort)。选择排序的算法更为容易理解和实现，就是每次都从原序列中顺序查找出最小的元素，放入新的序列的下一个位置。在这种思想的引导下堆排序(Heap Sort) 被发明了。与选择排序一样，对排序仍然是每次从原序列中取出最小的元素，放在新序列的下一个位置。但是不同在于使用了堆这一数据结构，取出最小元素仅需要O(LogN)的时间，于是它的时间复杂度为O(NlogN)。我们玩扑克牌的时候，习惯于每起得一张牌后