= Solution
First perform <splaying> on the key to be deleted, making its node the <root of a tree>. Delete that root, leaving left and right <subtrees> $L,R$. If either is empty, return the other. Otherwise find the maximum key $m$ of $L$ by following right-child references, and perform <splaying> on $m$ within $L$. This makes $m$ the root of $L$ with an empty right <subtree>. Attach $R$ there. \b[The result is the original <splay tree> with exactly the selected key removed.] An unsuccessful lookup leaves the represented <set> unchanged.
For <algorithm correctness>, all keys of $L$ are smaller than the deleted key, and all keys of $R$ are larger. <Splaying> preserves the <binary search tree> property by the permitted assumption. Since $m$ is the maximum of $L$, it has no larger key within $L$; since every key of $R$ exceeds $m$, attaching $R$ as its right <subtree> preserves every ordering condition. All remaining keys occur once. This is the join-based deletion of a <splay tree>.<Self-Adjusting Binary Search Trees by Daniel Sleator and Robert Tarjan>[Author-hosted publication record and abstract: splay-tree search, insertion and deletion operations]{ref}
Back to article page
