I would like to describe a bijection between binary trees and plane trees. A binary tree has a root node and each node of the tree has at most 2 children (left and right). A plane tree has a root node and the children of each node are ordered from left to right. Can someone enlighten me on this? Thanks!
[Math] Bijection between binary trees and plane trees
combinatoricstrees
Related Solutions
Catalan numbers satisfy the recurrence:
$C_0 = 1, C_{n+1} = \sum_{i=0}^nC_iC_{n-i}, n \geq 0$
So it suffices that show that binary trees satisfy the same recurrence.
Let $T_n$ be the number of binary trees with $n$ parent nodes.
There is 1 tree with zero parent nodes. So $T_0=1$.
For $n \geq 0$: A tree $t$ with $n+1$ parent nodes has a root with two subtrees as children $t_1$ and $t_2$. Since the root of $t$ is a parent node, $t_1$ and $t_2$ must have $n$ parent nodes together (i.e. if $t_1$ has $i$ parent nodes then $t_2$ has $n-i$ parent nodes). Then the number of ways to make children $t_1$ and $t_2$ is $\sum_{i=0}^nT_iT_{n-i}$.
First a side remark. As you noted, $n=c_0+c_1+c_2$. Also, we note that every node except the root is the child of exactly one other node, therefore $n-1=c_1+2c_2$. Using these two relations, we can write $$\begin{align} c_1&=n+1-2c_0 \\c_2 &= c_0-1 \end{align}$$ And then only use $n$ and $c_0$ as parameters.
Second, the actual question. For the worst case (large $h$), you can simply put all one- and two-sibling in a single long chain, which means $h=c_1+c_2+1$. For the best case (small $h$) you make a balanced tree out of the two-children nodes. This will have height about $log_2(c_2)$ with about $c_2/2$ nodes on the lowest level. The remaining one-child nodes should be distributed into $c_2/2$ chains of equal lengths and put underneath the balanced tree. The result is something like $h\approx \log_2(c_2)+2\frac{c_1}{c_2}+1$.
So the answer you are looking for is approximately $h\in [\log_2(c_2)+2\frac{c_1}{c_2}+1,c_1+c_2+1]$. The second expression needs some appropriate rounding in case $c_2$ is not a nice number and such, but you can figure that out for yourself if neccesary.
Third, you see that the upper bound is not really good. In particular it is worse then any real actual red-black/avl tree. Maybe instead of considering strict bounds on $h$, you should think about the average $h$ over all trees with given $c_0,c_1,c_2$. That will be much closer to practical datastructures.
Best Answer
There is a way of encoding n-ary trees into binary: the left is a son and the right is a brother; here is the Wikipedia's entry.
P.S. This was a comment, made an answer on request.