Splay Trees

Splay trees are self-adjusting binary search trees i.e., they adjust their nodes after accessing them. So, after searching, inserting or deleting a node, the tree will get adjusted.

Splay trees put the most recently accessed items near the root based on the principle of locality; 90-10 "rule" which states that 10% of the data is accessed 90% of the time, other 90% of data is only accessed only 10% of the time.

Thus, there is a 90% chance that the elements near the root of a splay tree are going to be accessed in an operation.

Let's learn how these trees adjust nodes on accessing them.

Splaying

"Splaying" is a process in which a node is transferred to the root by performing suitable rotations. In a splay tree, whenever we access any node, it is splayed to the root. It will be clear with the examples given in this chapter.

There are few terminologies used in this process. Let's learn about those.

Zig-Zig and Zig-Zag

When the parent and the grandparent of a node are in the same direction, it is zig-zig.

When the parent and the grandparent of a node are in different directions, it is zig-zag.

Whenever we access a node, we shift it to the root by using suitable rotations. Let's take the following example.

Here, we have performed a single right rotation and a single rotation is termed as "zig".

"zig-zag" consists of two rotations of the opposite direction. Take a look at the following example.

Let's take a look at the following example in which we have accessed the node R.

So, we have performed two single rotations of the same direction to bring the node at the root. This is "zig-zig".

Let's take a look at some examples.

Let's write a code to splay a node to the root.

Code for Splaying

We will start by passing the tree (T) and the node which is going to be splayed (n).

SPLAY(T, n)

We have to splay the node n to the root. So, we will use a loop and perform suitable rotations and stop it when the node n reaches to the root.

SPALY(T, n)
  while n.parent != NULL //node is not root
    ...

Now, if the node n is the direct child of the root, we will just do one rotation, otherwise, we will do two rotations in one iteration.

SPALY(T, n)
  while n.parent != NULL //node is not root
    if n.parent == T.root //node is child of root, one rotation
      if n == n.parent.left //left child
        RIGHT_ROTATE(T, n.parent)
      else //right child
        LEFT_ROTATE(T, n.parent)
    else //two rotations
      ...

To perform two rotations, we will first set a variable p as the parent of n and a variable g as grandparent of n.

SPALY(T, n)
  while n.parent != NULL //node is not root
    if n.parent == T.root //node is child of root, one rotation
      ...
    else //two rotations
      p = n.parent
      g = p.parent

Now, we just have to do the rotations.

SPALY(T, n)
  while n.parent != NULL //node is not root
    ...
    else //two rotations
      ...
      if n.parent.left == n and p.parent.left == p //both are left children
        RIGHT_ROTATE(T, g)
        RIGHT_ROTATE(T, p)
      else if n.parent.right == n and p.parent.right == p //both are right children
        LEFT_ROTATE(T, g)
        LEFT_ROTATE(T, p)
      else if n.parent.right == n and p.parent.left == p
        LEFT_ROTATE(T, p)
        RIGHT_ROTATE(T, g)
      else
        RIGHT_ROTATE(T, p)
        LEFT_ROTATE(T, g)

SPLAY(T, n)
  while n.parent != NULL //node is not root

      if n.parent == T.root //node is child of root, one rotation
          if n == n.parent.left //left child
              RIGHT_ROTATE(T, n.parent)
          else //right child
              LEFT_ROTATE(T, n.parent)

      else //two rotations
          p = n.parent
          g = p.parent

          if n.parent.left == n and p.parent.left == p //both are left children
              RIGHT_ROTATE(T, g)
              RIGHT_ROTATE(T, p)
          else if n.parent.right == n and p.parent.right == p //both are right children
              LEFT_ROTATE(T, g)
              LEFT_ROTATE(T, p)
          else if n.parent.right == n and p.parent.left == p
              LEFT_ROTATE(T, p)
              RIGHT_ROTATE(T, g)
          else
              RIGHT_ROTATE(T, p)
              LEFT_ROTATE(T, g)

