Mahmoud H.M. Evolution of Random Search Trees

Wiley-Interscience, 1991. — 330 p. — (Wiley Series in Discrete Mathematics and Optimization). — ISBN-10: 0471532282, ISBN-13: 978-0471532286.Since the advent of computer science as a discipline, several excellent books have been written on algorithms and their analysis. However, remarkably very few books have been dedicated to the probabilistic analysis of algorithms, even though the area has witnessed an avalanche of research. The purpose of this book is to fill this gap and bring together material that is scattered over tens of publications. We have chosen one facet of the theory of algorithms (search trees) and produced an exposition that explores certain analytical methods that have become popular in the analysis of algorithms; references are given whenever possible. Most of the results in this book about averages have appeared in Knuth's monumental three volumes The Art of Computer Programming, which were published in the late 1960s and early 1970s, but most of the results concerning probabilistic convergence and central limit theorems have only appeared in the last two decades.
The unifying theme in this book is the study of a distribution theory that underlies some classes of random trees suitable for use as data structures with a behavior of random growth that is almost as good as balanced trees. To this date, very little is known about the analysis of random trees in the presence of deletions. There are very few results that appear sporadically in the literature [for example, Culberson's A985) analysis of updates in binary search trees and the recent extension of these results by Culberson and Munro A989), Jonassen and Knuth's A987) complete, but very hard, analysis of sequences of updates in a binary search tree of size 3, and the recent extension by Baeza-Yates A989) to trees of size 4]. We thought that the inclusion of these results would make the theme of the book less coherent and, therefore, decided not to include them. The state of balanced trees is not in any better shape. Virtually nothing is known about distributions in classes of balanced search trees, like AVL trees and B trees, and this book does not contain them either. What the book does contain is the algorithms and analyses of random search trees grown by pure insertion.
It is hoped that this book will disseminate information concerning the probabilistic analysis of algorithms and that it will inspire many young scientists to contribute to this growing area and use its method in other facets of computer science. The book is aimed at professionals and students in the field of computer science and other fields where random tree-like models are sought. The material of this book could be taught in courses on data structures and algorithms with an emphasis on their analyses. The background assumed is one year in programming, one year in probability, and one semester in combinatorics or discrete mathematics. Arguments from real and complex analysis are used extensively, and we have tried to keep them simple. So that the reader is able to follow these arguments, no special background, other than prior exposure to a general introduction to functions of complex variables, is assumed.
Clarity of the presentation was one of our main concerns in writing this book. In several places in the book, long chains of derivation are used. In most cases we have chosen to keep the details for a smooth reading so that using this book does not become an exhausting mental exercise. On some occasions we replaced the original proofs with simpler ones. We chose the theorem-proof format for the book so that the results can be easily identified and that the book is structured in units that can be more or less read independently. The exercises vary from the very simple, just checking the reader's grasp of the basic definitions, to the very challenging, which may require that the reader mimic the method of an entire section of the book in a similar or different context. We refrained from classifying the exercise as easy and hard because, after all, it is a subjective measure. Nevertheless many of the exercises can be used for homework problems and some of the long exercises can be used for term papers or take-home examinations.Basic Tools.
Naturally Growing Binary Search Trees.
Search Trees with Higher Branching Factors.
Trees for Multidimensional Data.
Tries.
Digital Search Trees.