（计算机应用技术专业论文）左倾堆枚举算法的研究.pdf

华东师范人学硕士学位论文左倾堆枚举算法的研究 摘要 枚举有两层含义：一是计数，即计算具有某种特性的所有对象的个数；二是 生成，即产生具有某特性的所有对象。本文主要介绍了二叉树的枚举，最大值堆 的枚举和自己所研究的左倾堆的枚举。 二叉树是一种重要的数据结构。二叉树枚举的研究无论在算法理论上还是在 实际应用中都具有重要的意义。与二叉树枚举计数相关的最有名的就是c a t a l a n 数。目前二叉树的枚举生成主要是基于编码的二叉树生成算法【3 】，这些算法建 立了二叉树集合和编码集合间的一一对应关系，将二叉树的枚举生成问题转化为 编码的枚举生成问题。 最大值堆在结构上是一棵完全二叉树。最大值堆的枚举生成是将数值映射到 结构固定的完全二叉树上。目前最大值堆的枚举生成【1 0 。4 1 大都是基于回溯法，并 采用单个数判断法和层次判断法来减少回溯的次数。 左倾堆是具有堆序性质和左倾性质的特殊二叉堆。它可以作为优先队列的一 种实现方式，跟普通的二叉堆相比，有着更加高效的合并操作【1 6 1 。左倾堆的枚举 对于研究左倾堆的性质、分析其相关算法的平均复杂性有着重要意义，并为左倾 堆的随机生成提供了基础。本文首先根据左倾堆的距离和结点数的关系，用组合 方法推导出了左倾堆枚举计数的递推公式，然后提出了基于构造的左倾堆枚举生 成算法和基于排列的左倾堆枚举生成算法。基于构造的左倾堆的枚举生成算法是 在含1 1 1 个结点的左倾堆中插入一个结点构造所有含1 1 个结点的左倾堆；基于排 列的左倾堆枚举生成算法的依据是本文提出的一个定理，即一个二叉堆的中序序 列能够唯一的确定该二叉堆。该定理确立了一个含n 个结点的二叉堆与一个n 元 排列的一一对应关系。基于排列的左倾堆枚举生成算法通过生成n 元排列，将排 列看成是二叉堆的中序序列，通过中序序列来构造二叉堆，再从二叉堆中筛选出 左倾堆，该算法简化了左倾堆的枚举过程，相对比基于构造的左倾堆的枚举生成 算法，左倾堆的枚举生成效率提高了3 5 以上。同时本文进一步改进了基于排列 的左倾堆枚举生成算法，使得左倾堆的枚举生成效率进一步提高了4 0 左右。 本文最后对三种结构的枚举进行了总结，对左倾堆枚举生成的进一步改进方 法进行了讨论。 关键词：枚举计数生成二叉树最大值堆左倾堆 华东师范大学硕十学位论文左倾堆枚举算法的研究 a bs t r a c t t h e r ea r et w om e a n i n g so fe n u m e r a t i o n o n ei sc o u n t i n g , t h a ti st oc o u n tt h e n u m b e ro ft h eo b j e c t sw i t hs o m ec h a r a c t e r i s t i c s ；t h eo t h e ri sg e n e r a t i n g ，t h a ti st o g e n e r a t ea l lt h eo b j e c t sw i t ht h e s ec h a r a c t e r i s t i c s t h i sp a p e ri sm a i n l yd i s c u s s i n gt h e e n u m e r a t i o n so fb i n a r yt r e e s ，m a xh e a p sa n dl e f t i s th e a p s t h ee n u m e r a t i o no fl e f t i s t h e a p si st h em a j o rp a r to fm yj o b b i n a r yt r e ei sa ni m p o r t a n td a t as t r u c t u r e t h ee n u m e r a t i o no fb i n a r yt r e ei so f g r e a ti n t e r e s tf r o mt h e o r e t i c a la n dp r a c t i c a lp o i n to fv i e w t h em o s tf a m o u sr e s u l t r e l a t e dt ot h ec o u n t i n go fb i n a r yt r e ee n u m e r a t i o ni sc a t a l a nn u m b e r n o w , t h e a l g o r i t h mo fg e n e r a t i n gb i n a r yt r e e s i sm a i n l yb a s e do nc o d i n gm e t h o d s ，w h i c h c o n s t r u c to n et oo n ec o r r e s p o n d e n c eb e t w e e nb i n a r yt r e e sa n dc o d i n g m e a n w h i l e ， t h e yc o n v e r tt h eg e n e r a t i o no fb i n a r yt r e e s t ot h eg e n e r a t i o no fc o d i n g m a xh e a pi ss t r u c t u r a l l yac o m p l e t eb i n a r yt r e e t h eg e n e r a t i o no fm a xh e a pi st o p u tv a l u e st ot h es t r u c t u r eo ff i x e dc o m p l e t eb i n a r yt r e e p r e s e n t l y , t h eg e n e r a t i o no f m a xh e a pi sm o s t l yb a s e do nb a c k t r a c k i n g , w h i c hu s e ss i n g l en u m b e rj u d g ea n d h i e r a r c h yj u d g et or e d u c eb a c k t r a c k i n gt i m e s l e f t i s th e a pi sas p e c i a lb i n a r yh e a pw i t hh e a po r d e ra n dl e f t i s tp r o p e r t y f i r s t l y , t h i sp a p e rd e d u c e dt h er e c u r s i v ef o r m u l ao fl e f t i s th e a pe n u m e r a t i o nn u m b e r , s e c o n d l y , i tb r i n g su pt w oa l g o r i t h m so fg e n e r a t i n ga l l l e f t i s th e a p s o n eu s e sm e t h o do f c o n s t r u c t i o n ，t h eo t h e ri st h ea l g o r i t h mb a s e dp e r m u t a t i o n t h ef i r s ta l g o r i t h mi s g e n e r a t i n ga l ll e f t i s th e a p sw i t hn n o d e sb yi n s e r t i n go n en o d et ot h el e f t i s th e a p sw i m n - 1n o d e s t h es e c o n da l g o r i t h mi sa c c o r d i n gt ot h et h e o r e mt h a tah e a p sm i d o r d e r s e q u e n c e c a nc o n s t r u c tt h eb i n a r yh e a pu n i q u e l y ,w h i c hb u i l d so n et oo n e c o r r e s p o n d e n c eb e t w e e nab i n a r yh e a pw i t hnn o d e sa n dap e r m u t a t i o nw i t hn e l e m e n t s t h ea l g o r i t h mb a s e do np e r m u t a t i o ng e n e r a t e sap e r m u t a t i o nw i mn e l e m e n t sa n dc o n s i d e r st h i sp e r m u t a t i o na sam i d o r d e rs e q u e n c ea n dt h e nu s e st h i s m i d - o r d e rs e q u e n c ec o n s t r u c tt h eb i n a r yh e a pa n d j u d g e w h e t h e rt h eb i n a r yh e a pi sa l e f t i s th e a p w h e na l lp e r m u t a t i o n sw i t hne l e m e n t sg e n e r a t e d ，a l lt h el e f t i s th e a p si s g e n e r a t e d t h es e c o n da l g o r i t h mi n c r e a s e st h ee f f i c i e n c yb y3 5 c o m p a r i n gw i t ht h e f i r s to n e f i n a l l y , t h ea l g o r i t h mb a s e do np e r m u t a t i o ni si m p r o v e da n dt h ee f f i c i e n c yi s i i 华东师范大学硕十学位论文 左倾堆枚举算法的研究 r a i s e db y4 0 f u r t h e r t h i sa r t i c l ef i n a l l yc o m p a r e st h et h r e es t r u c t u r e s e n u m e r a t i o na n dg e t sa s u m m a r i z a t i o n , m a k i n gt h ep r o s p e c tf o ri m p r o v i n gm e t h o do fg e n e r a t i n gl e f t i s th e a p s k e yw o r d s ：e n u m e r a t i o n ，c o u n t i n g ，g e n e r a t i o n , b i n a r yt r e e ，m a xh e a p ，l e f t i s t h e a p i i i 华东师范大学硕士学位论文 左倾堆枚举算法的研究 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。据我所知，除文中已经注明引用的内容外，本论文不包含其它个人已 经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已 在文中作了明确说明并表示谢意。 作者签名：盈递! ! 学位论文授权使用声明 日期：三竺z ：z ：2 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名：霹害l 踟 导师签名： 轧， 华东师范大学硕上学位论文左倾堆枚举算法的研究 o r i g i n a l i t yn o t i c e i np r e s e n t i n gt h i s t h e s i s i n p a r t i a lf u l f f i l m e n to ft h er e q u i r e m e n t s f o rt h e m a s t e r sd e g r e ea te a s tc h i n an o r m a lu n i v e r s i t y , 1w a r r a n tt h a tt h i st h e s i si s o r i g i n a la n da n yo ft h et e c h n i q u e sp r e s e n t e di nt h et h e s i sh a v eb e e nf i g u r e do u t b ym e a n yo ft h er e f e r e n c e st ot h ec o p y r i g h t , t r a d e m a r k , p a t e n t , s t a t u t o r yr i g h t , o rp r o p r i e t yr i g h to fo t h e r sh a v eb e e ne x p l i c i t l ya c k n o w l e d g e da n di n c l u d e di n t h er e f e r e n c e ss e c t i o na tt h ee n do ft h i st h e s i s 。s i g n a t u 联堑狃l d a t e ： c o p y r i g h tn o t i c e ih e r e i na g r e et h a tt h el i b r a r yo fe c n us h a l lm a k ei t sc o p i e sf r e e l ya v a i l a b l ef o r i n s p e c t i o n if u r t h e ra g r e et h a te x t e n s i v ec o p y i n go ft h et h e s i si sa l l o w a b l eo n l y f o rs c h o l a r l yp u r p o s e s ，i np a r t i c u l a r , s t o r i n gt h ec o n t e n to ft h i st h e s i si n t o r e l e v a n td a t a b a s e s ，a sw e l la sc o m p i l i n ga n dp u b l i s h i n gt h et i t l ea n da b s t r a c to f t h i st h e s i s ，c o n s i s t e n t 砌t h “f a i ru s e a sp r e s c r i b e di nt h ec o p y r i g h tl a wo ft h e p e o p l e sr e p u b l i co fc h i n a i s i g n a t u r e ：二奎查l 盈! ld a t e ：z 垒：三21 ：2 华东师范大学硕士学位论文左倾堆枚举算法的研究 第一章绪论 1 1 研究的背景和意义 枚举是世界上最古老而简单的研究方法之一，它往往同大量的观察，总结， 列举密切相关，但同样它也是一个时间周期很长的研究方法。计算机的出现，使 得处理大量数据变得更加迅速，这无疑大大促进了枚举方法的应用发展，比如化 学元素的构成，基因研究，色谱光谱分析，味觉构成分析，组合排列理论研究等 枚举都是极为重要的方法。 树作为计算机领域中最重要的非线性数据结构，大量应用于数据存储、组织， 决策分析，语言分析等领域。由于树的应用领域极广，针对各种不同应用的树形 结构应运而生，形成了各种树族。同时，多种树族的形成为树结构带来了复杂性。 为了研究树形结构的特性和共性，我们可能就需要计算机帮我们处理大量树的比 较包括树族内的树的比较和树族间的树的比较。于是作为计算机分析树形结 构最为直接的方法，枚举在树的研究当中发挥了重要作用。 树的枚举一般包含两部分内容：一是获得符合某一特性的树的总数目，即获 得某一树族的大小，使我们能够对研究对象的规模有一个整体上的认识；二是生 成某树族的所有对象或者随机生成该树族中的一个对象。 树的枚举已经取得很多重要的成果，在计数方面像卡特兰( c a t a l a n ) 数，波利 亚( p o l y a ) 计数定理，生成函数等等都与树枚举计数相关，而二叉树的枚举生 成极大的促进了与二叉树相关的排序和编码理论的发展。另外在数学领域，树的 枚举已经成为了图论的一个重要研究分支。 堆作为特殊的树型结构，父子结点有着特定的数值特性，因此堆枚举中结点 的数值大小与堆结构之间的映射成为主要的考虑内容。目前已有多篇文献对最大 值堆的枚举计数和生成进行了深入研究。 2 0 0 1 年，文献 1 0 】发现了最大值堆的一种层次性质，为层次判断法提供了基 础。在这一性质的基础上，文献 1 l 】提出了一种生成所有最大值堆的枚举实用算 法。2 0 0 2 年文献【1 2 】提出了计算任意最大值堆的枚举总数目的实用算法，并推导 了满堆的枚举计数公式，提出了求任意最大值堆的枚举计数的算法。2 0 0 5 年文 献【1 3 】得出了最大值堆的枚举计数公式。2 0 0 6 年文献【1 4 】提出了最大值堆的子树 生成和多层子树的生成算法，提高了最大值堆的生成效率。 华东师范大学硕士学位论文 左倾堆枚举算法的研究 左倾堆是特殊的堆，作为可合并堆的一种，是优先队列的一种重要实现。由 于结构的左倾性，其结构足p - - 叉树更加接近，其枚举必须同时考虑数值和结构的 结合特性，使得结点数值与树结构之间的映射难度更大，因此枚举的难度比最大 值堆要大。本文所研究的主要工作也就是找到一种合适方法来枚举生成左倾堆和 找到一个合理的计数方式。 1 2 本文的主要工作 本文首先介绍了二叉树枚举和最大值堆枚举的相关知识，在这些知识的基础 上本文着重研究了左倾堆的枚举，包括左倾堆的枚举计数和左倾堆的枚举生成。 关于左倾堆的枚举计数，本文通过组合方法结合左倾堆的性质定理得出了求 左倾堆枚举计数的递推公式，并给出了算法实现。 关于左倾堆的枚举生成，本文提出了两个生成左倾堆的算法：一是基于构造 的左倾堆的枚举生成算法；一是基于排列的左倾堆枚举生成算法。基于构造的左 倾堆的枚举生成算法是通过插入结点的方式从含一个结点的左倾堆逐步生成含n 个结点的所有左倾堆。基于排列枚举生成算法的依据是本文提出一个定理，即二 叉堆的中序序列能够唯一确定一个二叉堆。该算法通过生成全排列序列，将这些 序列看成是二叉堆的中序序列，根据中序序列能够唯一构造一个二叉堆的定理构 造相应的二叉堆，然后判断生成的二叉堆是否为左倾堆，将所有的序列进行判断 便可以得到所有的左倾堆。在基于排列的算法基础上本文对中序序列和左倾堆的 关系进行了研究，排除了一些序列生成左倾堆的可能性，进一步改进了基于排列 的左倾堆枚举生成算法，使得左倾堆的枚举生成的效率提高了4 0 左右。 1 3 本文的内容安排 本文其余章节内容安排如下： 第二章介绍了二叉树的枚举，包括二叉树的枚举计数，以及二叉树编码的 相关理论。 第三章重点介绍了最大值堆的枚举计数和生成的相关算法。 第四章推导了左倾堆的枚举计数的递推公式，提出了两个左倾堆枚举生成 的算法。 第五章对本文的研究进行了总结 2 华东师范大学硕十学位论文左倾堆枚举算法的研究 第二章二叉树的枚举 本章首先介绍了二叉树的相关概念，然后介绍了二又树的枚举计数，接着讨 论了二叉树的排序，以及二叉树的排名和解析排名，最后介绍了主要的两种编码 模式下的二叉树枚举生成算法。 2 1 二叉树的相关概念和符号约定 定义2 1 二叉树( b i n a r yt r e e ) 是一个有限的结点的集合t ，这个集合或者 为空；或者有一个根结点r 及表示根结点的左、右子树的两个互不相交的结点集 合所组成，而根结点的左、右子树也都是二叉树。我们称用空集表示的二叉树为 空的二叉树。空的二叉树不含有结点。 二叉树是非常有用的数据结构，它具有统一的结构、有多种扫描算法可供使 用并可提供对元素的高效访问，故广泛用于表示和维护各种类型的数据。假设t 是一棵二叉树，并且t 不为空，我们将左子树表示为l ( t ) ，右子树表示为r ( t ) ； 对于二叉树t 中的一个结点u ，我们用“u ) 表示结点u 的左子树，r ( u ) 表示u 的右 子树。二叉树t 的结点数目，也称为二叉树的大小，表示为lti 2 1 ，如果t 为 空集，那么itl = o 。 图2 1 二叉树 f i g 2 - lb i n a r yt r e e 定义2 2 结点次别1 1 ( d e g r e e ) 结点次数是指一个结点的非空子树的个数。0 次结点又叫叶子结点。 定义2 3 从父结点移动到孩子结点和其他后代所经路线叫“路径”( p a t h ) 。 从根结点到结点之间的路径可以提供一种被称作结点的“层次”( l e v e l ) 这样的 度量。结点的层次等于从根结点到结点之间的路径的长度。根的层次为o ，根结点 的每个孩子的层次为l ，下一层结点的层次为2 ，以此类推。二叉树的“深度” ( d e p t h ) 是树中所有结点层次中的最大值。深度的概念可以用路径来描述。二 3 华东师范大学硕士学位论文 左倾堆枚举算法的研究 叉树的深度是从根到结点之间最长路径的长度。如图2 2 中，树的深度为3 。 一层次0 层次1 层次2 层次3 图2 - 2 树的结点层次 f i g 2 2t h el e v e lo ft r e en o d e s 在任一层次n ，二叉树可能包含1 到2 n 个结点。每一层的结点数决定了二叉 树的密度。直观上说，密度是相对于树的深度而言对树的大小( 结点数) 的一种 度量。当一棵二叉树只有一个叶子结点，每个非叶子结点只有一个孩子时，其树 被称为“退化”二叉树，一棵退化二叉树等价于一个链表。 密度较大的二叉树在数据结构上很重要，因为它们在接近二叉树的顶部离根 较近的地方集中了较大比例的元素数目。一棵致密的二叉树使得我们可以存储大 量数据并对这些项进行有效的访问。快速访问是用来存放数据的关键。 2 2 二叉树的枚举计数 二叉树的枚举计数是指计算具有n 个结点的结构不同的二叉树的数目。设具 有n 个结点的结构不同的二叉树的数目为b n ，由于二叉树是递归定义的，所以很 自然可以得到关于b n 的递推关系： b n = b o b n q + b lb l 佗+ + b m l b b 一棵具有n 1 个结点的二叉树可以看成是有一个根结点，一棵具有i 个结点的左 子树和一棵具有n i 1 个结点的右子树所组成。 b n ) 的生成函数为： b(x)=0nxn=_1-ifl-4xn=o 厶a 它满足方程b ( x ) = l + x b ( x ) 2 。求解上述关系可以得到： 4 公式( 2 1 ) 华东师范大学硕士学位论文 左倾堆枚举算法的研究 it , o = 1 卜善n - 1 。= 鬲1 错= 六捌 矧2 二叉树计数的另一种考虑角度，由于二叉树结点的前序序列和中序序列能够 唯一确定一棵二叉树，假设二叉树的n 个结点从1 到n 加以编号，且其先序序列 为1 ，2 ，n 。那么n 个结点的不同形态的二叉树的数目就等同于先序序列为 1 ，2 ，n 的二叉树所能够得到的中序序列的数目。可以得到： 咒一嚷1 = 鬲1 巴 公式( 2 3 ) i 音 就是有名的c a t a l a i l 数。c a t a l a n 数不仅具有独立的数学意义，还作 为组合对象的计数结果被应用于组合数学领域的研究【2 1 。 在得到了二叉树的计数后，我们可以容易得到n 个结点的有序树的计数，通 过克努特( k n u t h ) 变换能够实现从有序树到二叉树的变换，具体变换方法参考文 献【3 】。克努特变换揭示了有序树m - x 树之间的本质联系，即1 1 个结点的有序 树与n 1 个结点的二叉树存在一一对应关系。所以具有n 个结点的有序树的数目 t n = b n - 1 。 2 3 二叉树的排序 为了生成n 个结点的所有形态的二叉树，p a l l o 和r a c c a 在1 9 8 5 年提出了二 叉树的a 顺序( a o r d e r ) 和b 顺序( b o r d e r ) 。这里我们用r t 表示二叉树根结 点次数。 定义2 4a 顺序【3 】两棵- - y 树t 和s 按a 顺序满足t s 当且仅当： 1 ) ltl isi ；或者 2 ) lti = lsi 并且t l s l ；或者 3 ) itl = isl ，t l - s l 并且t r s r 。 a 顺序又被称作自然顺序( n a t u r a lo r d e r ) 。m c e r 将自然顺序的定义进一步 扩展到了k 叉( 有序) 树，并提出了局部顺序( l o c a lo r d e r ) 的概念。 5 华东师范大学硕士学位论文 左倾堆枚举算法的研究 假设t ( k ，n ) 表示含有r 1 个结点的k 叉树的集合。如果t t ( k ，n ) ，则用t i 表 示k 叉树t 的第i 棵子树。图2 - 3 给出了树的集合t ( 2 ，4 ) _ 1 2 所有树的自然顺序 关系。 定义2 5 ( n a t u r a lo r d e r ) 4 1 已知集合t ( k ，n ) 内的两棵k 叉树t ，s ，定义偏 序关系t s 为： 1 ) iti lsf ；或者 2 ) iti = isi ，并且存在一个i ，1 i 5 血有 a ) t j = s j ，其中1 匀 i ；且 b ) t i 入之夕憎抄5 ：父 图2 3t ( 2 ，4 ) 上的自然顺序 f i g 2 - 3n a t u r a lo r d e ro ft ( 2 ，4 ) 定义2 6 ( l o c a lo r d e r ) 【4 】已知集合t ( k ，n ) l - k 叉树t , s ，定义t s 为： i ) t 为空树，而s 非空；或者 2 ) t 、s 都不为空，且存在一个i ，l _ i s k 有 a ) t j = s j ，其中1 匀；且 b ) t i 入之夕 令5 ： 图2 4t ( 2 ，4 ) 上的局部顺序 f i g 2 4l o c a lo r d e ro f t ( 2 ，4 ) 6 华东师范大学硕士学位论文左倾堆枚举算法的研究 自然顺序的特点是将二叉树的结点个数考虑在内，对参与排序的树结构有一 个全局的了解，使用自然顺序设计的生成树算法总是将结点个数小的二叉树排在 前面。与自然顺序不同的是，局部顺序只注重各个树之间的局部差异，差异越小 的二叉树排名越相近，可见生成的树不一定是按照结点个数排序的。 假设两棵树t 、s 属于同一树族集合，按照自然顺序比较的结果是：t s ， 但按照局部顺序却可能是：s t 。例如图2 5 种的两棵二叉树在图2 3 和图2 4 中的顺序就不同。 9 1 0 ( a ) 自然顺序 91 l ( b ) 局部顺序 图2 - 5 自然顺序和局部顺序的比较 f i g 2 5c o n t r a s tb e t w e e nn a t u r a lo r d e ra n dl o c a lo r d e r 定义2 。7b 顺序【3 1 两棵- - y 树t 和s 按a 顺序满足t s 当且仅当： 1 ) r r r s ；或者 2 ) r t = - r s ，并且t l 之夕k 以憎” l2 3 4 56 7891 0“1 21 31 4 图2 - 6 t ( 2 ，4 ) 上的b 顺序 f i g 2 - 6b o r d e ro ft ( 2 ，4 ) 7 华东师范大学硕士学位论文左倾堆枚举算法的研究 跟局部顺序相同的是b 顺序也不关心二叉树的结点个数，但不同的b 顺序 将结点次数作为衡量大小的标准。 2 4 二叉树的排名和解析排名 通过二叉树枚举计数可以得到结点个数为n 的不同形态的二叉树的个数为， 即集合b ( n ) 的大小为c n ，c n 为c a t a l a n 数。再由2 3 节二叉树的排序，我们可以 确定b ( n ) 和区间【1 ，c n 】上的一一映射。 定义2 8 【4 】设1 1 个结点的二叉树的集合为b ( n ) ，i b ( n ) | _ c n ，如果b ( n ) 上的偏 序关系“ ，使得t 1 t 2 t c n 成立，则定义函数r a n k ( t i ) = i ( 1 i 0 其中g j ，n _ c j 半c n - j 1 表示左子树含有j 个结点，总结点数目为n 的二叉树的数目， 即： g = q 。 ( 令g 0 ，o = 1 ) j = o 定理2 1 已知n 个结点的二叉树t 1 ，t 2 满足定义2 5 的自然顺序t l t 2 ，当 且仅当r a n k ( t 0 r a n k ( t 2 ) 。 r a n k ( t ) 函数的计算需要常数时间获得各子树的大小，然后对每个结点递归 调用r a n k ( t ) ，所以时间复杂度为o ( n ) 。 下面分析逆函数r a n k d ( i ，n ) ，即要根据排名i 构造对应的二叉树t i 。 已知g j ，n - c j 宰c 叫1 表示左子树个数含有j 个结点，总结点数目为n 的二叉树 的数目。首先，假设t i 的左子树结点数目为k ，则： k = m a x js 加= g ，且s j n i ) 脚s j 其中，s j ，n 是可以预计算的信息，可以通过二分查找树查找到所需要的值， 华东师范人学硕士学位论文左倾堆枚举算法的研究 时间复杂度为o ( 1 0 9 k ) s o ( 1 0 舯) 2 5 二叉树的枚举生成算法 树的存储结构主要是通过指针来实现的，因此最直接容易想到的是基于结构 操作的枚举生成，这涉及到大量的指针操作。但是，结果证明，使用树的指针结 构设计生成算法并不是一个好的选择。因此在二叉树的各种排序的基础上，基于 编码的二叉树枚举生成算法被提出并得到发展，避免了指针的操作，降低了时间 和空间的开销。 目前主要有四种编码模式下的二叉树生成算法，即基于树排列( t r e e p e r m u t a t i o n s ) 的编码生成算法，基于旋转( r o t a t i o n s ) 的编码生成算法，广义模 式下( g e n e r a ls c h e m e ) 的编码生成算法，基于文法( c o n t e x t f r e eg r a m m a r ) 的 编码生成算法。这些算法都是先建立二叉树集合和编码集合之间的一一映射关 系，然后对二叉树的枚举生成转化为编码的枚举生成。 由于二叉树枚举并非本文的主要工作，故简单介绍了树排列编码生成算法， 其他算法参考文献【4 】 2 5 1 二叉树的编码过程 ( x t ，x 2 ，x n ) 图2 7 二叉树的编码过程 f i 醇一7c o d i n ga n dd e c o d i n g 9 华东师范大学硕士学位论文左倾堆枚举算法的研究 图2 7 给出了二叉树的编码过程示意图，借助于一定的编码方法，我们就可 以得到一棵二叉树对应的编码，一棵二叉树的编码方式有多种，但并非所有的编 码都是有效的，有效的( f e a s i b l e ) 编码【4 】需要满足下面两个条件： 1 ) 编码与待生成的二叉树是一一对应的，即一棵二叉树对应一个唯一的编 码，反之亦然。 2 ) 必须有一个有效的编码算法，使得给定一棵二叉树可以方便的获得对应 的编码，同时也要有一个有效的解码算法使得给定一个有效的编码可以方便的构 造对应的二叉树。 2 5 2 基于树排列的编码生成算法 我们可以用l ，2 ，- - - - n 的某个排列来表示一棵具有n 个结点的二叉树。 我们用p 来表示该一个给定的排列，用t 来表示对应的二叉树。t 可以通过p 来 构造生成。如果p 为空，那么t 为空二叉树；如果p 不为空，那么二叉树t 的 根被标记成为p l 。p7 表示p 中小于p l 的元素构成的排列，p ”表示p 中大于p l 的元素构成的排列。通过递归的方式，用p7 来构造二叉树的左子树，用p ”构 造二叉树的右子树。如果能建立一个含1 1 _ 个结点的二叉树和一个n 元排列的一一 对应关系，那么该n 元排列称之为树排列【5 】o 对于一个树排列p = p lp 7 p ”，有这样的性质p7 和p ”本身都是一个树排列。 例如当一个树排列p = 6 2 1 3 4 5 8 7 9 时，p7 = 2 1 3 4 5 且p ”= 8 7 9 。 对于给定一个树排列，我们很容易通过递归的方式得到一棵二叉树。对于t 的任意一棵子树s ，包含t 本身，其左子树l ( s ) 的任意元素x ，满足x r o o t ( s ) 。因此对于树排列p = 6 2 1 3 4 5 8 7 9 ，其对 应的二叉树如图2 8 所示： l o 华东师范大学硕十学位论文 左倾堆枚举算法的研究 图2 - 8 树排列和其对应的二叉树 f i g2 - 8t r e ep e r m u t a t i o na n db i n a r yt r e e 而且，给定一棵按照中序遍历的对二叉树的结点从1 开始标号的二叉树， 通过前序遍历也可以很容易的得到其树排列。 这样就建立了n 元排列与二叉树之间的一一对应关系。例如图2 - 9 中的二叉 树对应的树排列为( 6 ，4 ，2 ，l ，3 ，5 ，1 0 ，8 ，7 ，9 ) 。 假如已知二叉树上以每个结点u 为根的子树的大小s i z e ( u ) ，只用一次遍历就 可以获得树排列。假设结点u i 所对应的树排列编码的整数是x i ，则： f s i z e ( l ( u ，) ) + 1u i 是根节点 x i = p i - s i z e ( r ( u 一l “f 是左孩子 lp f + s i z e ( l ( u f ) ) + 1u i 是右孩子 u 6 图2 - 9 按中序遍历标记过的二叉树 f i g 2 - 9b i n a r yt r e em a r k e db ym i d - o r d e rt r a v e r s i n g 其中p i 是u i 的父亲结点对应的整数。例如图2 - 9 中的结点u t x c 应的编码整数x 7 华东师范大学硕：t 学位论文左倾堆枚举算法的研究 是1 0 ，因为u 7 是根结点的右孩子，所以：x 7 = p 7 + s i z e ( l ( u 7 ) ) + l = 1 0 。 定理2 2 【5 】一个整数序列p = ( p l ，p 2 ，p n ) 是一个排列，当且仅当p 中不存在 这样的子排列p i p j p k ，其中p k p i y 成立， x y 取值为1 ；否则，取值为o 。换句话说， b i 的值是排列p 中数字i 的左边并且比i 大的数字的个数。 表 定理2 3 【5 】一个整数序列p = ( p 1 ，p 2 ，p n ) 是- - 个树排列，当且仅当p 的反演 b 满足：b i - b i + l 2 ( 1 i n ) 。 定理2 4 【5 1 已知n 个结点的二叉树t l ，t 2 ，对应的树排列p l 、p 2 ；t l 、1 2 满足定义2 4 中的自然顺序t l t 2 ，当且仅当序列p l 在字典顺序上优先先于p 2 ， 即：r a n k ( t 0 o ，且剩下的n 个结点都靠左的排列在第i 层上，则称t 是一棵完全 二叉树。 3 ) 若r 0 ，且剩下的r 个结点随意分布在第i 层上，则称t 是一棵丰满树。 定义3 3 - x 堆( b i n a r yh e a p ) 二叉堆在结构上是一棵完全二叉树，并满 足堆序。 本章中的所称的最大值堆如果没有特别说明指的就是最大值二叉堆。 定义3 4 隐式二叉堆( i m p l i c i tb i n a r yh e a p )该数据结构是1 9 6 4 年 j w w i l l i a m s 在建立堆排序时提出的。它是二叉堆的一种数组实现方式，见图3 1 。 1 3 华东师范大学硕十学位论文左倾堆枚举算法的研究 l 551 1348 ( a ) 二叉堆( b ) 二叉堆的数组表示 图3 1 隐式二叉堆 f i g 3 - 1i m p l i c i tb i n a r yh e a p 如果用数组a 【n 】( a o ，a 【1 】，a n - 1 】) 表示n 个结点的最大值堆，那么数组 a n 】中的元素具有如下性质： 1 ) 若2 i + l n ，则a 【i a 2 i + 1 】；并且 2 ) 若2 i + 2 n ，则a i a 2 i + 2 】 定义3 5 满堆当一个最大值堆是满二叉树时，称为满堆。根据堆的定义可 以知道满堆的左右子树均是满堆。 定理3 1 设一个满堆的大小为n ，这里我们重新规定根结点的层次( l e v e l ) 为l ，结点的最大层次为k ，那么n = 2 k 1 ，即k = l o g a ( n + 1 ) 。 定理3 2 满堆的第r 层上结点总数为2 ；以满堆第r 层的结点为根结点的 子树( 子树不为空) 也是满堆，该堆的大小是2 k - 忖l _ 1 。 特别的，当r = l 时，r 层只有根结点一个结点。以根结点为根的满堆大小为 2 k 1 ；当r = k 时，r 层上共有2 k - 1 个结点。 根据上述分析，以及完全二叉树的性质不难得出定理3 3 。 定理3 3 堆的左右子树分别记作h l 和h r ，子树的大小分别记作s l 和s r ，那 么其中至少有一个是满堆。如果h l 是满堆，那么k ( s l 2 ) j s 匹s l ；如果h r 是满 堆，那么s 匹s & s r + l 。 值得注意的是文献【4 】中描述该定理时不等式为s 匹s & s r ，这个不等式是有 1 4 华东师范大学硕士学位论文左倾堆枚举算法的研究 误的，很容易证明。对于h r 是满堆的情况，这里假设h r 的最大层次为m ，h l 有两种情况，或者h l 的最大层次为m ，或者h l 的最大层次为m + l ，对于第一 种情况s r = s l = 2 m - 1 ，对于第二种情况s l 的最大值是h l 为满堆的情况，此时 s l = 2 r e + l _ 1 ，那么2 s r = 2 m + 1 - 2 ，很显然s l s 2 s r 并不成立，应为s l # _ 2 s r + i 。 定理3 4 最大值堆h ( 由键值为1 ，2 ，n 的n 个数构成的最大值堆) 中 的元素h i 】，必须满足如下不等式：s i _ h i 】匀- l o g a i ，其中s i 是以i 为根结点的子 树的大小。 证明：根据最大值堆的定义，h i 】一定是以i 为根结点的子树的最大值，而 该子树的结点数为s i ，所以可以证明h i 2 s i ； 我们已经知道，当i = l 时，根结点处的数值h 1 - - n l 0 9 2 1 - - m 假设对于k = i 2 ， 已经满足h 【k 鱼1 0 9 e k ，这里k 是i 的父亲结点，根据最大值堆的定义得出： h