On succinct representations of binary trees

DOI10.1007/S11786-017-0294-4zbMATH Open1369.68169arXiv1410.4963OpenAlexW2169671414MaRDI 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)

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.

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

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

zbMATH Keywords

binary treesuccinct data structureCartesian treetree traversalordinal treeZaks' sequence

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Succinct representation of balanced parentheses and static trees
• Fully functional static and dynamic succinct trees
• Universal Succinct Representations of Trees?
• Title not available (Why is that?)
• Succinct Trees in Practice
• Representing trees of higher degree
• Compressed suffix trees with full functionality
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Title not available (Why is that?)
• Succinct data structures for flexible text retrieval systems
• Lexicographic generation of ordered trees
• Space-Efficient Algorithms for Document Retrieval
• A unifying look at data structures
• Title not available (Why is that?)
• Lempel-Ziv factorization using less time \& space
• Replacing suffix trees with enhanced suffix arrays
• A Uniform Approach Towards Succinct Representation of Trees
• A simple optimal representation for balanced parentheses
• Dominance made simple
• Encoding range minima and range top-2 queries
• Succinct Representations of Ordinal Trees

Cited In (10)

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

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)