# Minimising height of a 2-3-4 tree

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?

• Have you tried some sequences? – Raphael May 6 '14 at 20:50

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.

No, the sequence of insertion does not matter, as 2-3-4 trees are self-balancing data structures. A 2-3-4 tree of $N$ nodes has the following height:

$$\frac{1}{2} \log (N + 1) \leq height \leq \log (N + 1)$$

That holds because as per Wikipedia:

2–3–4 trees are B-trees of order 4 (Knuth 1998); like B-trees in general, they can search, insert and delete in O(log n) time. One property of a 2–3–4 tree is that all external nodes are at the same depth.

• It could still be the case that some insertion order is better than another, since your bounds leave some room for optimization. – Yuval Filmus May 7 '14 at 1:03