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.