Abstract

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 …