英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
树的计数应用
Nachum Dershowitz*
Department of Computer Science
University of Illinois
Urbana, Illinois 61801
U.S.A.
Shmuel Zaks
Department of Computer Science
Technion
Haifa 32000
Israel
- 介绍
在这篇论文里我们认为是有n条边的未标记的树，并用组合证明几个关于的计算公式。尤其定义这个封闭的表达式为（1）中的树的个数有个子叶，个一元结点，hellip;，个d个子树的结点，并不限制多于d个子树的结点，（2）中结点的个数为第层d个子树。有几个统计学结果都来源于这些定义。
我们用来证明我们结果的组合工具包括有序树中的一一对应关系和其他的组合对象，包括循环引理和格盘路径手法。很多这些结果可能或者已经被用于生成函数和Lagrange反演公式。
我们证明这些计算的使用分析了以下情况：（1）排序问题，（2）大量树的遍历的平均长度，（3）线索二叉树的算法，（4）模式匹配问题。
二、关系
我们讨论有序树（见Knuth[1968]的定义）。每个结点有一个度（它的子树个数）。度为0的结点称为它的叶子；其他结点都被称为内部结点。结点的深度是它到根的距离（根的深度为0）。在集合中n边有序树的和就是著名的Catalan数。
（例子见Gardner[1976]）。
这些是很多有序树集合中的元素一一对应关系和其他的组合对象（例子见Kuchinski[1977]）。其中，以下集合中的关系可以帮助我们计算：
：有n条边的有序树的集合。
：有n个内部结点的二叉树（每个结点最多有两个子树）的集合。
：有n个左括号和n个右括号的按一个左括号对应一个右括号的顺序的集合。
： n 1个非负整数和为n，如
其中i=0,1，hellip;，n-1
：格盘路径中从（0,0）到（n,n）的不低于对角线y=x（所有步数都是往上或者往右）的最短路径的集合。
这五个集合中的关系都在图1中阐述。总之，就是中有一个树t，就是前序遍历t得到的，并在每条边的路向下时写“（”每条边的路向上时写“)”（见图1.2.）。在中选取一条来自的格盘路径，从（0,0）开始并每次左括号为向上一个坐标，右括号为向右一个坐标（见图1.3.）。从唯一的t在中得到序列是前序读取所有t的所有结点的度（见图1.4.）。从到中的一个二叉树是通过前序建立的，路上每一步的向上相当于一个内部结点，每一步向右相当于一个叶子（最末端的叶子也要被加起来）（见图1.5.）。
左右括号的顺序被称作为规定。如果在每个左括号数字的前缀比右括号数字更大。我们用如下引理：
循环引理（Dvoretzky and Motzkin[1947])：在任何序列，其中m个左括号，n个右括号，，这里恰好有有个循环数列
这就是规定。
这个引理符合了中的有序树与n 1个左括号n个右括号的循环存在一一对应的关系，这里只有一个有一个额外需要预先考虑的左括号的合法的排列。此外，每个这样的括号循环对应一个总和为n的n 1个非负整数（代表着在一对左括号中的右括号的个数）。这些对应都是我们计算用的循环引理中的基础。
三、计算
在这一章我们提出主要计算结果并讨论这些结果中的一些。所有的树都来自。
定理 1:中的树有个j度结点，，没有多于d
的结点限制，为，
当（所有限制结点的总和），（所有导致的边的总和）。
这概括了Narayana[1959]的结论：当d=0（Dershowitz证明，zaks[1980]用在了循环定理中）和多项式公式中d=n的情况（Erdelyi和Etherington[1940]，Raney[1960]用循环定理证明了这点）。
证明：在循环定理中我们必须数n 1个总和为n的非负整数的循环，其中为i，。为了数这些限制循环的个数，标记共有种方式来放置一个有n 1个位置的循环中限制结点的度。这剩下的n 1-m个不限制结点必须有结点值从d 1到n共计n-e。这些安置那些度的方式的数目等于把整数分解成从0到共个整数，即。
从这个定理我们可以得到以下：
结论：
1.1）有着k个叶子的的树的个数。这就是Narayana[1959]的结论。
1.2）有着k个叶子的的树的个数等于有着n 1-k个子叶的的树的个数.
1.3)被排除的叶子（或内部结点）的个数是。（这里假定中所有的树的结果都等概率的）。这个结果也是Dasarathy和Yang[1980]提供的。
1.4）被排除的内部结点的度为
定理2：在中第层度为d的结点的总数为，其中。
这个结果首先被Dershowitz和Zaks[1980]所证明。我们这里用格子路径证明。
证明：从（0,0）到（）的不在对角线下面的格子路径数目为
（如见Mohanty[1979]）。我们给每一条路径和每个中第层度为d的结点对应。（这个对应适用于，且时有一个更简单的对应成立的情况）。
考虑中的一棵树t和其对应的从（0,0）到（n，n）的格子路径。t中第层度为d的结点x对应一条路径分割
（a）
这不在对角线的下面（除了两个端点）。这个分割在另一个分割之后：
（b）
在这个分割之前：
（c）
为了得到从（0,0）到（）的想得到的格子路径，我们做如下事情（见图2）：
- 格子路径的步骤，，和，一样，都是从（a）中移出来的，产生一个路线分割从。
- 分割（b）完好无损地保留。
- 分割（c）被颠倒命令和步骤方向所转化，即每一步向右变成了向下，每一步向上变成了每一步向左，产生一个路线分割结束于（）开始于（）。漏掉的步骤也加上去了。
因为结点和路径间的对应是一对一的，想要的结果就被证明了。（为了得到对应的结点，考虑到路径，注意和都由结束点（）决定，并对所有j，，从到结束点的路径分割不返回低于对角线。被删除的步骤和被转化的路径分割都可以被容易地恢复。） []
从这个定理，我们可以得到以下：
结论：
2.1）第层度从i到j的结点的总数是
特别的，第层的结点总数为
2.2）其他的中的一棵树第层的叶子期望总数为
对于小，
2.3）一个叶子的期待深度为
（这个总数和后来的几个被用于恒等式，比如Riordan[1968]。）树的外部路径长度（被Knuth[1968]定义）是子叶和他们的叶子数的总和。因此，期望外部路径长度为
2.4）第层的内部结点的期望总数为
对于小，
2.5）所有内部结点的叶子期待总数为
树的内部路径长度是叶子和它们的内部结点的总和。因此，树的内部路径期待长度为
2.6）一个结点的期待叶子数为
这个结果来自Volosin[1974],Meir和Moon[1978],和Dasarathy和Yang[1980]。更高层次的结点深度可以被同样计算。
2.7）深度i到j的度为d的结点总数为
特别的，度为d的结点总数为
这遵循深度i到j的结点总数为
度为i到j的结点总数为
2.8）中的一棵树的度为d的结点期望总数为
对于小d，
2.9）根上度r的树的个数为
根度的期望值为
这些结果也在Ruskey和Hu[1977]中被给出。用类似的方式更高次也可以被计算。比如，根度的不一致数为
四、应用
在这一章我们阐明之前的章节的公式如何帮助验证各种各样的算法。
- 排序问题：给定一个有n条边且每个结点都有一个数字储存的定向树，我们希望给这些边排序以便每个结点的子树可以有越来越多的数字。（在这种情况下给树分类的需求被引发在算法中来按条件计算递归路径排序，在Dershowitz[1981]中被定义）。一个有d个子叶的结点需要少于个类似去排序，因此类似的总数被来自度为i的有个结点的一棵树所约束。为了寻找中所有有这个功能的树的平均数，我们使用中度为d的结点数的闭型（结论2.7）：
因此，一般来说，每个少于一个类似结点是必需的。考虑到排序d子叶实际上需
要只与个类似相似，一个更略微好的结论就可能得到了。
- 一个堆栈的平均高度：有序树的高度是最差的堆栈大小，在遍历树，表达，前序中产生。deBruijn,Knuth和Rice[1972]还有其他人都已经证明了中所有树中这个高度的期待值大概是。代替研究最差的堆栈大小，如果我们在遍历树的时候关注其平均值，我们需要结点的期望水平，这个我们已经看过（结论2.6）是
如果这个平均数是被在那个高度的堆栈的遍历中的次数所加权。也就是说，这个节
点的度加上一，然后我们得到
- 线索二叉树：在Brinck和Foo[1981]的最近的论文中，线索二叉树的算法都是调查的。这些分析都在某些枚举引理的基础上，用递归关系证明。我们的计算方法使某种用一个直接的组合方法来证明那些引理成为可能，这也阐明了那些树的结构。
比如说，中一个二叉树的左边叶子（即反向线程）的期待值和右边叶子（即正向
线程）的期待值，都等于一个有序树（在和中对应）中所有叶子的期待值，这个我们已经见过（结论1.3）是。并且，从一个二叉树的根到最左（或者最右）的叶子的期待路程等于一个有序树（让中的序列中的每个数字对应优于中的前序构造的树的叶子的内部叶子）的根度的期待值，这个我们已经见过（结论2.9）是。
- 模式匹配：Flajolet和Steyaert[1980]最近已经研究了树的匹配算法。用我们的
方法可以解决相似问题。比如，一个模式是一些叶子指定打开的有序树。模式p就是说存在在x包含一个和有着代替开结点的任意的树p有同样形式代替树。为了知道有着e条边d个开叶子的确定的模式p有多少次以中的一些树中的代替树出现，我们简单地用一个度为d的结点代替p，并提问度为d有多少结点为；这个数字已经给出（结论2.7）为。
类似的，第层发现数为p的数字为。
更普遍地，m和中明显不重叠的模式的组合存在数为
当e是这些模式中边的总数，d是开叶子的总数，。
为了证明这个，注意有n个结点的树中模式的存在数等于有度为（为中开叶子的个数）边为的m个贴上标签的结点。每一个这样的树相当于（周期引理）一个有个度的周期，它们中规定并被贴上标签的有m个，共计。它们为。
在循环里放置这些被贴上标签的结点的方法为个详述这些剩下的结点的
度的方法。以类似的方式这个可以被证明为
是二叉树的集合中的m个模式的存在数，在这种情况下e代表模式里内部结点的总数。比如有正向线程的中左结点的个数（即有都是左子叶也有右叶子的内部结点的个数）为
（比较 Brinck和Foo[1981]）
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[27574]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
