AN ALGORITHM FOR BALANCING BINARY TREES
A.W. Colijn · Libraries and Cultural Resources (University of Calgary) · 1981
An algorithm is presented for balancing binary trees; the algorithm re-structures in place any tree of arbitrary structure, to produce a tree with the property that the numbers of left and right descendants of any node differ by at most one. The algorithm is convenient to use, and it is fast; the time required to balance a tree varies linearly with the number of nodes. Experimental results and variations of the basic algorithm are discussed.