Binary Search Tree Randomization

So far, we’ve looked at various types of randomized algorithms. Generating a random number is perhaps the “ultimate” randomized algorithm, as it is what powers all of the other randomized algorithms. Shuffling an array is also a randomized algorithm since it uses randomization to jumble the order of the array’s values.

Randomized Quicksort, another randomized algorithm we’ve seen, uses randomization for the sake of creating order efficiently. Although the algorithm’s goal is to create order rather than randomness, it is still considered a randomized algorithm since it utilizes randomization somewhere within the algorithm’s steps. In fact, this utilization of randomization can be useful in any scenario where having sorted data would be to our disadvantage. Another example of this pops up with regard to the building of binary search trees.

I noted back in Volume 1, Chapter 15, that the order of our data could significantly affect the formation of our tree. For example, if we want to build a tree out of the data [3, 2, 4, 1, 5] by pulling out each value from left to right and inserting them into the tree, we get this nicely balanced tree:

However, if those same values were in the order [1, 2, 3, 4, 5], our tree would come out like this:

This tree is essentially nothing more than a linked list and loses all the efficiency advantages that a binary search tree has over a linked list. So, this is another instance where sorted data works to our disadvantage.

However, if we have reason to suspect that our data might be in sorted order, we can do our little trick of preshuffling the array before building the tree! The shuffling of an array will greatly reduce the odds that the array is in sorted order.