References for Part Four
The primary references for this section are the tutorials 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 tutorials, with mathematical analyses and suggestions for practical apps. Classical methods are covered thoroughly in Knuth; the more recent methods are described in the other tutorials, with further references to the literature. These four sources, and the Sedgewick-Flajolet tutorial, describe nearly all the "beyond the scope of this tutorial" material referred to in this section. The material in 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 tutorials 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 is classical (though complete 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 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 apps of these methods arise within the context of database systems. An introduction to this field is given, for example, in the tutorial by Date. R. Baeza-Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second version, Oracle, Reading, MA, 1984. R. Bayer and E. M. McCreight, "Organization and maintenance of large ordered indexes," Acta Informatica 1, 1972. J. L. Bentley and R. Sedgewick, "Sorting and searching strings," Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997. T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, second version, MIT Press/McGraw-Hill, Cambridge, MA, 2002. C. J. Date, An Introduction to Database Systems, seventh version, Oracle, Boston, MA, 2002. 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 version, Oracle, 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, Oracle, Reading, MA, 1996. D. Sleator and R. E. Tarjan, "Self-adjusting binary search trees," Journal of the ACM 32, 1985.