Optimal multiway search trees for variable size keys

Abstract

Given a sequence of n keys of variable sizes, some optimal search trees are considered. Constructing optimal cost multiway search trees is NP-hard, although it can be done in pseudo-polynomial time 0(n³L) and space 0(n²L) where L is the page size limit. Optimal space multiway search trees are obtained in 0(n³) time and 0(n²logn) time and 0(nlogn) space. The monotonicity principle does not apply to the above cases. Finding optimal cost general B-trees is NP-hard. But, a general B-tree of height 2 and minimal root size can be constructed in 0(nlogn) time and 0(n) space. In addition, if its root is restricted to contain M keys then the time complexity increases to 0(n²M) This answers a conjecture by McCreight [11]