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

3.5.3 Profiling Running Time

3.5.4 Profiling Memory Usage

3.5.5 Conclusions

3.6 Summary