Preface

Early in 1998, I wanted an AVL tree library for use in writing GNU PSPP. At the time, few of these were available on the Internet. Those that were had licenses that were not entirely satisfactory for inclusion in GNU software. I resolved to write my own. I sat down with Knuth's The Art of Computer Programming and did so. The result was the earliest version of libavl. As I wrote it, I learned valuable lessons about implementing algorithms for binary search trees, and covered many notebook pages with scribbled diagrams.

Later, I decided that what I really wanted was a similar library for threaded AVL trees, so I added an implementation to libavl. Along the way, I ended up having to relearn many of the lessons I'd already painstakingly uncovered in my earlier work. Even later, I had much the same experience in writing code for right-threaded AVL trees and red-black trees, which was done as much for my own education as any intention of using the code in real software.

In late 1999, I contributed a chapter on binary search trees and balanced trees to a book on programming in C. This again required a good deal of duplication of effort as I rediscovered old techniques. By now I was beginning to see the pattern, so I decided to document once and for all the algorithms I had chosen and the tradeoffs I had made. Along the way, the project expanded in scope several times.

You are looking at the results. I hope you find that it is as useful for reading and reference as I found that writing it was enjoyable for me. As I wrote later chapters, I referred less and less to my other reference books and more and more to my own earlier chapters, so I already know that it can come in handy for me.

Please feel free to copy and distribute this book, in accordance with the license agreement. If you make multiple printed copies, consider contacting me by email first to check whether there are any late-breaking corrections or new editions in the pipeline.