Trusted answers to developer questions

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.

- 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 reference processors 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.

- 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.

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.*

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.

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).

A zig-zag corresponds to the parent being left of the grandparent and right of the parent. A zag-zig is the opposite.

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:

RELATED TAGS

splay tree

data structures

binary tree

jargon

Copyright Â©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses