A Maximally Parallel Balancing Algorithm for Obtaining Complete Balanced Binary Trees
Abha Moitra, S. S. Iyengar · IEEE Transactions on Computers · 1985
We present a new iterative balancing algorithm for binary trees of size N = 2n-1 by exploiting the similarity of pointer restructuring at each level. We also extract parallelism from this algorithm to yield a constant time complexity balancing algorithm for an N-processor configuration. This achieves the theoretical limit of speedup possible.