Definition: Splay tree

A splay tree is a self-balancing binary search tree intended to provide quick access to frequently accessed items in the tree. The tree performs key functions such as insert, search, and delete in $O(log\space n)$ amortized time. A splay tree performs these basic operations in combination with the splay operation.

Splaying involves rearranging the tree to bring a particular element to the root of the tree. This is typically done using the standard binary search tree (BST) operation in combination with tree rotations to bring the particular element to the root of the tree. These rotations do not change the BST property of the tree.

Advantages

Splaying ensures that frequently accessed elements stay near the root of the tree so that they are easily accessible. By staying near the top of the tree, the tree can benefit from the locality of referenceprocessors can optimize for information that is frequently accessed.
The average case performance of splay trees is comparable to other fully-balanced trees: $O(log\space n)$ .
Splay trees do not need bookkeeping data; therefore, they have a small memory footprint.

Disadvantages

The major disadvantage of splay trees is that - although unlikely - a splay tree can arrange itself linearly. Therefore, the worst-case performance of a splay tree is $O(n)$ .
Multithreaded operations can be complicated since, even in a read-only configuration, splay trees can reorganize themselves.

Splaying

After an element is accessed, the splay operation is performed, which brings the element to the root of the tree. If the element is not in a root position, splaying can take one of three patterns:

Zig (or zag) step
Zig-zig (or zag-zag) step
Zig-zag (or zag-zig) step

The step you take is dependent on the position of the node. If the node is at the root, it is immediately returned.

1. Zig (or zag)

When no grandparent node exists, the splay function will move the node up to the parent with a single rotation. A left rotation is a zag and a right rotation is a zig.

Note: A left rotation corresponds to a right placement (the node is right of the parent) and vice versa.

#include <iostream>
using namespace std;
// basic node structure   
struct node {
  int key;
  node *left, *right;
  node *parent;
  node(int init) : key(init), left(nullptr), right(nullptr), parent(nullptr) { }
  ~node() {}
};
class splay_tree {
  public:
   node *root;
   
   splay_tree() : root(nullptr) {}
  // left rotation helper function used to splay
  // This will make more sense if you follow along
  // from the splay function.
  // Here x can refer to either the parent or grandparent node.
  void left_rotate(node *x) {
    node *y = x->right;
    if (y) {
      x->right = y->left;
      if (y->left) 
        y->left->parent = x;
      y->parent = x->parent;
    }
    if (!x->parent)
      root = y;
    else if (x == x->parent->left)
      x->parent->left = y;
    else 
      x->parent->right = y;
    
    if (y)
      y->left = x;
    
    x->parent = y;
  }
  // right rotation helper function used to splay
  void right_rotate(node *x) {
    node *y = x->left;
    if (y) {
      x->left = y->right;
      if (y->right)
        y->right->parent = x;
      y->parent = x->parent;
    }
    if (!x->parent)
      root = y;
    else if (x == x->parent->left)
      x->parent->left = y;
    else 
      x->parent->right = y;
    if (y)
      y->right = x;
    x->parent = y;
  }
  // the splay function moves the accessed node up the tree 
  void splay(node *x) {
    while (x->parent){
      // if no grandparent: zig operation
      if (!x->parent->parent) {
        if (x->parent->left == x) 
          right_rotate(x->parent);
        else 
          left_rotate(x->parent);
      } 
      // when grandparent exists: 
      // Node exist at left of the left node: zig-zig
      else if (x->parent->left == x && x->parent->parent->left == x->parent) {
        right_rotate(x->parent->parent);
        right_rotate(x->parent);  
      // Node exist at right of the right node: zag-zag
      } else if (x->parent->right == x && x->parent->parent->right == x->parent) {
        left_rotate(x->parent->parent);
        left_rotate(x->parent);
      } 
      // Node exist at right of grandparent and left of parent:
      // zig-zag
      else if (x->parent->left == x && x->parent->parent->right == x->parent) {
        right_rotate(x->parent);
        left_rotate(x->parent);
      } 
      // Node exist at left of grandparent and right of parent: 
      // zag-zig
      else {
        left_rotate(x->parent);
        right_rotate(x->parent);
      }
    }
  }
  node* find(int key) {
    node *z = root;
    while (z) {
      if (z->key < key) 
        z = z->right;
      else if (key < z->key)
        z = z->left;
      else {
        splay(z);
        return z;
      }
    }
    return nullptr;
  }
  void insert(int key) {
    node *z = root;
    node *p = nullptr;
    
    while (z) {
      p = z;
      if (z->key < key) 
        z = z->right;
      else 
        z = z->left;
    }
    
    z = new node(key);
    z->parent = p;
    
    if (!p) 
      root = z;
    else if (p->key < z->key)
      p->right = z;
    else 
      p->left = z;
    
    splay(z);
  }
};
int main() {
  // please feel free to use the insert or 
  // find operations and observe the results
  splay_tree *tree = new splay_tree();
  tree->insert(5);
  tree->insert(4);
  tree->insert(1);
  tree->insert(6);
  
  cout << "Root before find operation: " << tree->root->key <<endl;
  tree->find(4);
  cout << "Root after find operation: "  <<tree->root->key <<endl;
  return 0;
}

Definition: Splay tree

Advantages

Disadvantages

Splaying

1. Zig (or zag)

2. Zig-zig (or zag-zag)

3. Zig-zag (or zag-zig)

Implementation