Chapter 15
Speeding Up All the Things with Binary Search Trees

Sometimes, we may want to arrange our data in a specific order. For example, we may want an alphabetized list of names or a list of products in order of lowest price to highest.

While we can use a sorting algorithm such as Quicksort to arrange our data into perfect ascending order, it comes at a cost. As we’ve seen, even the fastest algorithms take O(N log N) time. So if we’re going to want our data sorted often, it would be sensible to always keep our data in sorted order in the first place so that we never need to resort it.

An ordered array is a simple but effective tool for keeping data in order. It’s also fast for certain operations, as it has O(1) reads and O(log N) search (when using binary search).

However, ordered arrays have a drawback.

When it comes to insertions and deletions, ordered arrays are relatively slow. Whenever a value is inserted into an ordered array, we first shift all greater values one cell to the right. And when a value is deleted from an ordered array, we shift all greater values one cell to the left. This takes N steps in a worst-case scenario (inserting into or deleting from the first cell of the array), and N / 2 steps on average. Either way, it’s O(N), and O(N) is relatively slow for a simple insertion or deletion.

Now, if we were looking for a data structure that delivers all-around amazing speed, a hash table is a great choice. Hash tables are O(1) for search, insertion, and deletion. However, they don’t maintain order, and order is what we need for our alphabetized-list application.

So what do we do if we want a data structure that maintains order yet also has fast search, insertion, and deletion? Neither an ordered array nor a hash table is ideal.

Enter the binary search tree.