Dynamic Binary Search Trees
William E. Wright · 1978
This paper compares the performance of many algorithms designed to maintain balance in binary search trees. The algorithms are rated primarily in terms of execution speed, although weighted path length is also included. The investigation includes algorithms for height balanced trees, weight balanced trees, trees of bounded balance, and optimal trees, as well as some combination algorithms. Input to the algorithms consists of insert and search commands using given sets of keys with unequal but unknown probabilities. Other types of input are also considered. The best algorithms are shown to be the basic search algorithm which performs no rebalancing, and a combination algorithm.