A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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, 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 re-sort 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 ...