Splay Tree Deletion
What you'll learn: How to delete nodes from a splay tree by combining splaying operations with tree-joining techniques.
The Core Idea
Deleting from a splay tree is more involved than insertion because you must both remove a node and maintain the self-adjusting property. The elegant solution uses splaying twice: first to bring the target node to the root, then to reorganize what remains.
The Deletion Process
When deleting a node with key k:
- Splay the target key to make it the root (or splay the closest key if
kdoesn't exist) - If
kisn't found, you're done—the tree is already adjusted - If
kis at the root, remove it, leaving two subtrees:L(left) andR(right) - Join the subtrees:
- Find the maximum element in
Lby splaying it toL's root - This node has no right child (it's the max!)
- Attach
Ras its right child
- Find the maximum element in
Why This Works
Think of it like removing the CEO of a company: you promote the highest-ranking person from the left division to CEO, then place the entire right division under them. The splay operation on the max element ensures it becomes L's root with an empty right slot—perfect for attaching R.
The splaying during deletion also maintains the self-adjusting behavior: frequently accessed elements still migrate toward the root over time.
Alternative Approach
Some implementations splay the predecessor or successor instead of finding the max in L, but the principle is identical—splay to create a convenient connection point.
Key Takeaway: Splay tree deletion combines two splay operations (one to move the target to the root, one to join remaining subtrees) to maintain the self-adjusting structure while removing nodes efficiently.