Searching in a Splay Tree

Searching is just the same as a normal binary search tree, we just splay the node which was searched to the root

SEARCH(T, n, x)
  if x == n.data
      SPLAY(T, n)
      return n
  else if x < n.data
      return search(T, n.left, x);
  else if x > n.data
      return search(T, n.right, x);
  else
      return NULL

This is the same code that of a binary search tree, we are just splaying the node to root if it is found - if x == n.data → SPLAY(T, n).

Insertion in a Splay Tree

We normally insert a node in a splay tree and splay it to the root.

INSERT(T, n)
  temp = T.root
  y = NULL
  while temp != NULL
      y = temp
      if n.data < temp.data
          temp = temp.left
      else
          temp = temp.right
  n.parent = y
  if y==NULL
      T.root = n
  else if n.data < y.data
      y.left = n
  else
      y.right = n

  SPLAY(T, n)

Deletion in a Splay Tree

To delete a node in a splay tree, we first splay that node to the root.

After this, we just delete the root which gives us two subtrees.

We find the largest element of the left subtree and splay it to the root.

Lastly, we attach the right subtree as the right child of the left subtree.

Let's write the code for deletion.

Code for Deletion in Spaly Tree

We will first store the left and right subtrees in different variables.

DELETE(T, n)
  left_subtree = new splay_tree
  right_subtree = new splay_tree
  left_subtree.root = T.root.left
  right_subtree = T.root.right
  if left_subtree.root != NULL
    left_subtree.root.parent = NULL
  if right_subtree.root != NULL
    right_subtree.root.parent = NULL

Then we will find the maximum of the left subtree and splay it to the root.

  if left_subtree.root != NULL
    m = MAXIMUM(left_subtree, left_subtree.root)
    SPLAY(left_subtree, m)

After that, we will make the right subtree the right child of the new root of the left subtree.

  if left_subtree.root != NULL
    ...
    left_subtree.root.right = right_subtree.root
    T.root = left_subtree.root

If there is no left subtree, we will make right subtree the new tree.

  if left_subtree.root != NULL
    ...
  else
    T.root = right_subtree.root

DELETE(T, n)
  left_subtree = new splay_tree
  right_subtree = new splay_tree
  left_subtree.root = T.root.left
  right_subtree = T.root.right
  if left_subtree.root != NULL
      left_subtree.root.parent = NULL
  if right_subtree.root != NULL
      right_subtree.root.parent = NULL

  if left_subtree.root != NULL
      m = MAXIMUM(left_subtree, left_subtree.root)
      SPLAY(left_subtree, m)
      left_subtree.root.right = right_subtree.root
      T.root = left_subtree.root
  else
      T.root = right_subtree.root

• C
• Python
• Java

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
int data;
struct node *left;
struct node *right;
struct node *parent;
}node;

typedef struct splay_tree {
struct node *root;
}splay_tree;

node* new_node(int data) {
node *n = malloc(sizeof(node));
n->data = data;
n->parent = NULL;
n->right = NULL;
n->left = NULL;

return n;
}

splay_tree* new_splay_tree() {
splay_tree *t = malloc(sizeof(splay_tree));
t->root = NULL;

return t;
}

node* maximum(splay_tree *t, node *x) {
while(x->right != NULL)
  x = x->right;
return x;
}

void left_rotate(splay_tree *t, node *x) {
node *y = x->right;
x->right = y->left;
if(y->left != NULL) {
  y->left->parent = x;
}
y->parent = x->parent;
if(x->parent == NULL) { //x is root
  t->root = y;
}
else if(x == x->parent->left) { //x is left child
  x->parent->left = y;
}
else { //x is right child
  x->parent->right = y;
}
y->left = x;
x->parent = y;
}

