)
through all of this node's ancestors.
The algorithm is described further here.
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.