Deletion and Joining

The most complicated (but still not very complicated) operation we perform on splay trees is deletion, which assumes the item to delete is present. To perform deletion, we first find the node to delete and splay it. We then remove the root, leaving us with a left and right subtree, and finally join theses two subtrees. Joining the two subtrees is actually nontrivial, so we will look at how it works now.

The operation of joining consists of merging two trees t1 and t2, assuming that all items of t1 <= items in t2. Joining consists of three steps; first, we splay the largest item of t1. This will leave t1 with no right child, meaning that we can now simply attach t2 as the right child of t1. The fact that we use this join operation after we have deleted the root gives us an advantage; we know that the element we just deleted is guaranteed to be >= every element of t1, meaning that performing a splay search for the deleted node in t1 will result in the largest element being splayed.