Binary search trees - Data Structures and Problem Solving Using Java - page 770

analytical evidence (but not a complete proof for the general case of inter-
mixed insertions and deletions). The claim that the deepest node in a random
binary search tree is three times deeper than the average node is proved in
[11]; the result is by no means simple.
AVL trees were proposed by Adelson-Velskii and Landis [1]. A dele-
tion algorithm is presented in [19]. Analysis of the average costs of search-
ing an AVL tree is incomplete, but some results are contained in [20]. The
top-down red-black tree algorithm is from [15]; a more accessible descrip-
tion is presented in [21]. An implementation of top-down red-black trees
without sentinel nodes is given in [12]; it provides a convincing demonstra-
tion of the usefulness of nullNode . The AA-tree is based on the symmetric
binary B-tree discussed in [4]. The implementation shown in the text is
adapted from the description in [2]. Many other balanced search trees are
described in [13].
B-trees first appeared in [5]. The implementation described in the
original paper allows data to be stored in internal nodes as well as in
leaves. The data structure described here is sometimes called a B + -tree.
Information on the B*-tree, described in Exercise 19.14, is available in [9]. A
survey of the different types of B-trees is presented in [6]. Empirical
results of the various schemes are reported in [14]. A C++ implementation
is contained in [12].
1. G. M. Adelson-Velskii and E. M. Landis, “An Algorithm for the Organi-
zation of Information,” Soviet Math. Doklady 3 (1962), 1259-1263.
2. A. Andersson, “Balanced Search Trees Made Simple,” Proceedings of
the Third Workshop on Algorithms and Data Structures (1993), 61-71.
3. R. A. Baeza-Yates, “A Trivial Algorithm Whose Analysis Isn't: A Contin-
uation,” BIT 29 (1989), 88-113.
4. R. Bayer, “Symmetric Binary B-Trees: Data Structure and Maintenance
Algorithms,” Acta Informatica 1 (1972), 290-306.
5. R. Bayer and E. M. McCreight, “Organization and Maintenance of Large
Ordered Indices,” Acta Informatica 1 (1972), 173-189.
6. D. Comer, “The Ubiquitous B-tree,” Computing Surveys 11 (1979), 121-137.
7. J. Culberson and J. I. Munro, “Explaining the Behavior of Binary Search
Trees Under Prolonged Updates: A Model and Simulations,” Computer
Journal 32 (1989), 68-75.
8. J. Culberson and J. I. Munro, “Analysis of the Standard Deletion Algo-
rithm in Exact Fit Domain Binary Search Trees,” Algorithmica 5 (1990),
295-311.