The construction of optimal multiway search trees and the monotonicity principle

Abstract

Given Nweighted keysN+1 missing-key weights and a branching factor t the application of dynamic programming yields algorithms for constructing optimal binary search trees (t = 2), optimal multi-way search trees (t>2), and optimal leaf search trees (or alphabetic code trees) with leaf weights only. The basic running time in all cases is O(N ³)(in terms of the number of keys), but it can be reduced to O(N ²) for binary search trees by a “monotonicity” principle which restricts the number of candidates for the root at each step in the construction. This principle can also be applied for multiway search trees when the missing-key weights are zero. However it does not extend to optimal multiway search trees in general, as we demonstrate; in particular, there is no monotonicity principle for alphabetic code trees, contrary to what is claimed in [5].

Keywords:

• Algorithms
• optimal multiway search trees
• dynamic programming

C.R. Categories:

• 3.73
• 3.74
• 4.34
• 5.25
• 5.42