On succinct representations of binary trees

DOI10.1007/S11786-017-0294-4zbMATH Open1369.68169OpenAlexW2169671414MaRDI QIDQ2363992FDOQ2363992

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 treesuccinct data structureCartesian treetree traversalordinal treeZaks' 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

• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• scientific article; zbMATH DE number 6146456 (Why is no real title available?)
• A Uniform Approach Towards Succinct Representation of Trees
• A simple optimal representation for balanced parentheses
• 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
• 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 Trees in Practice
• Succinct data structures for flexible text retrieval systems
• Succinct representation of balanced parentheses and static trees
• Succinct representations of ordinal trees
• Universal Succinct Representations of Trees?

Cited In (10)

• Succinct Trees in Practice
• A uniform paradigm to succinctly encode various families of trees
• Title not available (Why is no real title available?)
• Constant-memory iterative generation of special strings representing binary trees
• Dualities in tree representations
• Succinct representations of binary trees for range minimum queries
• Short Transitive Signatures for Directed Trees
• Succinct permutation graphs
• A Uniform Approach Towards Succinct Representation of Trees
• Efficient Schemes for Computing α-tree Representations

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)