Memory refresher/My understanding:
A 2-3 tree is a balanced search tree that allows two types of nodes.
-
2-node: Normal node with two children.
- LChild < Parent and RChild > Parent
-
3-node: Node with two parents and three children.
- Parent1 < Parent2
- LChild < Parent1, Parent1 < MChild < Parent2, RChild >Parent2
A 2-3 tree is always balanced, and grows when the root raises the height of the tree by one.
http://en.wikipedia.org/wiki/2%E2%80%933_tree
My question is then as follows,
given n distinct keys, how many different 2-3 trees can one construct?
My math skills are poor, so if anyone knows how I should “math” in order to approach an answer, then that would be awesome! 🙂
0
Let T[n] be the number of 2-3-trees with n keys. We have:
-
T[n]= sum withkfrom 1 tonofT[k - 1] * T[n - k], because we can make a 2-node with the keyk, with left tree with keys1, ..., k - 1and right tree with keysk + 1, ..., n. For each arrangement of the left tree, we have the arrangements of the right tree, so we must multiply the two. This counts the case when we’re dealing with 2-nodes; -
T[n]+= sum withkfrom 1 tonof sum withpfromk + 1tonofT[k - 1] * T[p - k - 1] * T[n - p]. This counts the case when we’re dealing with 3-nodes;
Base case is T[0] = 1.
0