Binary Search Trees in Action

We’ve seen that binary search trees boast efficiencies of O(log N) for search, insertion, and deletion, making it an efficient choice for scenarios in which we need to store and manipulate ordered data. This is particularly true if we’ll be modifying the data often, because while ordered arrays are just as fast as binary search trees when searching data, binary search trees are significantly faster when it comes to inserting and deleting data.

For example, let’s say we’re creating an application that maintains a list of book titles. We’d want our application to have the following functionality:

• Our program should be able to print the list of book titles in alphabetical order.

• Our program should allow for constant changes to the list.

• Our program should allow the user to search for a title within the list.

If we didn’t anticipate that our book list would be changing that often, an ordered array would be a suitable data structure to contain our data. However, we’re building an app that should be able to handle many changes in real time. If our list had millions of titles, a binary search tree may be a better choice.

Such a tree might look something like this:

Here, the titles are positioned based on their alphabetical order. A title that comes earlier in the alphabet is considered a “lower” value, while titles that come later are “greater” values.