Balanced Parentheses Strike Back
Date Issued
2006
Date
2006
Author(s)
Yeh, Chia-Chi
DOI
en-US
Abstract
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.
Subjects
有根樹
資料結構
平衡括號
rooted tree
succinct data structure
balanced parentheses
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93922048-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):446c4c086a92821b90bfda71f26ce390