廣義PORT樹與d維樹的子樹大小描述

Abstract

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.