Treap Removal: Exercise

  • Select the appropriate rotation type to rebalance a Treap after performing a removal.

Consider the following (max-heap) treap, where the keys are the letters and the priorities are the integers:

Exercise Show the result of removing the key T, including any necessary rotations.

Solution

After finding the node with key T we set its priority to $-1$:

We must now apply tree rotations to fix the max-heap order property. Among the children of T, the node with key Y has the highest priority. So we must apply a left rotation to bring Y above T:

Among the children of T, the node with key P has the highest priority. So we must apply a right rotation to bring P above T:

Notice at this point we can simply remove T (since it has only one child). If we were to follow the process completely, we would have to apply another left rotation to bring X above T:

We can easily remove the node with key T as it is a leaf now.