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