Treap的方法与应用

Treap的方法与应用河南省实验中学郭家宝Treap的方法与应用河南省实验中学郭家宝关键词Treap数据结构平衡树动态统计摘要Treap是一种编写容易，时间高效的一种平衡二叉查找树。本文分析了Treap的平衡性，介绍了Treap的构造方法与技巧，并与其他各种平衡树进行了比较，体现了Treap的优越性，并通过例题介绍了Treap在信息学竞赛中广泛的应用。说明本文写作的目的Treap作为被广泛应用的一种平衡树数据结构，一直以来许多人都在研究或想要研究。但笔者经历多番查找资料，很难找到一个关于Treap的系统性、总结性而又简明易懂，适合初学者阅读的论文。本文想通过对Treap的介绍，起到抛砖引玉的作用。欢迎大家指正和批评。本文适合的读者信息学奥林匹克选手计算机或相关专业的大学生对计算机算法、数据结构感兴趣的读者阅读本文所需掌握的预备知识基础的数学知识计算机操作方法程序设计语言基本算法基本数据结构(堆栈、队列、二叉树)目录1.一.序言1.我们为什么要排序2.基于比较的排序1.基于比较的排序的三种手段3.二叉查找树2.二.二叉查找树1.二叉查找树的定义、遍历与查找1.定义2.遍历3.查找2.二叉查找树的插入与删除1.插入2.删除3.二叉查找树的平衡性问题讨论3.三.Treap1.什么是Treap1.Treap=Tree+Heap2.为什么平衡2.如何构建Treap1.旋转2.遍历和查找3.插入4.删除3.为什么要用Treap1.Treap的特点2.Treap与其他平衡树的比较4.Treap的更多操作与技巧1.懒惰删除2.查找最值3.前驱与后继4.合并重复节点5.Treap中元素的类型与排序的规则6.维护子树大小的必要性7.查找第k小元素8.求元素的排名9.维护附加关键字4.四.Treap的应用1.Treap在动态统计问题中的应用2.Treap在搜索问题中的应用3.Treap在动态规划问题中的应用4.Treap与其他数据结构的相关应用1.优先队列的实现2.数据结构的复合——树套树5.五.结语1.总结2.感谢3.参考资料一、序言1.我们为什么要排序Treap是用来排序(Sort)的一种数据结构(DataStructure)。在讨论Treap之前，让我们先讨论一下，我们为什么要排序？当我们看到世间万物的时候，是否想探究其内在的规律，是否想了解自然的顺序？也许你认为，排序当然是必要的，我给出我认为需要排序的三点理由：1.有序的事物符合人类大脑结构你可以轻易地一眼看清少于6个物体，更多的话就需要数了。在有序的事物中，你可以很快得找到需要的信息，因为有序的事物符合人类大脑的认识规律，内在的排序不是人类的本能。2.有序的事物符合数学规律有序的元素之间有着递增或递减的单调性。对于探究元素的内在联系，排序是极其重要的。3.打乱顺序是容易的，建立顺序是困难的如热力学第二定律指出，对不可逆过程，系统的熵总是增加的。也就是元素就是自发的走向无序的状态，建立顺序是需要代价的，不能自发的进行，所以需要我们主动来排序。2.基于比较的排序在计算机科学中，排序是一门基础的算法技术，许多算法都要以此作为基础，不同的排序算法有着不同的时间开销和空间开销。从1959年DonaldShell发明了冲破O(N2)时间屏障的希尔排序，到1962年C.A.R.Hoare发明了时间复杂度为O(NlogN)快速排序，排序已经被认为是一个已解决的问题。然而至今新的排序算法依然在不断产生，如2005年被发明的图书馆排序。排序算法已经有非常多种了，最直观的，序列中数据之间需要进行比较的排序，被称为基于比较的排序。(1)基于比较的排序的三种手段在基于比较的排序算法中，存在着两种基本的思想，即对于混乱的数据，调整或者重建。于是有三种基本手段：交换、选择、插入。交换是实现调整的最直接手段，基本方法是把逆序的数据进行交换，以实现顺序排列。以重建实现排序，考虑是每次从原序列中挑出应该取的元素，还是从原序列中顺序地取出元素，考虑插入到新序列中哪个位置。前者的手段为选择，后者的手段是插入。在基于交换的排序算法中，人们最早发明了O(N2)的冒泡排序(BubbleSort)。这种算法十分简单，而且只需要常数的额外的空间，所有一直以来是初学者一定要了解的排序算法。后来有人发明了基于交换的快速排序(QuickSort)，它的平均时间界为O(NlogN)。迄今为止，快速排序是一般实际应用中效果最好的算法。在基于选择的排序算法中，人们最早发明了O(N2)的选择排序(SelectionSort)。选择排序的算法更为容易理解和实现，就是每次都从原序列中顺序查找出最小的元素，放入新的序列的下一个位置。在这种思想的引导下堆排序(HeapSort)被发明了。与选择排序一样，对排序仍然是每次从原序列中取出最小的元素，放在新序列的下一个位置。但是不同在于使用了堆这一数据结构，取出最小元素仅需要O(LogN)的时间，于是它的时间复杂度为O(NlogN)。我们玩扑克牌的时候，习惯于每起得一张牌后，直接将它是插入到合适的位置，以实现顺序的排列。插入排序(InsertionSort)正是运用了这种思想，方法是从原序列中取出下一个元素，然后再新序列中找到合适的位置并插入。使用线性表存储时，由于新序列中已有的元素是已经有序的，确定插入的位置时，可以使用二分查找(BinarySearch)，使时间降为O(LogN)。但是不同于扑克牌，在线性表中，我们只能把这个位置后面的元素一个个向后移动，才能插入这个元素，最坏情况下可能会移动所有的元素，时间为O(N)。为了加快插入，我们可以使用链表，这样插入的时间复杂度无论如何就变成了O(1)了，但是确定插入的合适的位置却变成了O(N)。总而言之无论是基于线性表还是基于链表的简单插入排序，时间复杂度都是O(N2)。为了解决这种矛盾，人们发明了跳跃表(SkipList)和二叉查找树(BinarySearchTree)，基于这两种数据结构的排序的期望时间复杂度都是O(NlogN)。3.二叉查找树二叉查找树(BinarySearchTree)是基于插入思想的一种在线的排序数据结构。它又叫二叉搜索树(BinarySearchTree)、二叉排序树(BinarySortTree)，简称BST。这种数据结构的基本思想是在二叉树的基础上，规定一定的顺序，使数据可以有序地存储。二叉查找树运用了像二分查找一样的查找方式，并且基于链式结构存储，从而实现了高效的查找效率和完美的插入时间。二、二叉查找树1.二叉查找树的定义、遍历与查找(1)定义13245图SEQ图\*ARABIC1二叉查找树(BinarySearchTree)或者是一棵空树，或者是具有下列性质的二叉树：1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3.它的左、右子树也分别为二叉查找树。4.上述性质被称为BST性质。可以看出，二叉查找树是递归定义的，如图1是一个二叉查找树。代码1给出了一个BST节点的定义。structBST_Node{BST_Node*left,*right;//节点的左右子树的指针intvalue;//节点的值};代码1(2)遍历对于一个已知的二叉查找树，从小到大输出其节点的值，只需对其进行二叉树的中序遍历，即递归地先输出其左子树，再输出其本身，然后输出其右子树。遍历的时间复杂度为O(N)。代码2为把一个以root为根的BST所有节点的值从小到大输出到标准输出流。BST_Node*root;voidBST_Print(BST_Node*P){if(P){BST_Print(P-left);printf(“%d\n”,P-value);BST_Print(P-right);}}intmain(){BST_Print(root);return0;}代码2(3)查找对于一个已知的二叉查找树，在其中查找特定的值，方法如下。1.从根节点开始查找；2.如果当前节点的值就是要查找的值，查找成功；3.如果要查找的值小于当前节点的值，在当前节点的左子树中查找该值；4.如果要查找的值大于当前节点的值，在当前节点的右子树中查找该值；5.如果当前节点为空节点，查找失败，二叉查找树中没有要查找的值。6.查找的期望时间复杂度为O(logN)。代码3为在一个已知的二叉查找树中查找值5。BST_Node*root;BST_Node*BST_Find(BST_Node*P,intvalue){if(!P)return0;//查找失败if(P-value==value)returnP;//查找成功elseif(valueP-value)returnBST_Find(P-left,value);//在左子树中查找elsereturnBST_Find(P-right,value);//在右子树中查找}intmain(){BST_Node*result;result=BST_Find(root,5);//在BST中查找值为5的节点if(result)printf(Found!);elseprintf(NotFound!);return0;}代码32.二叉查找树的插入与删除(1)插入在二叉查找树中插入元素，要建立在查找的基础上。基本方法是类似于线性表中的二分查找，不断地在树中缩小范围定位，最终找到一个合适的位置插入。具体方法如下所述。1.从根节点开始插入；2.如果要插入的值小于等于当前节点的值，在当前节点的左子树中插入；3.如果要插入的值大于当前节点的值，在当前节点的右子树中插入；4.如果当前节点为空节点，在此建立新的节点，该节点的值为要插入的值，左右子树为空，插入成功。5.对于相同的元素，一种方法我们规定把它插入左边，另一种方法是我们在节点上再加一个域，记录重复节点的个数。上述方法为前者。插入的期望时间复杂度为O(logN)。代码4为在一个二叉查找树中插入值5。BST_Node*root;BST_Node*BST_Insert(BST_Node*&P,intvalue)//节点指针要传递引用{if(!P){P=newBST_Node;//插入成功P-value=value;}elseif(value=value)returnBST_Insert(P-left,value);//在左子树中插入elsereturnBST_Insert(P-right,value);//在右子树中插入}intmain(){BST_Insert(root,5);//在BST中插入值5return0;}代码4(2)删除二叉查找树的删除稍有些复杂，要分三种情况分别讨论。基本方法是要先在二叉查找树中找到要删除的节点的位置，然后根据节点分以下情况：1452删除它451图SEQ图\*ARABIC2情况一，该节点是叶节点(没有非空子节点的节点)，直接把节点删除即可。情况二，该节点是链节点(只有一个非空子节点的节点)，为了删除这个节点而不影响它的子树，需要把它的子节点代替它的位置，然后把它删除。如图2所示，删除节点2时，需要把它的左子节点代替它的位置。情况三，该节点有两个非空子节点。由于情况比较复杂，一般的策略是用它右子树的最小值来代替它，然后把它删除。如图3所示，删除节点2时，在它的右子树中找到最小的节点3，该节点一定为待删除节点的后继。删除节点3(它可能是叶节点或者链节点)，然后把节点2的值改为3。实际上在实现的时候，情况一和情况二是可以一样对待的，因为用叶节点的子节点代替它本身，就是用空节点代替了它，等同于删除。对待情况三除了可以用后继代替本身以外，我们还可以使用它的前驱(左子树的最大值)代替它本身。删除它1267453136754图SEQ图\*ARABIC3牵涉到的查找最小值的问题，章节三.4.(4)有详细讨论。基本方法就是从子树的根节点开始，如果左子节点不为空，那么就访问左子节点，直到左子节点为空，当前节点就是该子树的最小值节点。删除它只需用它的右子节点代替它本身。代码5给出