void right_rotate(splay_tree *t, node *x) {
node *y = x->left;
x->left = y->right;
if(y->right != NULL) {
  y->right->parent = x;
}
y->parent = x->parent;
if(x->parent == NULL) { //x is root
  t->root = y;
}
else if(x == x->parent->right) { //x is left child
  x->parent->right = y;
}
else { //x is right child
  x->parent->left = y;
}
y->right = x;
x->parent = y;
}

void splay(splay_tree *t, node *n) {
while(n->parent != NULL) { //node is not root
  if(n->parent == t->root) { //node is child of root, one rotation
    if(n == n->parent->left) {
      right_rotate(t, n->parent);
    }
    else {
      left_rotate(t, n->parent);
    }
  }
  else {
    node *p = n->parent;
    node *g = p->parent; //grandparent

    if(n->parent->left == n && p->parent->left == p) { //both are left children
      right_rotate(t, g);
      right_rotate(t, p);
    }
    else if(n->parent->right == n && p->parent->right == p) { //both are right children
      left_rotate(t, g);
      left_rotate(t, p);
    }
    else if(n->parent->right == n && p->parent->left == p) {
      left_rotate(t, p);
      right_rotate(t, g);
    }
    else if(n->parent->left == n && p->parent->right == p) {
      right_rotate(t, p);
      left_rotate(t, g);
    }
  }
}
}

void insert(splay_tree *t, node *n) {
node *y = NULL;
node *temp = t->root;
while(temp != NULL) {
  y = temp;
  if(n->data < temp->data)
    temp = temp->left;
  else
    temp = temp->right;
}
n->parent = y;

if(y == NULL) //newly added node is root
  t->root = n;
else if(n->data < y->data)
  y->left = n;
else
  y->right = n;

splay(t, n);
}

node* search(splay_tree *t, node *n, int x) {
if(x == n->data) {
  splay(t, n);
  return n;
}
else if(x < n->data)
  return search(t, n->left, x);
else if(x > n->data)
  return search(t, n->right, x);
else
  return NULL;
}

void delete(splay_tree *t, node *n) {
splay(t, n);

splay_tree *left_subtree = new_splay_tree();
left_subtree->root = t->root->left;
if(left_subtree->root != NULL)
  left_subtree->root->parent = NULL;

splay_tree *right_subtree = new_splay_tree();
right_subtree->root = t->root->right;
if(right_subtree->root != NULL)
  right_subtree->root->parent = NULL;

free(n);

if(left_subtree->root != NULL) {
  node *m = maximum(left_subtree, left_subtree->root);
  splay(left_subtree, m);
  left_subtree->root->right = right_subtree->root;
  t->root = left_subtree->root;
}
else {
  t->root = right_subtree->root;
}
}

void inorder(splay_tree *t, node *n) {
if(n != NULL) {
  inorder(t, n->left);
  printf("%d\n", n->data);
  inorder(t, n->right);
}
}

int main() {
splay_tree *t = new_splay_tree();

node *a, *b, *c, *d, *e, *f, *g, *h, *i, *j, *k, *l, *m;
a = new_node(10);
b = new_node(20);
c = new_node(30);
d = new_node(100);
e = new_node(90);
f = new_node(40);
g = new_node(50);
h = new_node(60);
i = new_node(70);
j = new_node(80);
k = new_node(150);
l = new_node(110);
m = new_node(120);

insert(t, a);
insert(t, b);
insert(t, c);
insert(t, d);
insert(t, e);
insert(t, f);
insert(t, g);
insert(t, h);
insert(t, i);
insert(t, j);
insert(t, k);
insert(t, l);
insert(t, m);

delete(t, a);
delete(t, m);

inorder(t, t->root);

return 0;
}

class Node:
def __init__(self, data):
  self.data = data
  self.parent = None
  self.left = None
  self.right = None

class SplayTree:
def __init__(self):
  self.root = None

def maximum(self, x):
  while x.right != None:
    x = x.right
  return x

