Editing Splay tree (section)

=== Deletion ===
To delete a node ''x'', use the same method as with a binary search tree:

* If ''x'' has two children:
** Swap its value with that of either the rightmost node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor).
** Remove that node instead.

In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree.

Alternatively:

* The node to be deleted is first splayed, i.e. brought to the root of the tree and then deleted.  leaves the tree with two sub trees. 
* The two sub-trees are then joined using a "join" operation.