Beginning Algorithms

Chapter 10. Binary Search Trees

Chapter 9 introduced a binary search algorithm that enables you to efficiently search a sorted array list. Unfortunately, a binary search algorithm suffers when it comes to insertions and deletions as elements are copied around. Binary search trees, on the other hand, can achieve the O(log N) average search/insert/delete time of the binary search algorithm without the associated overhead. By storing values in a tree structure — where values are linked together — it's easy to insert new values and remove deleted ones.

Unlike most other chapters, this chapter is largely theoretical. That is, you don't work through any practical examples because binary search trees actually form the basis for many other data structures. This chapter is confined to a discussion about how binary search trees work, rather than how you use them in practice. In later chapters on sets (Chapter 12), maps (Chapter 13), and B-Trees (Chapter 15), you'll see how these other data structures are built using the code in this chapter as a template.

This chapter discusses the following topics:

• Characteristics that make binary search trees so interesting

• Various binary search tree operations and how each works

• How the ordering of data can affect performance

• A simple technique for restoring the balance after insertion and deletion

• How to test and implement a nonbalancing binary search tree

Understanding Binary Search Trees

Chapter 2 mentioned how a file system is often referred to as a directory ...