Representation of ordered trees with a given degree distribution

2018/07/01 by Tsur, Dekel
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1807.00371

Abstract

The degree distribution of an ordered tree T with n nodes is n = (n₀,…,n_n-1), where n_i is the number of nodes in T with i children. Let N(n) be the number of trees with degree distribution n. We give a data structure that stores an ordered tree T with n nodes and degree distribution n using log N(n)+O(n/log^t n) bits for every constant t. The data structure answers tree queries in constant time. This improves the current data structures with lowest space for ordered trees: The structure of Jansson et al. [JCSS 2012] that uses \logN(n)+O(nloglog n/log n) bits, and the structure of Navarro and Sadakane [TALG 2014] that uses 2n+O(n/log^t n) bits for every constant t.

Related

• Tree Path Majority Data Structures
• Automated Counting and Statistical Analysis of Labeled Trees with Degree Restrictions
• Using statistical encoding to achieve tree succinctness never seen before
• Open Problem: Properly learning decision trees in polynomial time?
• Fully-Functional Static and Dynamic Succinct Trees