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

Log in or register to write something here or to contact authors.