Chapter 6
Randomized Treaps: Haphazardly Achieving Equilibrium

In the previous chapter, we looked at red-black trees and how they keep themselves balanced using a set of complex algorithms. We’re now going to take a look at another type of self-balancing tree known as a treap. Treaps can maintain balance as effectively as a red-black tree, but with algorithms that are way simpler. And as you’ll see, this simplicity is achieved through the power of … randomization.