Splay Trees: The Pretty Much Perfect Binary Search Tree

Splay trees are very simple as far as structure. A splay tree a binary search tree, so each node has a key, maybe a left child, and maybe a right child. There's no subtree height, ranking info, or anything else. It's pretty simple. It's the splay algorithm that gives the splay tree its magical properties.

The splay algorithm moves (splays) an accessed node (or insertion candidate's parent) to the root of the tree. So the next time it's accessed, it will be close to the root, or even the root. Values are splayed to root on insert, access, and delete (when it gets lopped off).

Splaying moves the node to the root through a sequence of subtree rotations. That's it.

The by-product of splaying is that the tree adjusts itself to common requests. However, there's no guarantee that the tree will stay balanced. It stays roughly balanced. It can get greatly out of whack, but still guarantees O(log n) amortized performance.

This snippet from an MIT lecture on splay trees ends with some surprising claims and proofs of the splay tree's capabilities.

The last ten minutes is great. I've jumped to the spot:

Here's the algorithm that moves the given value to the root of the tree:

spltree_node* splay(spltree_node* x, int value) {  
  spltree_node temp, *l, *r, *y;

  temp.left = temp.right = NULL;
  l = r = &temp;

  for (;;) {
    if (value < x->value) {
      if (x->left == NULL) break;
      if (value < x->left->value) {   // rotate right
        y = x->left;
        x->left = y->right;
        y->right = x;
        x = y;
        if (x->left == NULL) break;
      }
      r->left = x;                    // link right
      r = x;
      x = x->left;
    } else if (value > x->value) {
      if (x->right == NULL) break;
      if (value > x->right->value) {  // rotate left
        y = x->right;  
        x->right = y->left;
        y->left = x;
        x = y;
        if (x->right == NULL) break;
      }
      l->right = x;                   // link left
      l = x;
      x = x->right;
    } else {
      break;
    }
  }

  l->right = x->left;
  r->left = x->right;
  x->left = temp.right;
  x->right = temp.left;

  return x;
}