Treap Insertion: Exercise
Consider the following (max-heap) treap, where the keys are the letters and the priorities are the integers:
Exercise Show the result of inserting the key M, including any necessary rotations. Assume the priority generated for the key M is 15.
Solution
We insert M following the insertion process of a regular BST (ignoring priorities):
We must now apply tree rotations to fix the max-heap order property. Since M is to the left of P, we apply a right rotation to bring M above P and P to the right of M:
Since the priority of M is larger than priority of T we must apply tree rotation again to bring M above T:
We must apply a rotation one last time; this time, however, we apply left rotation since M is to the right of J:
Notice the BST order property is maintained over the keys (letters) and the max-heap order property is maintained over the priorities (integers).