On succinct representations of binary trees

DOI10.1007/S11786-017-0294-4MaRDI QIDQ2363992zbMATH OpenOpenAlexFDO

Authors Pooya Davoodi, Srinivasa Rao Satti, Rajeev Raman

Publication date 17 July 2017

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.4963

zbMATH Keywords

binary treeCartesian treeordinal treesuccinct data structuretree traversalZaks' sequence

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We observe that a standard transformation between emph{ordinal} trees (arbitrary rooted trees with ordered children) and binary trees leads to interesting succinct binary tree representations. There are four symmetric versions of these transformations. Via these transformations we get four succinct representations of $n$-node binary trees that use $2n+n/(logn{)}^{O(1)}$ bits and support (among other operations) navigation, inorder numbering, one of pre- or post-order numbering, subtree size and lowest common ancestor (LCA) queries. The ability to support inorder numbering is crucial for the well-known range-minimum query (RMQ) problem on an array $A$ of $n$ ordered values. While this functionality, and more, is also supported in $O(1)$ time using $2n+o(n)$ bits by Davoodi et al.'s (emph{Phil. Trans. Royal Soc. A} extbf{372} (2014)) extension of a representation by Farzan and Munro (emph{Algorithmica} extbf{6} (2014)), their emph{redundancy}, or the $o(n)$ term, is much larger, and their approach may not be suitable for practical implementations. One of these transformations is related to the Zaks' sequence (S.~Zaks, emph{Theor. Comput. Sci.} extbf{10} (1980)) for encoding binary trees, and we thus provide the first succinct binary tree representation based on Zaks' sequence. Another of these transformations is equivalent to Fischer and Heun's (emph{SIAM J. Comput.} extbf{40} (2011)) minheap structure for this problem. Yet another variant allows an encoding of the Cartesian tree of $A$ to be constructed from $A$ using only $O(sqrtnlogn)$ bits of working space.

Recommendations

• Succinct representations of binary trees for range minimum queries
• Fully-functional succinct trees
• Representing dynamic binary trees succinctly
• Ultra-succinct representation of ordered trees
• Succinct ordinal trees based on tree covering

Cites work

• A simple optimal representation for balanced parentheses
• A Uniform Approach Towards Succinct Representation of Trees
• A unifying look at data structures
• Compressed suffix trees with full functionality
• Dominance made simple
• Encoding range minima and range top-2 queries
• Finding dominators revisited (extended abstract)
• Fully functional static and dynamic succinct trees
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• scientific article; zbMATH DE number 6146456 (Why is no real title available?)
• Lempel-Ziv factorization using less time \& space
• Lexicographic generation of ordered trees
• Replacing suffix trees with enhanced suffix arrays
• Representing trees of higher degree
• Space-Efficient Algorithms for Document Retrieval
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct data structures for flexible text retrieval systems
• Succinct representation of balanced parentheses and static trees
• Succinct representations of ordinal trees
• Succinct Trees in Practice
• Universal Succinct Representations of Trees?

Cited in

(13)

• A uniform paradigm to succinctly encode various families of trees
• Succinct permutation graphs
• Short Transitive Signatures for Directed Trees
• Constant-memory iterative generation of special strings representing binary trees
• Succinct representations of binary trees for range minimum queries
• A Uniform Approach Towards Succinct Representation of Trees
• Efficient Schemes for Computing α-tree Representations
• Dualities in tree representations
• Succinct Trees in Practice
• scientific article; zbMATH DE number 7765383 (Why is no real title available?)
• Quantum data structure for range minimum query
• Tiny pointers
• A simple representation of tree covering utilizing balanced parentheses and efficient implementation of average-case optimal RMQs

This page was built for publication: On succinct representations of binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2363992)