A right rotation rearranges a binary-search-tree subtree so its left child becomes the subtree root. It preserves key ordering while changing parent and child links. section 3.3.1
Apply the rotation to a left child X of parent Y:
- Reconnect X to Y’s former parent, or make X the tree root when Y had no parent. section 3.3.1
- Move X’s right subtree to become Y’s left subtree; its keys remain within Y’s left-side range. section 3.3.1
- Attach Y as X’s right child, restoring the rotated subtree without violating binary-search-tree ordering. section 3.3.1
Listing 3.2 Right rotation
function rightRotate(treap, x) #1
if x == null or isRoot(x) then #2
throw
y ← x.parent #3
throw-if y.left != x #4
p ← y.parent #5
if p != null then #6
if p.left == y then #7
p.setLeft(x) #8
else
p.setRight(x)
else #9
treap.root ← x
y.setLeft(x.right) #10
x.setRight(y) #11
Use the pseudocode to check root handling, parent replacement, subtree transfer, and the required left-child relationship. section 3.3.1
