Related Tags

splay tree
data structures
binary tree
jargon

# Definition: Splay tree Educative Answers Team

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.

1. 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.
2. The average case performance of splay trees is comparable to other fully-balanced trees: $O(log\space n)$.
3. Splay trees do not need bookkeeping data; therefore, they have a small memory footprint.

1. 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)$.
2. 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:

1. Zig (or zag) step
2. Zig-zig (or zag-zag) step
3. 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. X is splayed, P is parent, T1, T2 and T3 are subtrees

### 2. Zig-zig (or zag-zag)

When a grandparent and parent node exist and are placed in a similar orientation (e.g., the parent is left of the grandparent and the node is left of the parent), the operation is either zig-zig (left) or zag-zag (right). X is splayed, P is parent, and G is grandparent. T1, T2 , T3 and T4 are subtrees.

### 3. Zig-zag (or zag-zig)

A zig-zag corresponds to the parent being left of the grandparent and right of the parent. A zag-zig is the opposite. X is splayed, P is parent, and G is grandparent. T1, T2 , T3, and T4 are subtrees

## Implementation

Below, is a C++ implementation of a splay tree.

Tip: To visualize what is happening, it may be helpful to visit this tool.

#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;
}
The find operation triggers the splaying function on the found node.

Below is a visual representation of what is going in the code above:

1 of 9

RELATED TAGS

splay tree
data structures
binary tree
jargon 