標題: 廣義PORT樹與d維樹的子樹大小描述
The Subtree Size Profile of Generalized PORTs and d-ary Trees
作者: 林立庭
Lin, Li-Ting
符麥克
Fuchs, Michael
應用數學系所
關鍵字: 解析組合;奇異點分析;同層描述;子樹大小描述;廣義PORT樹;d維樹;m次動差生成函數;Analytic Combinatorics;Singularity Analysis;Node Profile;Subtree Size Profile;Generalized PORTs;d-ary Trees;m-th Moment Generating Function
公開日期: 2012
摘要: Generalized PORTs和d-ary trees都有其對應的應用模型。這兩種不同的tree 我們能使用相同手法去對於它們的性質進行研究,而利用的性質可以是它們的out-degree為k的node數、level為k的node數、subtree size為k的node數...等。 本篇中我們所使用的性質為相同subtree size為k的node數───即subtree size profile───來進行研究。在這裡,我們使用singularity analysis來進行我們的證明並且能讓證明過程能更加簡化且清楚。 本篇的概述為:第一章將介紹關於我們的研究領域的歷史以及前人的結果,最後提出關於我們主要證明的源由跟主要定理的提出。第二章我們會介紹singularity analysis,以及我們主要證明中相關的機率定理和會用到的預備知識。第三章為我們證明generalized PORTs之下,使用subtree size profile的性質所證明的結果。第四章是我們要證明d-ary trees之下,使用subtree size profile的性質所證明的結果。第五章我們會對於主要證明的過程以及主要定理的結果給予結論跟討論。
Generalized plane-oriented recursive trees (PORTs) and d-ary trees are two important tree families with many applications. Their properties can be analyzed with the same tools, where properties which are often studied include: the number of nodes of a fixed out-degree, the number of nodes of a fixed level, the number of nodes with subtree rooted at the node having a fixed size, etc. In this thesis, we will consider the number of nodes with subtree rooted at the node having a fixed size. This is the so called subtree size profile. We will show how to use singularity analysis to obtain the mean value, variance, higher moments and limiting distribution of the subtree size profile for the above two families of trees (under a suitable random model). An outline of the thesis is as follows: in Chapter 1, we will review the recent history of the subtree size profile and explain the purpose of the current work. In Chapter 2, we will give a brief introduction into singularity analysis, state some useful results from probability theory and prove some prepatory results. In Chapter 3 and Chapter 4, we will discuss the subtree size profile for generalized PORTs and d-ary trees, respectively. These two chapters will also contain our main results. Finally, in Chapter 5, we will summarize our work and conclude with some remarks.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070052228
http://hdl.handle.net/11536/71611
Appears in Collections:Thesis


Files in This Item:

  1. 222801.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.