11 Binary search trees: A balanced container
In this chapter
- modeling hierarchical relationships with trees
- binary, ternary, and n-ary trees
- introducing data constraints into binary trees: binary search trees
- evaluating the performance of binary search trees
- discovering how balanced trees provide better guarantees
This chapter marks a shift from the previous few chapters, where we focused on containers. Here, we discuss trees, which is a data structure—or rather a class of data structures! Trees can be used to implement several abstract data types, so unlike the other chapters, we won’t have an ADT section here. We’ll go straight to the point, describing trees, and then focus on one particular kind of tree—the binary search tree (BST). We’ll describe what trees do well and how we can make them work even better.
What makes a tree?
In chapter 6, we discussed linked lists, our first composite data structure. The elements of a linked list, its nodes, are themselves a minimal data structure. Linked lists are based on the idea that each node has a single successor and a single predecessor—except for the head of the list, which has no predecessor, and the tail of the list, which has no successor.
However, things are not always so simple, and the relationships are more intricate. Sometimes, instead of a linear sequence, we need to represent some kind of hierarchy, with a single, clear starting point, but then with different paths branching out from each node.