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