0
$\begingroup$

I have a task to find a number of 2-3 trees... I don't quite know what it means, I'm asked to: find the number of 2-3 trees of depth $4$? Is there a specific way to find number of 2-3 trees of depth $n$?

Thanks!

$\endgroup$
3
  • 1
    $\begingroup$ I think I would be best to ask for clarification from the one who set this question for you. $\endgroup$ Nov 25 '17 at 2:26
  • $\begingroup$ Draw them all. Count them. $\endgroup$
    – Raphael
    Nov 25 '17 at 11:33
  • $\begingroup$ I'm guessing the 2-3 trees mean B-trees with the parameters set to 2 and 3 here? $\endgroup$
    – Raphael
    Nov 25 '17 at 11:35
2
$\begingroup$

Here is one interpretation of this question. We want to count rooted trees with ordered children in which each internal node has either 2 or 3 children.

Denote by $T_d$ the number of 2-3 trees of depth at most $d$, so $T_0 = 1$ (the tree consisting of a single node) and $T_1 = 3$ (the tree consisting of a a single node; a root with two children; a root with three children). More generally, a 2-3 tree of depth at most $d$ is either just a single node or consists of a root with two or three children, each of which is a 2-3 tree of depth at most $d-1$. Therefore $T_d = 1 + T_{d-1}^2 + T_{d-1}^3$.

Finally, the number of 2-3 trees of depth exactly $d$ is $T_d - T_{d-1}$. For example, the number of 2-3 trees of depth exactly 1 is $T_1 - T_0 = 3-1 = 2$.

$\endgroup$
2
  • $\begingroup$ So, in case of B-trees, where all leaves should be at the same level, it seems your analysis would lead to the recursion $B_0=1$, $B_d = B_{d-1}^2 + B_{d-1}^3$. (?) $\endgroup$ Nov 25 '17 at 14:17
  • $\begingroup$ Yes, this seems right. $\endgroup$ Nov 25 '17 at 14:28

Your Answer

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

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