Abstract
and the Society for Industrial and Applied Mathematics. There exist two well-known succinct representations of ordered trees: BP (balanced parenthesis) [Munro, Raman 2001] and DFUDS (depth first unary degree sequence) [Benoit et al. 2005]. Both have size 2n+o(n) bits for n-node trees, which asymptotically matches the information-theoretic lower bound. Many fundamental operations on trees can be done in constant time on word RAM, for example finding the parent, the first child, the next sibling, the number of descendants, etc. However there has been no single representation supporting every existing operation in constant time; BP does not support i-th child, while DFUDS does not support lca (lowest common ancestor). In this paper, we give the first succinct tree representation supporting every one of the fundamental operations previously proposed for BP or DFUDS along with some new operations in constant time. Moreover, its size surpasses the information-theoretic lower bound and matches the entropy of the tree based on the distribution of node degrees. We call this an ultra-succinct data structure. As a consequence, a tree in which every internal node has exactly two children can be represented in n + o(n) bits. We also show applications for ultra-succinct compressed suffix trees and labeled trees.
Original language | English |
---|---|
Title of host publication | Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |
Publisher | Association for Computing Machinery |
Pages | 575-584 |
Number of pages | 10 |
Volume | 07-09-January-2007 |
ISBN (Electronic) | 9780898716245 |
Publication status | Published - 1 Jan 2007 |
Externally published | Yes |
Event | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States Duration: 7 Jan 2007 → 9 Jan 2007 |
Conference
Conference | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |
---|---|
Country/Territory | United States |
City | New Orleans |
Period | 7/01/07 → 9/01/07 |
ASJC Scopus subject areas
- Software
- General Mathematics