1
$\begingroup$

By binary cardinal tree, I mean a tree with degree 2.

The question confuses me because I know LOUDS/DFUDS can encode binary trees with 2n bits; however, this paper claims that it is possible to encode with only n bits.

The paper was published on PODS 2008 and provides solid inferences around the confusing point. Thus, I could have missed some more succinct approach.

The related context is in Section 3, at the bottom right on Page 3 of the aforementioned paper.

I appreciate any advice or suggestions.

$\endgroup$
2
  • 1
    $\begingroup$ It’s not clear to me what exactly you are referencing, as the paragraph at bottom right on p. 3 discusses a lower bound, not upper bound, on the number of some kind of trees. However, the whole discussion there is about binary trees with no unary nodes. Such trees with $n$ nodes can be indeed encoded by $n$-bit strings in a straightforward way (write the tree in preorder, indicating for each node the 1-bit information whether it has 0 or 2 children). $\endgroup$ Commented Jun 11 at 7:39
  • $\begingroup$ @EmilJeřábek Oh thank you! I see the problem is I missed 'no unary nodes.' Would you mind posting the comment as an answer, or shall I close this question? $\endgroup$
    – Xavier Z
    Commented Jun 11 at 7:49

1 Answer 1

3
$\begingroup$

The discussion in the linked FGGSV paper is about binary trees with no unary nodes. It is easy to encode such trees with $n$ nodes by $n$-bit strings: write the tree in preorder, indicating for each node whether it has $0$ or $2$ children using $1$ bit. (In other words, if you think of such trees as terms/formulas in a language with one binary and one nullary symbol, just write it in prefix (Polish) notation.)

More precisely, the number of such trees is the Catalan number $C_{(n-1)/2}=\frac1n\binom n{(n-1)/2}=\Theta(2^nn^{-3/2})$ (NB: $n$ must be odd), hence the optimal number of bits they can be encoded with, not necessarily efficiently, is $n-\frac32\log n+O(1)$.

For binary trees that may possibly include unary nodes, there are $4$ possibilities for each node depending on which of its two children is occupied, hence the preorder description takes $2n$ bits, and one can check the number of such trees is $C_n$, thus the information-theoretic optimal encoding needs $2n-\frac32\log n+O(1)$ bits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.