2009/05/06 by Gonzalo Navarro, Navarro, Gonzalo, Kunihiko Sadakane +1 · 4 citations
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization #Video Analysis and Summarization
paper · pdf · doi:10.48550/arxiv.0905.0768
openalex publication_date 2009/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose new succinct representations of ordinal trees, which have been studied extensively. It is known that any n-node static tree can be represented in 2n + o(n) bits and a number of operations on the tree can be supported in constant time under the word-RAM model. However the data structures are complicated and difficult to dynamize. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature to a few primitives that are carried out in constant time on sufficiently small trees. The result is extended to trees of arbitrary size, achieving 2n + O(n /\polylog(n)) bits of space. The redundancy is significantly lower than any previous proposal. Our data structure builds on the range min-max tree to achieve 2n+O(n/log n) bits of space and O(log n) time for all the operations. We also propose an improved data structure using 2n+O(nloglog n/log n) bits and improving the time to the optimal O(log n/log log n) for most operations. Furthermore, we support sophisticated operations that allow attaching and detaching whole subtrees, in time \Order(log1+ε n / loglog n). Our techniques are of independent interest. One allows representing dynamic bitmaps and sequences supporting rank/select and indels, within zero-order entropy bounds and optimal time O(log n / loglog n) for all operations on bitmaps and polylog-sized alphabets, and O(log n log σ/ (loglog n)2) on larger alphabet sizes σ. This improves upon the best existing bounds for entropy-bounded storage of dynamic sequences, compressed full-text self-indexes, and compressed-space construction of the Burrows-Wheeler transform.