3 Treaps: Using Randomization to Balance Binary Search Trees

 

This chapter covers

  • Problem: index data according to multiple criteria
  • The Treap data structure
  • Problem: keep a binary search tree balanced
  • Using treaps to implement balanced binary search trees (BST)
  • Randomized Treaps (RT)
  • Comparing plain BSTs and RTs

In chapter 2 we have seen how it is possible to store elements and retrieve them based on their priorities by using heaps, and how we can improve over binary heaps by using a larger branching factor.

Priority queues are especially useful when we need to consume elements in a certain order from a dynamically changing list (like the list of tasks to run on a CPU), so that at any time we get the next element (according to a certain criterion), remove it from the list and (usually) not worry anymore about fixing anything for the other elements. The difference with a sorted list is that we only go through elements in a priority queue once, and the elements already removed from the list won’t matter for the ordering anymore.

3.1            Problem: Multi-Indexing

3.1.1                     The Gist of the Solution

3.2            Solution: Description and API

3.3            Treap

3.3.1                     Rotations

3.3.2                     A Few Design Questions

3.3.3                     Implementing Search

3.3.4                     Insert

3.3.5                     Delete

3.3.6                     Top, Peak, Update

3.3.7                     Min, Max

3.3.8                     Performance Recap

3.4            Applications: Randomized Treaps

3.4.1                     Balanced Trees

3.4.2                     Introducing Randomization

3.4.3                     Applications of Randomized Treaps

3.5            Performance Analysis and Profiling

3.5.1                     Theory: Expected Height

3.5.2                     Profiling Height