2

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

2

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.

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.