# Splay Trees

### A self-adjusting search tree

The demo below implements the operations **insert**, **delete**
and **locate** on splay trees. Each of the operations
is performed almost as
in a standard binary search tree,
except that after each, a **splay** is
performed at the node that has been accessed.
A splay at a selected node
essentially drags it to the root of the tree, through a sequence of
rotations. These rotations are performed in pairs
(pictured as )
through all of this node's ancestors.
The algorithm is described further here.

Informally, one can think of the splay trees as implementing a sort of
LRU policy on tree accesses: the most recently accessed elements are
pulled closer to the root; and indeed, one can show that the tree
structure adapts dynamically to the elements accessed, so that the
least frequently used elements will be those furthest from the root.
But remarkably, although no explicit balance conditions are imposed
on the tree, each of these operations can be shown to use time
*O(lg n)* on an *n*-element tree, in an amortized sense.

This demo starts you with a very unbalanced tree.
Also check out the alternate display options from the menus
below.

The Source.