Splaying

When a node $x$ is accessed, a splay operation is performed on $x$ to move it to the root. To perform a splay operation we carry out a sequence of splay steps, each of which moves $x$ closer to the root. By performing a splay operation on the node of interest after every access, the recently accessed nodes are kept near the root and the tree remains roughly balanced, so that we achieve the desired amortized time bounds.

Each particular step depends on three factors:

• Whether $x$ is the left or right child of its parent node, $p$,
• whether $p$ is the root or not, and if not
• whether $p$ is the left or right child of its parent, $g$ (the grandparent of $x$).

It is important to remember to set $gg$ (the great-grandparent of $x$) to now point to $x$ after any splay operation. If $gg$ is null, then $x$ obviously is now the root and must be updated as such.

There are three types of splay steps, each of which has a left- and right-handed case. For the sake of brevity, only one of these two is shown for each type. These three types are:

Zig step: This step is done when $p$ is the root. The tree is rotated on the edge between $x$ and $p$. Zig steps exist to deal with the parity issue and will be done only as the last step in a splay operation and only when $x$ has odd depth at the beginning of the operation (see fig. ).

Figure: Zip Step.

Zig-zig step: This step is done when $p$ is not the root and $x$ and $p$ are either both right children or are both left children. The picture below shows the case where $x$ and $p$ are both left children. The tree is rotated on the edge joining $p$ with its parent $g$, then rotated on the edge joining $x$ with $p$. Note that zig-zig steps are the only thing that differentiate splay trees from the rotate to root method introduced by Allen and Munro prior to the introduction of splay trees (see fig. ).

Figure: Zip zig.

Zig-zag step: This step is done when $p$ is not the root and $x$ is a right child and $p$ is a left child or vice versa. The tree is rotated on the edge between $p$ and $x$, and then rotated on the resulting edge between $x$ and $g$.

Figure: Zip zag.

Join. Given two trees $S$ and $T$ such that all elements of $S$ are smaller than the elements of $T$, the following steps can be used to join them to a single tree:

1. Splay the largest item in $S$. Now this item is in the root of $S$ and has a null right child.
2. Set the right child of the new root to $T$.

Split. Given a tree and an element $x$, return two new trees: one containing all elements less than or equal to $x$ and the other containing all elements greater than $x$. This can be done in the following way:

1. Splay $x$. Now it is in the root so the tree to its left contains all elements smaller than $x$ and the tree to its right contains all element larger than $x$.
2. Split the right subtree from the rest of the tree.

Insertion. To insert a value $x$ into a splay tree:

1. Insert $x$ as with a normal binary search tree.
2. when an item is inserted, a splay is performed.
3. As a result, the newly inserted node $x$ becomes the root of the tree.

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). Then 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.