Splay tree in data structure

Splay tree is self balanced binary search tree. That provides additional property that recently accessed elements are quick to access again.

Splay tree Operation

Mainly four operations are performed in the splay tree. Who control the activities of the splay tree. Such as rotational insertion delete and search.

Rotation

Rotation is most important in splay tree because everything is based on rotation, such as perform insertion, deletion and search operation. There is basically six types of rotation are maintaining its operation. There are following.

Zig

Zig Rotation this is simple rotation of Splay tree. This rotation are found when root and left subtree first element are make as Root node of tree.

Zag

Zag Rotation this is simple rotation of Splay tree. This rotation are work when root right child make as root.

Zig Zig

Zig Zig rotation occurs when the node left-left child make to root.

Zag Zig

Zag Zig rotation occurs when the node right then left child are make as root.

Zag Zag

Zig Zig rotation occurs when the node right-right child are make as root. Here include few example to understand this rotation. Here include few examples to understand this rotation.

Zig Zag

Zig Zag rotation occurs when the node left then right child are make as root.

Insertion

The insertion of the splay tree is the same as the BST insertion. In this case, the new node is brought as the root of the tree. This process requires rotation and rearrangement of the tree.

Suppose following [41,61,6,71,11,58] nodes are insert in splay tree.

Initial tree is empty, So create new node (41) and assign to root node.

Insert second node (61) in proper place and make to root node. This process are need zag rotation which is showing in above image.

Create a node value (6) and insert its proper position. After that make to new root.

Create a node value (71) and insert its proper position. After that make to new root.

Create a node value (11) and insert its proper position. After that make to new root.

Create a node value (58) and insert its proper position. After that make to new root.

Deletion

Deletion of an extinct tree node. The first removal element (search element) is searched. If the deleting node is present, create this node as the root of the tree. This process requires some splay tree rotation.

After removing the root node we get the left and right subtitles. If the left sub tree is not NULL, which means that the elements are present in the left subtype. Then find the larger value in this left subtree and create this larger node as the root of the tree and include it in the right subclass.

If left subtree empty and right subtree not. Then make first node of right subtree as root of tree. If both left and right subtree empty then remove this node.

Search

Searching a node of splay tree is similar of binary search tree. if found search node make this node as a root of tree. Let see an example.

Splay trees always replace the most recently used node as the root of the tree. In the above example, the first node value 51 is searched and then it is made root by using rotation.

Time Complexity

Splay tree in easy and useful data structure its time complexity is amortized O(log n).