= Splaying
In ordinary bottom-up <splaying>, locate the selected node by a <binary search tree> search and repeatedly move it toward the root. If its parent is the root, perform a <zig step>. Otherwise use a <zig-zig step> when the node and its parent occupy the same left/right directions, or a <zig-zag step> when their directions differ. Each <tree rotation> preserves the <inorder traversal> and hence the represented key order. The process ends with the selected key at the root. Unsuccessful access policies can instead move the last visited node to the root; arguments about successful calls should say the requested key exists.
Back to article page
