Editing Splay tree (section)

== Implementation and variants ==
Splaying, as mentioned above, is performed during a second, bottom-up pass over the access path of a node. It is possible to record the access path during the first pass for use during the second, but that requires extra space during the access operation.  Another alternative is to keep a parent pointer in every node, which avoids the need for extra space during access operations but may reduce overall time efficiency because of the need to update those pointers.<ref name="SleatorTarjan" />

Another method which can be used is based on the argument that the tree can be restructured during the way down the access path instead of making a second pass. This top-down splaying routine uses three sets of nodes – left tree, right tree and middle tree. The first two contain all items of original tree known to be less than or greater than current item respectively. The middle tree consists of the sub-tree rooted at the current node. These three sets are updated down the access path while keeping the splay operations in check. Another method, semisplaying, modifies the zig-zig case to reduce the amount of restructuring done in all operations.<ref name="SleatorTarjan" /><ref name="Lucas" />

Below there is an implementation of splay trees in C++, which uses pointers to represent each node on the tree. This implementation is based on bottom-up splaying version and uses the second method of deletion on a splay tree.  Also, unlike the above definition, this C++ version does ''not'' splay the tree on finds – it only splays on insertions and deletions, and the find operation, therefore, has linear time complexity.

<syntaxhighlight lang="cpp">
#include <functional>

#ifndef SPLAY_TREE
#define SPLAY_TREE

template<typename T, typename Comp = std::less<T>>
class splay_tree {
private:
  Comp comp;
  unsigned long p_size;
  
  struct node {
    node *left, *right;
    node *parent;
    T key;
    node(const T& init = T()) : left(nullptr), right(nullptr), parent(nullptr), key(init) { }
    ~node() {

    }
  } *root;
  
  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;
  }
  
  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;
  }
  
  void splay(node *x) {
    while (x->parent) {
      if (!x->parent->parent) {
        if (x->parent->left == x) right_rotate(x->parent);
        else left_rotate(x->parent);
      } else if (x->parent->left == x && x->parent->parent->left == x->parent) {
        right_rotate(x->parent->parent);
        right_rotate(x->parent);
      } else if (x->parent->right == x && x->parent->parent->right == x->parent) {
        left_rotate(x->parent->parent);
        left_rotate(x->parent);
      } else if (x->parent->left == x && x->parent->parent->right == x->parent) {
        right_rotate(x->parent);
        left_rotate(x->parent);
      } else {
        left_rotate(x->parent);
        right_rotate(x->parent);
      }
    }
  }
  
  void replace(node *u, node *v) {
    if (!u->parent) root = v;
    else if (u == u->parent->left) u->parent->left = v;
    else u->parent->right = v;
    if (v) v->parent = u->parent;
  }
  
  node* subtree_minimum(node *u) {
    while (u->left) u = u->left;
    return u;
  }
  
  node* subtree_maximum(node *u) {
    while (u->right) u = u->right;
    return u;
  }
public:
  splay_tree() : root(nullptr), p_size(0) { }
  
  void insert(const T &key) {
    node *z = root;
    node *p = nullptr;
    
    while (z) {
      p = z;
      if (comp(z->key, key)) z = z->right;
      else z = z->left;
    }
    
    z = new node(key);
    z->parent = p;
    
    if (!p) root = z;
    else if (comp(p->key, z->key)) p->right = z;
    else p->left = z;
    
    splay(z);
    p_size++;
  }
  
  node* find(const T &key) {
    node *z = root;
    while (z) {
      if (comp(z->key, key)) z = z->right;
      else if (comp(key, z->key)) z = z->left;
      else return z;
    }
    return nullptr;
  }
        
  void erase(const T &key) {
    node *z = find(key);
    if (!z) return;
    
    splay(z);
    
    if (!z->left) replace(z, z->right);
    else if (!z->right) replace(z, z->left);
    else {
      node *y = subtree_minimum(z->right);
      if (y->parent != z) {
        replace(y, y->right);
        y->right = z->right;
        y->right->parent = y;
      }
      replace(z, y);
      y->left = z->left;
      y->left->parent = y;
    }
    
    delete z;
    p_size--;
  }

/* //the alternative implementation
    void erase(const T &key) {
        node *z = find(key);
        if (!z) return;
        
        splay(z);
        
        node *s = z->left;
        node *t = z->right;
        delete z;
        
        node *sMax = NULL;
        if (s) {
            s->parent = NULL;
            sMax = subtree_maximum(s);
            splay(sMax);
            root = sMax;
        }
        if (t) {
            if (s)
                sMax->right = t;
            else
                root = t;
            t->parent = sMax;
        }
        
        p_size--;
    }
*/
  
  const T& minimum() { return subtree_minimum(root)->key; }
  const T& maximum() { return subtree_maximum(root)->key; }
  
  bool empty() const { return root == nullptr; }
  unsigned long size() const { return p_size; }
};

#endif // SPLAY_TREE
</syntaxhighlight>