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
-
Do an SPT search for the node to be deleted;
this will cause the node, if found, to be splayed to the root.
-
Remove the root node, leaving the two child trees (TL and TR).
-
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.
-
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.