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 ...