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