數位搜尋樹的機率演算分析

Abstract

數位搜尋樹(digital search trees, DSTs for short)與桶型數位搜 尋樹(bucket DSTs,每個的節點最多可儲存b 筆資料,b-DSTs for short)為電腦科學中基本的資料結構。這兩種資料結構由具有0-1 數列的儲存資料所組成。此篇論文中，我們考慮隨機生成的DSTs。

在這十年來，幾乎所有關於隨機DSTs 的重要參數(parameters)都有研究結果出現。如： 深度(Depth) ， 距離(Distance) ， 外部- 內部節點(External-internal nodes)，內節點路徑長度(Internal path length)和大小(Size)。這些研究結果中有用到許多的分析方法，其中最主要都在解析組合的範疇內。

在此論文中，我們主要著重於探討DSTs 的內節點路徑長度。我們將介紹近年發展出來之研究結果，與其使用到之分析技術。除此之外，還會介紹一個全新的方法，此法將由Fuchs、Hwang 和Zacharovas 在以後的研究中發表。此方法將會改進對b-DST 上內節點路徑長度的分析。

這份論文的主要目地有兩個：第一，我們給出近年來關於DSTs 之內節點路徑長度的分析方法與研究結果，和其他參數的研究結果整理。此外我們也給了一些分析技術上的改進。第二，我們提出一個全新的分析方法，也得到一個對於b-DSTs 上內節點路徑長度更加簡單的結果。

論文組織如下：第一章介紹內節點路徑長度研究使用之分析技術。第二章為內節點路徑長度與其他參數的期望值(mean)與變異數(variance)之研究結果整理。第三章中介紹新的方法並給出我們的主要結果。

Digital search trees (DSTs for short) and their generalizations such as bucket digital search trees (b-DSTs) are fundamental data structures in computer science. These trees are built from records whose keys consist of 0-1 strings. In this thesis, we will consider random DSTs which are obtained by assuming that the bits of the keys are randomly generated. Characteristic parameters of random DSTs are random variables and their analysis has attracted a lot of attention in recent decades. Examples of parameters considered in previous works include: the depth of a random node [5, 12, 15, 17, 18, 19, 20, 22], the distance of two random nodes [1], the number of external-internal nodes [5, 9, 15, 21, 13], the internal path length [5, 8, 10, 14], and the size of the tree [4, 9]. For the analysis, several interesting methods have been proposed, most of them belonging to the field of analytic combinatorics. In this thesis, we focus on the internal path length of DSTs. We will introduce the techniques which have been devised for the analysis of the internal path length. Moreover, we will give a new method, which will appear in a forthcoming work of Fuchs, Hwang, and Zacharovas, to improve the analysis of the internal path length of b-DSTs. The purpose of this thesis is twofold. First, we want to give a self-contained survey of the techniques used in the analysis of DSTs and the results achieved. Here, we will mainly follow previous works, but also introduce some technical improvements. Secondly, we are going to use the new approach of Fuchs, Hwang, and Zacharovas mentioned above to obtain exact and numerical results concerning the leading constant in the asymptotic expansion of the variance. In particular, our results will simplify and improve previous results. This thesis is organized as follows: in Chapter 1, we introduce the techniques which are of importance in the analysis of DSTs. In Chapter 2, we present results concerning mean value and variance of the internal path length and explain how they can be proved with the methods from Chapter 1. Moreover, we also give a short survey of results concerning other parameters. In Chapter 3, we introduce the new method and explain our new findings concerning the leading constant of the variance.