AN ALGORITHM FOR BALANCING BINARY TREES
Abstract
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.
Description
Keywords
Computer Science