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.

Splay Tree Zig rotation example

Zag

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

Splay Tree Zag rotation example

Zig Zig

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

Splay tree Zig Zig rotation example

Zag Zig

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

Splay tree rotation Zag Zig example

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.

Splay tree zag zag rotation example set A Splay tree zag zag rotation example set B Splay tree zag zag rotation example set C Splay tree zag zag rotation example set D

Zig Zag

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

Splay tree zig zag rotation example

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.

Add node 41

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

Add node 61

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

Add node 6

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

Add node 71

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

Add node 11

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

Add node 11

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.

Splay Tree delete node example

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.

Search node example 1

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.

Search node example 2

Time Complexity

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

Operation Average Worst case
Insert amortized O(log n) amortized O(log n)
Search amortized O(log n) amortized O(log n)
Delete amortized O(log n) amortized O(log n)


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved