Optimal Multi-Way Search Trees
L. Gotlieb · SIAM Journal on Computing · 1981
Given a set of N weighted keys, $N + 1$ missing-key weights and a page capacity m, we describe an algorithm for constructing a multi-way lexicographic search tree with minimum cost. The program runs in time $O(N^3 m)$ and requires $O(N^2 m)$ storage locations. If the missing-key weights are zero, the time can be reduced to $O(N^2 m)$. A further refinement enables the factor m in the above costs to be replaced by log m.