The splay

tree is a tree

data structure type which has 0(n)

worst-case operation time, but is O(logn) for

amortized accesses.

The

basic concept of a splay tree is that for any tree operation (insert/delete/find/etc) the node which you wish to operate on is

rotated to the root while maintaining the

binary search tree property (i.e. all nodes to the left of node x are less than x, and all nodes to the right are greater than x)

This creates some interesting possible situations, unlike

AVL trees which enforce their O(logn) time complexity after every operation, splay trees take a more lazy approach. You might notice that under the conditions of a splay tree, it is possible for a node to be O(n) distance away from the

root, but an access to it is likely to balance the tree greatly. Considering that nodes around the node previously accessed are the most likely to be accessed "soon after", the amortized time complexity for general tree operations is very very attractive. In other words, the tree may be rather unbalanced at any given point, but after any series of operations it's like to become very

bushy. Also consider that if an operation is "good" for the bushiness of a tree, it's

*very* good, but if the operation is "bad" for the tree is doesn't unbalance it too much.

The question becomes, how do we

rotate these nodes up to the

root while maintaining the

binary search tree property? There are 3 types of rotations that are necessary to be able to get any node in any tree to the root.

a zig zag rotation: (which is actually the same as a

double AVL rotation)

g n
/ \ / \
p d p g
/\ -> / \ / \
a n a b c d
/\
b c

a zig zig rotation:

g n
/ \ / \
p d a p
/ \ -> / \
n c b g
/ \ / \
a b c d

and a zig rotation: (which is the same as an

AVL single rotation
p n
/ \ / \
n c -> a p
/ \ / \
a b b c