References for Part Four

The primary references for this section are the books by Knuth; Baeza-Yates and Gonnet; Mehlhorn; and Cormen, Leiserson, and Rivest. Many of the algorithms covered here are treated in great detail in these books, with mathematical analyses and suggestions for practical applications. Classical methods are covered thoroughly in Knuth; the more recent methods are described in the other books, with further references to the literature. These four sources, and the SedgewickFlajolet book, describe nearly all the “beyond the scope of this book” material referred to in this section.

The material in Chapter 13 comes from the 1996 paper by Roura and Martinez, the 1985 paper by Sleator and Tarjan, and the 1978 paper by Guibas and Sedgewick. As suggested by the dates of these papers, balanced trees are the subject of ongoing research. The books cited above have detailed proofs of properties of red–black trees and similar structures, and references to more recent work.

The treatment of tries in Chapter 15 is classical (though C implementations are rarely found in the literature). The material on TSTs comes from the 1997 paper by Bentley and Sedgewick.

The 1972 paper by Bayer and McCreight introduced B trees, and the extendible hashing algorithm presented in Chapter 16 comes from the 1979 paper by Fagin, Nievergelt, Pippenger, and Strong. Analytic results on extendible hashing were derived by Flajolet in 1983. These papers are must reading for anyone wishing further information on external searching methods. Practical applications of these methods arise within the context of database systems. An introduction to this field is given, for example, in the book by Date.

R. Baeza-Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading, MA, 1984.

J. L. Bentley and R. Sedgewick, “Sorting and searching strings,” Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.

R. Bayer and E. M. McCreight, “Organization and maintenance of large ordered indexes,” Acta Informatica 1, 1972.

T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, 1990.

C. J. Date, An Introduction to Database Systems, sixth edition, Addison-Wesley, Reading, MA, 1995.

R. Fagin, J. Nievergelt, N. Pippenger, and H. R. Strong, “Extendible hashing—a fast access method for dynamic files,” ACM Transactions on Database Systems 4, 1979.

P. Flajolet, “On the performance analysis of extendible hashing and trie search,” Acta Informatica 20, 1983.

L. Guibas and R. Sedgewick, “A dichromatic framework for balanced trees,” in 19th Annual Symposium on Foundations of Computer Science, IEEE, 1978. Also in A Decade of Progress 1970–1980, Xerox PARC, Palo Alto, CA.

D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching, second edition, Addison-Wesley, Reading, MA, 1997.

K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Springer-Verlag, Berlin, 1984.

S. Roura and C. Martinez, “Randomization of search trees by subtree size,” Fourth European Symposium on Algorithms, Barcelona, September, 1996.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

D. Sleator and R. E. Tarjan, “Self-adjusting binary search trees,” Journal of the ACM 32, 1985.