Fully-Functional Static and Dynamic Succinct Trees - Computer Science > Data Structures and AlgorithmsReport as inadecuate

Fully-Functional Static and Dynamic Succinct Trees - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: We propose new succinct representations of ordinal trees, which have beenstudied extensively. It is known that any $n$-node static tree can berepresented in $2n + on$ bits and a number of operations on the tree can besupported in constant time under the word-RAM model. However the datastructures are complicated and difficult to dynamize. We propose a simple andflexible data structure, called the range min-max tree, that reduces the largenumber of relevant tree operations considered in the literature to a fewprimitives that are carried out in constant time on sufficiently small trees.The result is extended to trees of arbitrary size, achieving $2n + On-\polylogn$ bits of space. The redundancy is significantly lower than anyprevious proposal. Our data structure builds on the range min-max tree toachieve $2n+On-\log n$ bits of space and $O\log n$ time for all theoperations. We also propose an improved data structure using $2n+On\log\logn-\log n$ bits and improving the time to the optimal $O\log n-\log \log n$for most operations. Furthermore, we support sophisticated operations thatallow attaching and detaching whole subtrees, in time $\Order\log^{1+\epsilon}n - \log\log n$. Our techniques are of independent interest. One allowsrepresenting dynamic bitmaps and sequences supporting rank-select and indels,within zero-order entropy bounds and optimal time $O\log n - \log\log n$ forall operations on bitmaps and polylog-sized alphabets, and $O\log n \log\sigma - \log\log n^2$ on larger alphabet sizes $\sigma$. This improves uponthe best existing bounds for entropy-bounded storage of dynamic sequences,compressed full-text self-indexes, and compressed-space construction of theBurrows-Wheeler transform.

Author: Gonzalo Navarro, Kunihiko Sadakane

Source: https://arxiv.org/

Related documents