Alternate delete for a splay tree

Recall that insert in a Splay Tree (SPT) is a Binary Search Tree (BST) insert followed by a splay operation; also, a SPT search is a BST search followed by a splay. Similarly, a SPT delete is a BST delete followed by a splay.

However, we have another way to do an SPT delete that does not require implementation of the BST delete. You may wish to implement your SPT delete this way:

SPT Delete steps

  1. Do an SPT search for the node to be deleted; this will cause the node, if found, to be splayed to the root.
  2. Remove the root node, leaving the two child trees (TL and TR).
  3. Take the TL child subtree and do findMax on it; splay that node to the root of TL. Recall that the max element in a BST is found from the root by going down all right child links until you hit a node with no right child.
  4. Now that the max element of TL is at the root, it has no right child link (since all elements in the subtree are smaller than it, they are all down the left child link). So make TR the right child link of the root of TL.
Note that the last 2 steps above could be done symmetrically with the right child tree TR and findMin.