[Solved]: Minimising height of a 2-3-4 tree

Problem Detail: 

I'm wondering how a set of keys could be assigned to nodes in a 2-3-4 tree in order to minimize the height of the tree?

Does the sequence of insertion matter with 2-3-4 trees?

Asked By : Jack

Answered By : FrankW

The insertion order is relevant for the height of the tree. Inserting (in this order) 1,2,3,4,5,6,7,8 gives a tree of height 3, while inserting these keys in the order 1,3,4,6,7,8,2,5 gives a tree of height 2.

In order to create a tree of minimal height, you can place the keys with ranks $\lceil \frac{n}4\rceil$, $\lceil \frac{n}2\rceil$, and $\lfloor \frac{3n}4\rfloor$ in the root, partition the remaining keys accordingly into the subtrees and apply the this recursively to each of the subtrees. Depending on the number of keys, you may have to shift a few keys around between leaves and their parents to make sure that all leaves are at the same level.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24464