My interest in data structures was kindled in 1968, when Colin J. Bell, my tentative PhD supervisor, managed to complete the expected-case analysis of binary search trees under updates that performed fringe rebalancing. It was only in 1975, however, that I began to carry out research in the area of data structures and algorithms as a result of a long-term collaboration in formal-language theory with Hermann Maurer and Arto Salomaa. In parallel with that research, Hermann and I investigated a new class of balanced binary trees that we called neighbor trees. My interest in tree-like data structures took fire, and the flame continues to burn today.
Over the years my interest in data structures was fanned by collaborators, colleagues, and students. Without them this book would never have been written. In alphabetical order they are: Jon Bentley, Ricardo Baeza-Yates, Anne Brueggemann-Klein, Helen Cameron, Bernard Chazelle, Herbert Edelsbrunner, Vladimir Estivill-Castro, Gaston Gonnet, Ralf-Hartmut Gueting, Yoshihide Igarashi, Rolf Klein, Hans-Peter Kriegel, Yat-Seng Kwong, Tony Lai, Paul Larson, Ted Leslie, Michael Li, Ming Li, Heikki Mannila, David Matthews, Kurt Mehlhorn, Ian Munro, Naomi Nishimura, Otto Nurmi, Thomas Ottmann, Mark Overmars, Stott Parker, Darrell Raymond, Gregory Rawlins, Arny Rosenberg, Michael Schrapp, Bernhard Seeger, Raimund Seidel, Murray Sherk, Hannes Six, Eljas Soisalon-Soininen, Frank Tompa, Esko Ukkonen, Vijay Vaishnavi, Jan van Leeuwen, Emo Welzl, Peter Widmayer, and Chee Yap.
Six of these individuals deserve a special mention. Vladimir Estivill-Castro corrected and tested my Pascal subprograms and also obtained the simulation results; Paul Larson was a fount of wisdom about hashing methods; David Matthews provided the statistical approach to the length of test sequences discussed in Chapter 2; Bernhard Seeger tutored me about external data structures for multidimensional data, most of which was omitted; Murray Sherk gave valuable feedback about the amortized analysis of sequential search and splay trees; and Frank Tompa counseled me on the topic of abstract data types.
This text was a family project; without the continual encouragement, organization, and support of my wife Mary, and without the typesetting of Calvin and Charlton, it would never have seen the light of day. Anne Brueggemann-Klein gave selflessly of her TeXnical knowledge. (The original manuscript was prepared using Leslie Lamport's LaTeX and Donald Knuth's TeX.) The text was written while I was a fulltime faculty member in the Data Structuring Group, Department of Computer Science, The University of Waterloo, which provided an exciting environment that I will miss. Draft versions of the text were used on unsuspecting undergraduates at the University of Waterloo, many of whom provided constructive feedback.
Good reviewers are hard to find. I am grateful to Dan Hirschberg, Stan Kwasny, Tony Marsland, Chartel Martel, Jon Mauney, Bernard Moret, Gary Newell, Andrew Olson, Michael Quinn, Dana Richards, Hanan Samet, Maarten van Swaay, and Ralph Wilkerson, who gave unsparingly of their time in their critical evaluation of drafts of this book. A book is never finished, it is only published; therefore, I am solely responsible for all errors and omissions. Please send me your comments and corrections either in writing to: Department of Computer Science, Hong Kong University of Science & Technology, Clear Water Bay, Kowloon, Hong Kong, Canada, or by e-mail to dwood@cs.ust.hk or to dwood@csd.uwo.ca.
Keith Wollman was the CS editor at A-W who decided to undertake this project, and when he was promoted, Peter Gordon more than ably took over at short notice. Helen Goldstein, Assistant Editor, was a delight to work with. I am grateful to the three of them for their help and understanding. Lyn Dupre, the developmental editor, cut my manuscript into English prose with her sharp, yet gracious, pen. Finally, Helen Wythe and Denise Descoteaux nursed the book through the perils of production and marketing.
Dedication: To C.C. and M.
Derick Wood, January 14, 1993