Online Algorithms and Self-Balancing Trees

In Volume 1, Chapter 15, I noted that the primary benefit of BSTs is that they maintain data in order while also providing fast searching, insertion, and deletion. While hash tables are faster than BSTs when it comes to searching, insertion, and deletion, hash tables do not maintain any order. So, if you want ordered data that is also decently fast when it comes to the other operations, BSTs are a fantastic solution.

However, as I mentioned, BSTs have a worst-case scenario to contend with. When we insert values into a BST in order, the BST becomes imbalanced. Here’s a quick refresher.

If we build a tree by inserting data in the order of 3, 2, 4, 1, 5, we get this BST:

Beautiful. It’s as balanced as my dad’s checkbook. However, if we insert the data in perfect order, namely, 1, 2, 3, 4, 5, we get:

This BST is imbalanced and is as slow as a linked list for searching, insertion, and deletion. In fact, it pretty much is a linked list.

Earlier, in Chapter 3, , we developed a simple solution for this problem—we randomized the data! That is, before building the BST, we shuffled all the data, making it highly unlikely that the data will be inserted in order. But here’s the thing: this is a great solution for some applications, but it doesn’t satisfy all applications.

The randomized solution only works if we have all the data upfront before we begin building our BST. That is, say that we have an array of integers ready to be converted into a BST. Indeed, all we have to do is shuffle the data beforehand and, the BST is likely to be balanced when we build it.

But now say that we don’t have all the data in front of us. For example, perhaps we’re building and maintaining our BST over a long period of time. Suppose that our app receives its first integer at 1:00 and creates the initial BST. Then, at 2:00, we receive another integer and add it to the BST. At 3:00, we receive another integer and insert it into our tree.

In such a scenario, we don’t have the ability to randomize the data before we insert it into the tree because we don’t have all the data before creating the tree. The tree has already been built, and if we now receive a new integer, there’s no way to shuffle that integer together with the data already in the tree. In such a case, if our application receives ordered data, our BST will be imbalanced.

Online Algorithms

This is an example of an online algorithm, which is an algorithm that deals with data that is received in bits and pieces over an extended (and possibly infinite) period of time. The term “online” here can be a bit misleading, as it sounds like it has something to do with the Internet. It does not. In this context, “online” simply means that the data is still arriving, and we have to run an algorithm now, even though we don’t have all the data yet. In other words, an online algorithm is an algorithm that has to process data that is continually arriving.

You saw an example of an online algorithm in the previous chapter. Caches and their associated algorithms often process data that’s received over a period of time.

Conversely, an offline algorithm is one that only begins working once it has all the data in hand. Most of the algorithms we’ve dealt with before fall under this category.

So, with regard to BSTs, if they need to be “online” and process data continually as it comes in, randomization is not a solution. However, there’s another solution. It’s called the self-balancing tree.

Self-Balancing Trees

A self-balancing tree is one that, well, balances itself! As data is inserted or deleted, the tree rearranges its nodes so that the tree remains balanced or at least reasonably so.

Here’s a straightforward example of a self-balancing tree that you should never, ever use. I’m making it up off the top of my head to make a point. I call it The Phoenix Tree.

The Phoenix Tree is a BST that executes the following steps any time we insert or delete data:

1. The tree copies all of its own data into an array.
2. It shuffles the array.
3. It (figuratively) burns the original tree down to the ground and rebuilds the entire tree from scratch using the randomly ordered data.

Out of the ashes of the old tree emerges a new one. Because we’ve randomized the data before building the tree anew, there are good odds that the tree will be decently balanced. So, it’s fairly easy to make a self-balancing tree. The tricky part, though, is to make a self-balancing tree that is efficient.

The Phoenix Tree is—with no offense to phoenixes—an efficiency disaster. After all, we’re constantly rebuilding the entire tree from scratch. To put it in Big O terms: inserting into The Phoenix Tree takes at least O(N) time since we process all N elements each time we insert a single item. Compare this with a regular BST, where insertion is a speedy O(log N).

What we need to do is develop a self-balancing tree that doesn’t just work, but is also efficient.