Balanced Parentheses Strike Back
Resource
ACM Transactions on Algorithms 4 (3): 28
Journal
ACM Transactions on Algorithms
Pages
1
Date Issued
2008
Date
2008
Author(s)
LU, HSUEH-I
YEH, CHIA-CHI
Abstract
An ordinal tree is an arbitrary rooted tree where the children of each node are ordered. Succinct representations for ordinal trees with efficient query support have been extensively studied. The best previously known result is due to Geary et al. [2004b, pages 1--10]. The number of bits required by their representation for an n -node ordinal tree T is 2 n + 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 2 n parentheses, we give an improved 2 n + o ( n )-bit representation for T . Our improvement is two-fold: First, 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. Second, it is also much easier for our representation to support new queries by simply adding new auxiliary strings.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
04.pdf
Size
225.27 KB
Format
Adobe PDF
Checksum
(MD5):7d7dcd16297e91b7a8db3590f67940de