Course contentsShow
← Computer Science
Lesson 573 of 2,87213. Balanced TreesFree lesson

Splay Tree Deletion

Deleting nodes from splay trees using splay operations and tree joining techniques.

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:

  1. Splay the target key to make it the root (or splay the closest key if k doesn't exist)
  2. If k isn't found, you're done—the tree is already adjusted
  3. If k is at the root, remove it, leaving two subtrees: L (left) and R (right)
  4. Join the subtrees:
    • Find the maximum element in L by splaying it to L's root
    • This node has no right child (it's the max!)
    • Attach R as its right child

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.