# 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. A splay tree is not always a balanced tree and may become unbalanced after some operations.

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);
}
}

Heard melodies are sweet, but those unheard, are sweeter
- John Keats  