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 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.
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:
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.
#include <iostream>using namespace std;// basic node structurestruct 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;elsex->parent->right = y;if (y)y->left = x;x->parent = y;}// right rotation helper function used to splayvoid 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;elsex->parent->right = y;if (y)y->right = x;x->parent = y;}// the splay function moves the accessed node up the treevoid splay(node *x) {while (x->parent){// if no grandparent: zig operationif (!x->parent->parent) {if (x->parent->left == x)right_rotate(x->parent);elseleft_rotate(x->parent);}// when grandparent exists:// Node exist at left of the left node: zig-zigelse 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-zagelse 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-zigelse {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;elsez = z->left;}z = new node(key);z->parent = p;if (!p)root = z;else if (p->key < z->key)p->right = z;elsep->left = z;splay(z);}};int main() {// please feel free to use the insert or// find operations and observe the resultssplay_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;}
Below is a visual representation of what is going in the code above:
Free Resources