What is the number of ordinal trees (aka rose trees) with $n$ nodes, of depth $d$, with $l$ leaves?

I thought that it was a known results but I could not find it, and neither did the various combinatorics whom I asked. It seems that it should be computed using generating functions, but beside the fact that such a generating function would have two variables, there is also the fact that the number of nodes and of leaves are additive between the various children of a tree, whereas the depth of a tree is one plus the max of the depth of each of its children: I don't know how to express those in a generating functions.

The reason I ask is that, when considering (some variant of) the cartesian tree of a multiset in order to support Range Minimum Queries on it, the number of runs in the multisets corresponds exactly to the number of leaves, and the number of distinct elements in the multiset gives a bound on the depth of the ordinal tree: the logarithm of the number of such trees will give a lower bound on the space usage of any compressed index supporting Range Minimum Queries, in the worst case over multisets of size $n$ with $l$ runs and $d$ distinct values. (And, with only a bit more work I believe, an asymptotically tight upper bound.)

Demaine et al define an ordinal tree as "a rooted tree of arbitrary degree in which the children are ordered" http://erikdemaine.org/papers/MaryTrees_Algorithmica/paper.ps. It seems that they are also called Rose trees in some communities. They should not be confused with cardinal trees, also called $k$-ary trees.

  • 1
    $\begingroup$ What is an ordinal tree? $\endgroup$ – Kaveh May 24 '16 at 14:57
  • 2
    $\begingroup$ "An ordinal tree (see, e.g., [Geary et al. 2004; Benoit et al. 2005]) is an arbitrary rooted tree where the children of each node are ordered." [www.csie.ntu.edu.tw/~hil/paper/talg07.pdf] $\endgroup$ – Jeremy May 24 '16 at 22:40
  • 2
    $\begingroup$ What’s the difference between a “list” and an “array” here? As far as I can see, both are just (ordered) sequences. $\endgroup$ – Emil Jeřábek May 25 '16 at 12:34
  • $\begingroup$ An array can be accessed by position, and some positions can be empty. For instance, a node in a binary tree can have a right child without having a left child. A list (in general) does not have "empty elements". An ordinal tree has only a list of children, none of them empty (but the list itself can be empty). $\endgroup$ – Jeremy May 26 '16 at 12:06
  • 1
    $\begingroup$ In data structure terms, your ordinal trees are sometimes called Rose Trees, which algebraicly are labeled ordered unranked trees. I would call a cardinal tree a k-ary tree. I too found your array/list distinction a bit confusing at first; the point is that an array here is fixed size (doesn't grow, same size at all nodes) while a list is unbounded (no upper limit on number of children). $\endgroup$ – Joseph May 26 '16 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.