Evolution of random search trees. (English) Zbl 0762.68033

Pure and Applied Mathematics. A Wiley-Interscience Series of Texts, Monographs and Tracts. Chichester etc.: John Wiley & Sons Ltd. (ISBN 0-471-53228-2). X, 324 p. (1992).
It is known that while it is relatively easy to state such basic characteristics of an algorithm as its worst- or best-case complexity, its probabilistic analysis is much more difficult. However, due to the fruitful research in the area useful tools and methods for probabilistic analysis of algorithms are known, though they are usually scattered over many various publications. The book provides a thoroughful exposition of such methods used there to the analysis of search tree data structures and algorithms.
The first chapter of the book is devoted to the overview of relevant basic notions and tools as generating functions, Mellin transform and some elements of the theory of probability. The rest of the book deals with the analysis of various search trees - binary and \(m\)-ary trees, quad trees, \(k-d\) trees, tries, and digital search trees. For all these tree structures corresponding procedures in Pascal are given, followed by detailed probabilistic analysis of both successful and unsuccessful search, extreme path length, and some other characteristics.
Clarity of the presentation together with many exercises make the book a useful tool for all professionals and students interested in the analysis of data structures and algorithms.


68Q25 Analysis of algorithms and problem complexity
68P05 Data structures
68-02 Research exposition (monographs, survey articles) pertaining to computer science