def left_rotate(self, x):
  y = x.right
  x.right = y.left
  if y.left != None:
    y.left.parent = x

  y.parent = x.parent
  if x.parent == None: #x is root
    self.root = y

  elif x == x.parent.left: #x is left child
    x.parent.left = y

  else: #x is right child
    x.parent.right = y

  y.left = x
  x.parent = y

def right_rotate(self, x):
  y = x.left
  x.left = y.right
  if y.right != None:
    y.right.parent = x

  y.parent = x.parent
  if x.parent == None: #x is root
    self.root = y

  elif x == x.parent.right: #x is right child
    x.parent.right = y

  else: #x is left child
    x.parent.left = y

  y.right = x
  x.parent = y

def splay(self, n):
  while n.parent != None: #node is not root
    if n.parent == self.root: #node is child of root, one rotation
      if n == n.parent.left:
        self.right_rotate(n.parent)
      else:
        self.left_rotate(n.parent)

    else:
      p = n.parent
      g = p.parent #grandparent

      if n.parent.left == n and p.parent.left == p: #both are left children
        self.right_rotate(g)
        self.right_rotate(p)

      elif n.parent.right == n and p.parent.right == p: #both are right children
        self.left_rotate(g)
        self.left_rotate(p)

      elif n.parent.right == n and p.parent.left == p:
        self.left_rotate(p)
        self.right_rotate(g)

      elif n.parent.left == n and p.parent.right == p:
        self.right_rotate(p)
        self.left_rotate(g)

def insert(self, n):
  y = None
  temp = self.root
  while temp != None:
    y = temp
    if n.data < temp.data:
      temp = temp.left
    else:
      temp = temp.right

  n.parent = y

  if y == None: #newly added node is root
    self.root = n
  elif n.data < y.data:
    y.left = n
  else:
    y.right = n

  self.splay(n)

def search(self, n, x):
  if x == n.data:
    self.splay(n)
    return n

  elif x < n.data:
    return self.search(n.left, x)
  elif x > n.data:
    return self.search(n.right, x)
  else:
    return None

def delete(self, n):
  self.splay(n)

  left_subtree = SplayTree()
  left_subtree.root = self.root.left
  if left_subtree.root != None:
    left_subtree.root.parent = None

  right_subtree = SplayTree()
  right_subtree.root = self.root.right
  if right_subtree.root != None:
    right_subtree.root.parent = None

  if left_subtree.root != None:
    m = left_subtree.maximum(left_subtree.root)
    left_subtree.splay(m)
    left_subtree.root.right = right_subtree.root
    self.root = left_subtree.root

  else:
    self.root = right_subtree.root

def inorder(self, n):
  if n != None:
    self.inorder(n.left)
    print(n.data)
    self.inorder(n.right)

if __name__ == '__main__':
t = SplayTree()

a = Node(10)
b = Node(20)
c = Node(30)
d = Node(100)
e = Node(90)
f = Node(40)
g = Node(50)
h = Node(60)
i = Node(70)
j = Node(80)
k = Node(150)
l = Node(110)
m = Node(120)

t.insert(a)
t.insert(b)
t.insert(c)
t.insert(d)
t.insert(e)
t.insert(f)
t.insert(g)
t.insert(h)
t.insert(i)
t.insert(j)
t.insert(k)
t.insert(l)
t.insert(m)

t.delete(a)
t.delete(m)

t.inorder(t.root)

class Node {
public int data;
public Node left;
public Node right;
public Node parent;

public Node(int data) {
  this.data = data;
  this.parent = null;
  this.left = null;
  this.right = null;
}
}

