呂學一臺灣大學：資訊工程學研究所葉家齊Yeh, Chia-ChiChia-ChiYeh2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53734有根樹是一種非常基本且重要的資料結構，而如何有效率地將它儲存起來並提供快速地查詢是一個被廣泛地探討的問題。 目前已知最好的結果是由 Geary、Raman 和 Raman 所提出的表示法 [SODA 2004, 第 1-10 頁]。 給定一棵 n 個節點的有根樹 T，他們的表示法在空間上需要 2n + o(n) 位元，其最高項已經達到資訊理論上的最佳解。 此外，他們的表示法在常數時間內對於 T 支援多種查詢。 在本篇論文中，我們基於 2n 個括號的平衡字串，對於 T 提出了改良的 2n + o(n) 位元表示法。我們的成果可以分成兩方面： 其一，我們的表示法在常數時間內所能支援的查詢，為 Geary、Raman 和 Raman 的表示法所支援的超集合； 其二，在我們使用的表示法中，可以很容易地藉著加入新的輔助字串來支援新的查詢。Succinct representations for trees with efficient query support have been extensively studied. The best previously known result is due to Geary, Raman, and Raman [SODA 2004, pages 1-10]. The number of bits required by their representation for an n-node tree T is 2n + o(n), whose first-order term is information-theoretically optimal. Their representation supports a large set of O(1)-time queries on T. Based upon a balanced string of 2n parentheses, we give an improved 2n + o(n)-bit representation for T. Our improvement is two fold: Firstly, the set of O(1)-time queries supported by our representation is a proper superset of that supported by the representation of Geary, Raman, and Raman. Secondly, it is also much easier for our representation to support new queries by simply adding new auxiliary strings.Chinese Abstract . . . . . . . . . . . . . . . . . . . . . ii English Abstract . . . . . . . . . . . . . . . . . . . . . iii Acknowledgements . . . . . . . . . . . . . . . . . . . . . iv Contents . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . vi List of Figures . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 1 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . 5 3 Distance, Subtree Height, and Lowest Common Ancestor . . 7 4 Rank and Select for Children . . . . . . . . . . . . . . 11 4.1 Child Rank . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Child Select . . . . . . . . . . . . . . . . . . . . . 14 5 Concluding Remarks . . . . . . . . . . . . . . . . . . . 20 Bibliography . . . . . . . . . . . . . . . . . . . . . . . 21435963 bytesapplication/pdfen-US有根樹資料結構平衡括號rooted treesuccinct data structurebalanced parenthesesthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53734/1/ntu-95-R93922048-1.pdf