算法合集之《左偏树的特点及其应用》.ppt

左偏树的特点及其应用,广东省中山市第一中学黄源河,2,左偏树的定义,左偏树(LeftistTree)是一种可并堆(MergeableHeap)，它除了支持优先队列的三个基本操作（插入，删除，取最小节点），还支持一个很特殊的操作合并操作。左偏树是一棵堆有序(HeapOrdered)二叉树。左偏树满足左偏性质(LeftistProperty)。,3,左偏树的定义左偏性质,定义一棵左偏树中的外节点(ExternalNode)为左子树或右子树为空的节点。定义节点i的距离(dist(i)为节点i到它的后代中，最近的外节点所经过的边数。任意节点的左子节点的距离不小于右子节点的距离（左偏性质）。由左偏性质可知，一个节点的距离等于以该节点为根的子树最右路径的长度。,4,左偏树的性质,定理：若一棵左偏树有N个节点，则该左偏树的距离不超过log(N+1)-1。,最右路径:ACG最右路径节点数=3距离=2,8个节点的左偏树的最大距离：log(8+1)-1=2,5,左偏树的操作,左偏树支持下面这些操作：MakeNull初始化一棵空的左偏树Merge合并两棵左偏树Insert插入一个新节点Min取得最小节点DeleteMin删除最小节点Delete删除任意已知节点Decrease减小一个节点的键值,6,左偏树的操作合并,合并操作是递归进行的,合并T1和T2两棵左偏树,先将T1的右子树与T2合并,7,左偏树的操作合并,合并操作是递归进行的,a,L1,R,先将T1的右子树与T2合并,8,左偏树的操作合并,合并操作是递归进行的,交换左右子树并更新根节点距离,合并后的右子树距离可能大于左子树距离,9,左偏树的操作合并,合并操作的代码如下：FunctionMerge(A,B)IfA=NULLThenreturnBIfB=NULLThenreturnAIfkey(B)dist(left(A)Thenswap(left(A),right(A)Ifright(A)=NULLThendist(A)0Elsedist(A)dist(right(A)+1returnAEndFunction,10,左偏树的操作合并,下面是一个合并的例子：,11,左偏树的操作合并,下面是一个合并的例子：,12,左偏树的操作合并,下面是一个合并的例子：,13,左偏树的操作合并,下面是一个合并的例子：,18,NULL,14,左偏树的操作合并,下面是一个合并的例子：,37,7,0,1,?,15,左偏树的操作合并,下面是一个合并的例子：,1,1,2,26,17,37,18,8,7,16,左偏树的操作合并,下面是一个合并的例子：,0,2,?,17,左偏树的操作合并,下面是一个合并的例子：,3,10,2,0,1,18,左偏树的操作合并,合并操作都是一直沿着两棵左偏树的最右路径进行的。一棵N个节点的左偏树，最右路径上最多有log(N+1)个节点。因此，合并操作的时间复杂度为：O(logN1+logN2)=O(logN),19,左偏树的操作插入,插入一个新节点把待插入节点作为一棵单节点左偏树合并两棵左偏树时间复杂度：O(logN),20,左偏树的操作删除,删除最小节点删除根节点合并左右子树时间复杂度：O(logN),21,例题：数字序列,给定一个整数序列a1,a2,an，求一个不下降序列b1b2bn，使得数列ai和bi的各项之差的绝对值之和|a1-b1|+|a2-b2|+|an-bn|最小。数据规模：1n106,0ai2*109,22,假设数列a1,a2,ak的最优解为b1,b2,bk合并bi中相同的项，得到m个区间和数列s1,s2,sm显然，si为数列a中，下标在第i个区间内的各项的中位数。,b,ak+1,加入ak+1后，怎样得到前k+1项的最优解？,例题：数字序列算法分析,23,若ak+1sm，直接令sm+1ak+1，得到前k+1项的最优解；否则，将ak+1并入第m个区间，并更新sm不断检查最后两个区间的解sm-1和sm，若sm-1sm，合并最后两个区间，并令新区间的解为该区间内的中位数。,b,ak+1,sm,sm-1,例题：数字序列算法分析,24,下面考虑数据结构的选取我们需要维护若干个有序集，并能够高效完成下面两个操作：合并两个有序集查询某个有序集的中位数进一步分析，加入一个元素后，发生一连串合并操作，合并后有序集的中位数不会比原来大因此，每个有序集内只保存较小的一半元素，查询中位数操作转化为取最大元素操作。,例题：数字序列算法分析,25,例题：数字序列算法分析,现在，我们需要合并、取最大元素和删除三种操作，而这些都是可并堆的基本操作。下表列出了几种可并堆相应操作的时间复杂度,26,例题：数字序列算法分析,在本题中，合并操作和取最大元素操作少于n次，删除操作不超过n/2次由于合并次数比较多，二叉堆的合并操作太慢了，总时间复杂度也无法令人满意。二项堆和Fibonacci堆某些操作比左偏树快，但对于本题，三者的总时间复杂度均为O(nlogn)二项堆和Fibonacci堆的空间需求比较大，编程实现也远没有左偏