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. 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 (x is left, p is right). The tree is rotated on the edge between p and x, and then rotated on the resulting edge between x and g. 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: Splay the largest item in S. Now this item is in the root of S and has a null right child. 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: 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. Split the right subtree from the rest of the tree. Insertion To insert a value x into a splay tree: Insert x as with a normal binary search tree. when an item is inserted, a splay is performed. As a result, the newly inserted node x becomes the root of the tree. Alternatively: Use the split operation to split the tree at the value of x to two sub-trees: S and T. Create a new tree in which x is the root, S is its left sub-tree and T its right sub-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