Chapter 6
These are the solutions to the .
-
As with a BST, we’d make the L a right child of the K. Since the L has a greater priority than its parent, the K, we don’t need to enter a fixing phase. Therefore, the treap will look like the tree after inserting the L.
-
As with the previous exercise, we start by inserting the L as the K’s right child. However, because the L has a priority that is less than any other node in the treap, we must rotate the L up the treap until it becomes the root. After all the rotations are made, the treap will look like this:
-
We delete the Q node by rotating it downward through the treap. Which child we rotate the Q with depends on which child has a lower priority than the other. In this case, the N’s priority of 60 is less than the V’s priority of 72, so we rotate the Q with the N.
After this happens, the Q becomes a leaf node, and we then simply pluck it off the treap. At the end of the day, the treap will look like this after the deletion:
