Treap

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

  • Explain and trace the balancing operations of a Treap.
  • Explain the role of the priorities in rebalancing and the importance of being random.
  • Select the appropriate rotation type to rebalance a Treap after performing an insertion or removal.
  • Implement the core operations of an OrderedMap efficiently with a Treap.
  • Analyze the time/space efficiency of a Treap implementation approach for a Map.

Starter code for this chapter

This chapter does not have separate solution code because a homework is about implementing a treap.