Given n distinct keys, how many different 2-3/Red-black trees can be constructed?

Question

Memory refresher/My understanding:

A 2-3 tree is a balanced search tree that allows two types of nodes.

1. 2-node: Normal node with two children.

   • LChild < Parent and RChild > Parent

2. 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! :)

Answer 1

Let T[n] be the number of 2-3-trees with n keys. We have:

• T[n] = sum with k from 1 to n of T[k - 1] * T[n - k], because we can make a 2-node with the key k, with left tree with keys 1, ..., k - 1 and right tree with keys k + 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 with k from 1 to n of sum with p from k + 1 to n of T[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.