臺灣博碩士論文加值系統

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.

中文摘要 i
Preface ii
誌謝 iv
Contents(目錄) v
一 Introduction 1
二 Tools 9
2.1 Singularity Analysis 9
2.2 Probability Theory 13
2.3 Grown Simply Families of Increasing Trees 14
2.4 Differential Equation 16
2.5 Some Technical Lemmas 18
三 Generalized PORTs 23
3.1 Mean Value and Variance 23
3.2 Higher Moments and Distribution of X_{n,k} 28
四 d-ary Trees 38
4.1 Mean Value and Variance 38
4.2 Higher Moments and Distribution of X_{n,k} 43
五 Conclusion 52
Bibliography 53

[1] F. Bergeron, P. Flajolet, and B. Salvy. Varieties of increasing trees. Lectures Notes in Computer Science, 581:24-48, (1992).
[2] F. Dennert and R. Gr\''{u}bel. On the subtree size profile of binary search trees. Combinatorics, Probability and Computing, 19:561-578, (2010).
[3] Q. Feng, H. Mahmoud, and A. Panholzer. Phase changes in subtree varieties in random recursive and binary search trees. SIAM Journal on Discrete Mathematics, 22:160-184, (2008).
[4] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, (2009).
[5] M. Fuchs. Subtree sizes in recursive trees and binary search trees: Berry-esseen bounds and poisson approximations. Combinatorics, Probability and Computing, 17:661-680, (2008).
[6] M. Fuchs. Limit theorems for subtree size profiles of increasing trees. Combinatorics, Probability and Computing, 21:412-441, (2012).
[7] M. Fuchs, H.-K. Hwang, and R. Neininger. Profiles of random trees: Limit theorems for random recursive trees and binary search trees. Algorithmica, 46:367-407, (2006).
[8] A. Panholzer and H. Prodinger. Level of nodes in increasing trees revisited. Random Structures and Algorithms, 31:203-226, (2007).