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 in order to rebalance a Treap after an operation (insert, remove) is performed.
• 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