class SplayTree {
public Node root;

public SplayTree() {
  this.root = null;
}

public Node maximum(Node x) {
  while(x.right != null)
    x = x.right;
  return x;
}

public void leftRotate(Node x) {
  Node y = x.right;
  x.right = y.left;
  if(y.left != null) {
    y.left.parent = x;
  }
  y.parent = x.parent;
  if(x.parent == null) { //x is root
    this.root = y;
  }
  else if(x == x.parent.left) { //x is left child
    x.parent.left = y;
  }
  else { //x is right child
    x.parent.right = y;
  }
  y.left = x;
  x.parent = y;
}

public void rightRotate(Node x) {
  Node y = x.left;
  x.left = y.right;
  if(y.right != null) {
    y.right.parent = x;
  }
  y.parent = x.parent;
  if(x.parent == null) { //x is root
    this.root = y;
  }
  else if(x == x.parent.right) { //x is left child
    x.parent.right = y;
  }
  else { //x is right child
    x.parent.left = y;
  }
  y.right = x;
  x.parent = y;
}

public void splay(Node n) {
  while(n.parent != null) { //node is not root
    if(n.parent == this.root) { //node is child of root, one rotation
      if(n == n.parent.left) {
        this.rightRotate(n.parent);
      }
      else {
        this.leftRotate(n.parent);
      }
    }
    else {
      Node p = n.parent;
      Node g = p.parent; //grandparent

      if(n.parent.left == n && p.parent.left == p) { //both are left children
        this.rightRotate(g);
        this.rightRotate(p);
      }
      else if(n.parent.right == n && p.parent.right == p) { //both are right children
        this.leftRotate(g);
        this.leftRotate(p);
      }
      else if(n.parent.right == n && p.parent.left == p) {
        this.leftRotate(p);
        this.rightRotate(g);
      }
      else if(n.parent.left == n && p.parent.right == p) {
        this.rightRotate(p);
        this.leftRotate(g);
      }
    }
  }
}

public void insert(Node n) {
  Node y = null;
  Node temp = this.root;
  while(temp != null) {
    y = temp;
    if(n.data < temp.data)
      temp = temp.left;
    else
      temp = temp.right;
  }
  n.parent = y;

  if(y == null) //newly added node is root
    this.root = n;
  else if(n.data < y.data)
    y.left = n;
  else
    y.right = n;

  this.splay(n);
}

public Node search(Node n, int x) {
  if(x == n.data) {
    this.splay(n);
    return n;
  }
  else if(x < n.data)
    return this.search(n.left, x);
  else if(x > n.data)
    return this.search(n.right, x);
  else
    return null;
}

public void delete(Node n) {
  this.splay(n);

  SplayTree leftSubtree = new SplayTree();
  leftSubtree.root = this.root.left;
  if(leftSubtree.root != null)
    leftSubtree.root.parent = null;

  SplayTree rightSubtree = new SplayTree();
  rightSubtree.root = this.root.right;
  if(rightSubtree.root != null)
    rightSubtree.root.parent = null;

  if(leftSubtree.root != null) {
    Node m = leftSubtree.maximum(leftSubtree.root);
    leftSubtree.splay(m);
    leftSubtree.root.right = rightSubtree.root;
    this.root = leftSubtree.root;
  }
  else {
    this.root = rightSubtree.root;
  }
}

public void inorder(Node n) {
  if(n != null) {
    inorder(n.left);
    System.out.println(n.data);
    inorder(n.right);
  }
}

public static void main(String[] args) {
  SplayTree t = new SplayTree();

  Node a, b, c, d, e, f, g, h, i, j, k, l, m;
  a = new Node(10);
  b = new Node(20);
  c = new Node(30);
  d = new Node(100);
  e = new Node(90);
  f = new Node(40);
  g = new Node(50);
  h = new Node(60);
  i = new Node(70);
  j = new Node(80);
  k = new Node(150);
  l = new Node(110);
  m = new Node(120);

  t.insert(a);
  t.insert(b);
  t.insert(c);
  t.insert(d);
  t.insert(e);
  t.insert(f);
  t.insert(g);
  t.insert(h);
  t.insert(i);
  t.insert(j);
  t.insert(k);
  t.insert(l);
  t.insert(m);

  t.delete(a);
  t.delete(m);

  t.inorder(t.root);
}
}