Derivation of a parallel algorithm for balancing binary trees

A recent trend in program methodologies is to derive efficient parallel programs from sequential programs. This study explores the question of transforming a sequential algorithm into an efficient parallel algorithm by considering the problem of balancing binary search trees. The derivation of the parallel algorithm makes use of stepwise refinement. The authors first derive a new iterative balancing algorithm that exploits the similarity of point restructuring required at all the nodes at the same level. From this they derive a parallel algorithm that has time complexity O(1) on an N-processor configuration. This achieves the theoretical limit of speedup possible in a multiprocessor configuration.