Mu-balancing M-way Search Trees

A recent paper by Stout and Warren describes an asymptotically optimal algorithm (using 𝛉(N) time and constant space) for the balancing of binary search trees on N vertices. This paper shows how to extend their algorithm to balance M-way search trees, M ⩾ 2, using O(MN) time and O(M) temporary work space (consisting essentially of one node of the tree). The time bound (at least) is asymptotically optimal in cases of practical interest. When the M-way tree is stored on disc as the directory of an indexed sequential file, the algorithm uses at most 6N disc accesses (for large M) and requires that at most three nodes of the tree be simultaneously available in main memory. Various options for implementation of the algorithm are discussed, which allow the user to influence certain characteristics of the final balanced tree; in particular, to balance using MU < M − 1 keys per node.