《左偏树的特点及其应用》由会员分享，可在线阅读，更多相关《左偏树的特点及其应用（21页珍藏版）》请在金锄头文库上搜索。
1、左偏树的特点及其应用广东省中山市第一中学黄源河【摘要】本文较详细地介绍了左偏树的特点以及它的各种操作。第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。【关键字】左偏树可并堆优先队列【目录】一、引言2二、左偏树的定义和性质22.1优先队列，可并堆22.1.1优先队列的定义22.1.2可并堆的定义22.2左偏树的定义32.3左偏树的性质4三、左偏树的操作53.1左偏
2、树的合并53.2插入新节点73.3删除最小节点83.4左偏树的构建83.5删除任意已知节点93.6小结12四、左偏树的应用134.1例数字序列(Baltic2004)13五、左偏树与各种可并堆的比较155.1左偏树的变种斜堆155.2左偏树与二叉堆的比较165.3左偏树与其他可并堆的比较16六、总结18【正文】亠、引言优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。】、左
3、偏树的定义和性质在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。2.1优先队列，可并堆2.1.1优先队列的定义优先队列(PriorityQueue是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum)和删除最小节点(Delete-Min)。2.1.2可并堆的定义可并堆(MergeableHeap
4、)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert,Minimum,Delete-Min)，还支持一个额外的操作合并操作：HMerge(H1,H2)Merge()构造并返回一个包含H1和H2所有元素的新堆H。前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n),用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(LeftistTree)、二项堆(BinomialHeap)和Fibonacci堆(FibonacciHeap)都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。2.2左偏树的定义左偏树(Le
5、ftistTree)是一种可并堆的实现。左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针(left,right)夕卜，还有两个属性：键值和距离(dist)。键值上面已经说过，是用于比较节点的大小。距离则是如下定义的：节点i称为外节点(externalnode)，当且仅当节点i的左子树或右子树为空(left(i)=NULL或right(i)=NULL)；节点i的距离(dist(i)是节点i到它的后代中，最近的外节点所经过的边数。特别的，如果节点i本身是外节点，则它的距离为0;而空节点的距离规定为-1(dist(NULL)=-1)。在本文中，有时也提到一棵左偏树的距离，这指的是该
6、树根节点的距离。左偏树满足下面两条基本性质:性质1节点的键值小于或等于它的左右子节点的键值。即key(i)詠ey(parent(i)这条性质又叫堆性质。符合该性质的树是堆有序的(Heap-Ordered)。有了性质1，我们可以知道左偏树的根节点是整棵树的最小节点，于是我们可以在O(1)的时间内完成取最小节点操作。性质2节点的左子节点的距离不小于右子节点的距离。即dist(left(i)dist(right(i)这条性质称为左偏性质。性质2是为了使我们可以以更小的代价在优先队列的其它两个基本操作(插入节点、删除最小节点)进行后维持堆性质。在后面我们就会看到它的作用。这两条性质是对每一个节点而言的
7、，因此可以简单地从中得出，左偏树的左右子树都是左偏树。由这两条性质，我们可以得出左偏树的定义：左偏树是具有左偏性质的堆有序二叉树。下图是一棵左偏树:distkey2.618243733182.3左偏树的性质在前面一节中，本文已经介绍了左偏树的两个基本性质，下面本文将介绍左偏树的另外两个性质。我们知道，一个节点必须经由它的子节点才能到达外节点。由于性质2,个节点的距离实际上就是这个节点一直沿它的右边到达一个外节点所经过的边数，也就是说，我们有性质3节点的距离等于它的右子节点的距离加1。即dist(i)=dist(right(i)+1外节点的距离为0，由于性质2，它的右子节点必为空节点。为了满足性
8、质3，故前面规定空节点的距离为-1。我们的印象中，平衡树是具有非常小的深度的，这也意味着到达任何一个节点所经过的边数很少。左偏树并不是为了快速访问所有的节点而设计的，它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。从图中我们可以看到它并不平衡,由于性质2的缘故，它的结构偏向左侧，不过距离的概念和树的深度并不同，左偏树并不意味着左子树的节点数或是深度一定大于右子树。下面我们来讨论左偏树的距离和节点数的关系。引理1若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。证明：由性质2可知，当且仅当对于一棵左偏树中的每个节点i，都有dist(left(i)=dist(right(i)时
9、，该左偏树的节点数最少。显然具有这样性质的二叉树是完全二叉树。定理1若一棵左偏树的距离为k，则这棵左偏树至少有2k+1-1个节点。证明：由引理1可知，当这样的左偏树节点数最少的时候，是一棵完全二叉树。距离为k的完全二叉树高度也为k，节点数为2k+1-1，所以距离为k的左偏树至少有2k+1-1个节点。作为定理1的推论，我们有:性质4一棵N个节点的左偏树距离最多为Llog(N+1)-1。证明：设一棵N个节点的左偏树距离为k,由定理1可知，N2k+1-1，因此kdist(right(A)，交换left(A)和right(A)最后，由于right(A)的距离可能发生改变，我们必须更新A的距离：dist
10、(A)dist(right(A)+1不难验证，经这样合并后的树C符合性质1和性质2,因此是一棵左偏树至此左偏树的合并就完成了。下图是一个合并过程的示例:合并流程我们可以用下面的代码描述左偏树的合并过程:FunctionMerge(A,B)IfA=NULLThenreturnBIfB=NULLThenreturnAIfkey(B)dist(left(A)Thenswap(left(A),right(A)Ifright(A)=NULLThendist(A)J0Elsedist(A)Jdist(right(A)+1returnAEndFunction下面我们来分析合并操作的时间复杂度。从上面的过程可
11、以看出，每一次递归合并的开始，都需要分解其中一棵树，总是把分解出的右子树参加下一步的合并。根据性质3,棵树的距离决定于其右子树的距离，而右子树的距离在每次分解中递减，因此每棵树A或B被分解的次数分别不会超过它们各自的距离。根据性质4,分解的次数不会超过lllog(N1+1)+og(N2+1)-2,其中N和N2分别为左偏树A和B的节点个数。因此合并操作最坏情况下的时间复杂度为0(og(N1+1)+og(N2+1)-2)=O(logN1+logN2)。3.2插入新节点A单节点的树一定是左偏树，因此向左偏树插入一个节点可以看作是对两棵左偏树的合并。下面是插入新节点的代码：ProcedureInser
12、t(x,A)BJMakeIntoTree(x)AJMerge(A,B)EndProcedure由于合并的其中一棵树只有一个节点，因此插入新节点操作的时间复杂度是O(logn)。3.3删除最小节点由性质1,我们知道，左偏树的根节点是最小节点。在删除根节点后，剩下的两棵子树都是左偏树，需要把他们合并。删除最小节点操作的代码也非常简单:FunctionDeleteMin(A)tJkey(root(A)AJMerge(left(A),right(A)returntEndFunction由于删除最小节点后只需进行一次合并，因此删除最小节点的时间复杂度也为O(logn)。3.4左偏树的构建将n个节点构建成
13、一棵左偏树，这也是一个常用的操作。算法一暴力算法逐个节点插入，时间复杂度为O(nlogn)。算法二仿照二叉堆的构建算法，我们可以得到下面这种算法：将n个节点(每个节点作为一棵左偏树)放入先进先出队列。不断地从队首取出两棵左偏树，将它们合并之后加入队尾。当队列中只剩下一棵左偏树时，算法结束。55构建流程F面分析算法二的时间复杂度。假设n=2k,则:前-次和并的是两棵只有1个节点的左偏树。2接下来的-次合并的是两棵有2个节点的左偏树。4接下来的-次合并的是两棵有4个节点的左偏树。8JJ接下来的斗次合并的是两棵有2i-1个节点的左偏树。2合并两棵2个节点的左偏树时间复杂度为O(i),因此算法二的总时间复杂nnn/ik2度为：一*0(1)*0(2)*0(3)儿-0(n*、一r)=0(n*(2厂)=0(n)。248二223.5删除任意已知节点接下来是关于删除任意已知节点的操作。之所以强调“已知”，是因为这里所说的任意节点并不是根据它的键值找出来的，左偏树本身除了可以迅速找到最小节点外，不能有效的搜索指定键值的节点。故此，我们不能要求：请删除所有键值为100的节点。前面说过，优先队列是一种容器。对于通常的容器来说，一旦节点被放进去以后，容器就完全拥有了这个节点，每个容器中的节点具有唯一的对象掌握它的拥有权(ownership)。对于这种容器的应用，优先队列只能删除最小节点，
