Wrapping Up

Randomized treaps are a great example of a randomized data structure and, more importantly, a great example of how effective randomization is in simplifying algorithms. Red-black trees are notorious for making people’s heads spin, and yet treaps achieve similar results with insertion and deletion algorithms that require considerably fewer steps and conditions. We looked at some practical applications of red-black trees in the previous chapter, and randomized treaps can be used wherever red-black trees can.

In the next chapter, we’re going to take a slight detour from the theme of randomization. Because we’re already dealing with self-balancing trees, I want to introduce you to another such tree known as the B-tree. Besides being extremely prevalent in all sorts of applications, this topic will open up an entirely new class of problems and algorithms—and disrupt the way we think about time complexity in general.

I’ll see you there.