Operations Using Splays

We can perform all the standard binary-search-tree operations in terms of splays.

• Find: Locate the node, splay it to the top. If node is not found, splay last found node to the top.
• Min: Find $-\infty$.
• Max: Find $\infty$.
• Successor: Find node. Compute min of right subtree. (Much easier!)
• Alternate insert: Find node. Find min in right subtree (or max in left subtree, depending on what was found). It will have no left (or right, respectively) child, and therefore a place for the new element.
• Delete: Find node. Find max of left subtree. It will have no right child, so make the right subtree the new right child.