# Representation of ordered trees with a given degree distribution

arXiv: https://arxiv.org/abs/1807.00371 · HTML: https://mlsanity.com/paper/1807.00371/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [Yet Another Representation of Binary Decision Trees: A Mathematical Demonstration](https://mlsanity.com/paper/2101.07077/) (2021)

## Abstract (arXiv)

The degree distribution of an ordered tree T with n nodes is vecn = (n0,ldots,nn-1), where ni is the number of nodes in T with i children. Let N(vecn) be the number of trees with degree distribution vecn. We give a data structure that stores an ordered tree T with n nodes and degree distribution vecn using log N(vecn)+O(n/logt 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(vecn)+O(nloglog n/log n) bits, and the structure of Navarro and Sadakane [TALG 2014] that uses 2n+O(n/logt n) bits for every constant t.