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.