A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Chapter 15Speeding 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, there’s a cost to this. As we’ve seen, even the fastest algorithms take O(N log N) time. So, if we are 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) ...