字典樹與基數樹之二階保護點的數量

Abstract

數位樹在電腦科學中的資料結構扮演極其重要的角色，而所謂的二階保護點在近期則受到相當大的矚目。舉例來說，J. Gaither、Y. Homma、M. Sellke以及M. D. Ward曾探討隨機的字典樹之二階保護點的數量進而求出它的期望值之漸近展開式。不但如此，J. Gaither與M. D. Ward更進一步求出它的變異數之漸近展開式，並猜測它數量的分布會滿足中央極限定理。 在這篇論文中，我們的主要目標是用M. Fuchs、黃顯貴和V. Zacharovas三人所提出來一個有系統的方法來重新驗證（也可說是糾正）他們的結果。經過運算，即便我們得到一個與他們截然不同的展開式，但我們的在數值上與他們的結果卻是完全相同的。不但如此，我們更是證實了他們猜想的中央極限定理。事實上，我們證明了一個更一般化的結果就是字典樹之內點與二階保護點的二元中央極限定理。根據這個結果我們不但是證明了J. Gaither與M. D. Ward的猜想，更是直接得知基數樹也會滿足中央極限定理。最後，我們還算出基數樹之二階保護點數量的期望值及變異數之漸近展開式。

Digital trees are data structures which are of fundamental importance in Computer Science. Recently, so-called 2-protected nodes have attracted a lot of attention. For instance, J. Gaither, Y. Homma, M. Sellke, and M. D. Ward derived an asymptotic expansion for the mean of the number of 2-protected nodes in random tries. Moreover, J. Gaither and M. D. Ward found an asymptotic expansion of the variance and conjectured a central limit theorem. In this thesis, our main goal is to re-derive (and correct) their results by using a systematic method due to M. Fuchs, H.-K. Hwang, and V. Zacharovas. The resulting expressions we obtain are quite different from the paper from J. Gaither, Y. Homma, M. Sellke, and M. D. Ward, but numerically they of course coincide. Moreover, we prove the conjectured central limit theorem from J. Gaither and M. D. Ward. In fact, we prove even a more general result, namely, a bivariate central limit theorem for the number of internal nodes and the number of 2-protected nodes in random tries. From this, not only the conjecture from J. Gaither and M. D. Ward follows but we also obtain a central limit theorem for PATRICIA tries. Finally, we also derive asymptotic expansions of mean and variance for PATRICIA tries.