Splay Tree Algorithm

The splay tree algorithm is a self-adjusting procedure applied to a binary search tree after every access, called splaying, that moves the node just accessed all the way up to the root of the tree through a sequence of rotations, so an item used recently stays quick to reach again. Splaying combines three rotation patterns depending on the accessed node's position relative to its parent and grandparent, called zig, zig-zig and zig-zag, applied repeatedly until the target node reaches the root. Because every access reorganizes the tree around whatever was just used, a splay tree needs no separate balance information and no knowledge of the access pattern in advance, yet it still guarantees that any sequence of operations completes in time that on average is proportional to the logarithm of the tree's size, and it can do noticeably better than that bound on access patterns with strong locality, such as repeatedly reusing a small subset of items. Daniel Sleator and Robert Tarjan invented the splay tree and its splaying algorithm in 1985.