Editing Splay tree (section)

=== Splaying ===
When a node ''x'' is accessed, a splay operation is performed on ''x'' to move it to the root. A splay operation is 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 it provides 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'').

There are three types of splay steps, each of which has two symmetric variants: left- and right-handed. For the sake of brevity, only one of these two is shown for each type. (In the following diagrams, circles indicate nodes of interest and triangles indicate sub-trees of arbitrary size.) The three types of splay steps 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, 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.

[[File:splay tree zig.svg|center|350px]]

'''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''. Zig-zig steps are the only thing that differentiate splay trees from the ''rotate to root'' method introduced by Allen and Munro<ref name="AllenMunro">{{harvnb|Allen|Munro|1978}}.</ref> prior to the introduction of splay trees.

[[Image:Zigzig.gif|center]]

'''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''.

[[Image:Zigzag.gif|center]]