Treap removal deletes a matching key while preserving both the binary-search-tree ordering and heap invariants. It first searches for the key; if absent, it returns false. If found, the node is pushed downward until it becomes a leaf, then disconnected. The approach treats the target as having the lowest priority and uses rotations to move higher-priority children above it. section 3.3.5
The implementation proceeds through these cases:
- Search for the key and return false when no node matches. section 3.3.5
- Remove the sole root directly by setting the treap root to null. section 3.3.5
- While the target has children, select its higher-priority child and rotate that child upward: rotate right for the left child, otherwise rotate left for the right child. section 3.3.5
Removing “Butter”
After searching for “Butter,” choose its highest-priority child, rotate that child above the target, and repeat while the target still has a child. Once “Butter” reaches a leaf, unplug it without violating the treap’s invariants. section 3.3.5
