Height balance distribution of search trees (Q1183418)

Local balancing in binary search trees is a heuristic applied to the frings of a tree. This technique lies between no balance (binary search trees) and rigid balance disciplines (height \textit{G. M. Adel'son- Vel'skii} and \textit{E. M. Landis} [An algorithm for the organization of information, Dokl. Akad. Nauk SSSR 146 (2), 263-266 (1962); English translation in Soviet Math. Dokl. 3, (1962) 1259-1263 (1962)], weight, or internal path balance). The basic is to keep the fringe of a tree balanced using local rotations. The origin of this heuristic can be traced to the work of \textit{C. Bell} [An investigation into the principles of the classification and analysis of data on an automatic digital computer, Ph. D. Thesis, Leeds University (1965)] and \textit{W. A. Walker} and \textit{D. Wood}[Comput. J. 19 (4), 322-325 (1976; Zbl 0341.68026)]. We study the height balance distribution of binary search trees (BSTs), with or without local/global balancing. We extend this study to locally balanced search trees and analyze a generalized heuristic for local balance in binary search trees. From this we obtain the expected number of comparisons in successful and unsuccessful searches, and we also determine the optimal heuristic for this schema when uniform, random keys are used. We also propose an implementation, which in the worst case uses only one pointer per key. Furthermore we study the balance distribution of AVL trees and a variant of them. We also include exact results for small AVL trees.