Thinking Recursively with Java

10.2. Binary Search Trees

The enormous difference in the performance of the sorting algorithms from Chapter 7 offers a vivid illustration of the importance of algorithmic efficiency. Even with the best algorithms, however, sorting is time-consuming, especially when large amounts of data are involved. In many practical applications, it makes sense to avoid the cost of sorting a large list of items by making sure to insert each item into the correct position at the time you add it to the list. The cost of inserting an item in its proper sequence is larger than, for example, simply adding it to the end, but eliminating the need to sort the list at a later point offers a significant advantage. If nothing else, the cost of keeping the list sorted can be distributed over time, so that the program pays a little of that cost at each insertion rather than paying all at once the cost of sorting the entire list. Algorithms that distribute time-consuming activities over a series of individual operations are said to amortize the cost of those operations.

The task of keeping a list in sorted order as you add new items can be broken down into two distinct operations. The first step is to find the correct position for the new item. This step constitutes the search phase of the algorithm. Once you have found the correct position, the next step consists of inserting the new item in that position. This step constitutes the insert phase. The efficiency of these two phases turns out to depend dramatically ...