A Comparison of Tree-Balancing Algorithms

Several algorithms-height-balance (i.e. AVL
and extensions), weight-balance (i.e. BB and WB), 
and total restructuring-for building balanced binary search
trees are compared.  The criteria for comparison 
encompass theoretical aspects (e.g. path lengths) and implementation
independent and machine/algorithm-dependent 
measures (e.g. run time).  A detailed analysis of code is
also presented at a level believed to be language-and 
compiler-independent.  The quality of the resulting
trees and the overhead spent on building them are 
analyzed, and some guidelines are given for an efficient
use of the methods.  If insertion and subsequent 
queries are the only operations of in terest, then "pure"
AVL trees present the overall best qualities.

CACM May, 1977

Baer, J. L.
Schwab, B.

binary search trees, AVL trees, weight-balanced trees,
path length, analysis of algorithms, information 
storage and retrieval

3.7 3.72 3.74 5.31

CA770504 JB December 29, 1977  2:16 AM

2455	4	2968
2493	4	2968
2889	4	2968
2889	4	2968
2968	4	2968
2968	4	2968
3042	4	2968
2388	5	2968
2455	5	2968
2968	5	2968
2968	5	2968
2968	5	2968
3042	5	2968
2455	6	2968
2839	6	2968
2889	6	2968
2968	6	2968