codelike-logo
Splay Tree Visualization
Splay Tree

Splay Tree

Splay tree Operation

1) Insertion : Insertion of splay tree are similar to BST insertion. make this inserted node as a Root of tree. this process are required rotation and rearrangement of tree.

2) Deletion : deletion of a splay tree node. first need to find particular delete element (search element). if found deleted node then make this node as a root of tree. This process are required some splay tree rotation. after arrangement delete this root nodes.

After remove root node we are get left and right subtree. If left sub tree are not NULL that means element are exist in left subtree. then find big value in this left subtree and make this big node as a root of tree and combine right subtree.

If left subtree are NULL then make the Right subtree first node as a root node of tree.

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

Time complexity

Splay tree required O(logn) time in all operation like insertion, search and deletion.

Important feature

The most important feature of splay tree are as following.

1) Recently access key are used in again quick access manner.

2) Tree of a estimate balance while rearrange.

Rearrange of tree is called splay.

Rotation of splay Tree

The following rotations of splay tree.

1) Zig

2) Zag

3) Zig Zig

4) Zag Zig

5) Zag Zag

6) Zig Zag

Rotation Example

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

12354

View insertion [1 2 3 5 4] Try it yourself

View zig rotation of splay tree. for example insert following [1,2,3,5,4] data in newly splay tree. and search (find) [3] data . Try it yourself

123 Zig54 Before Rotation After Rotation 12354

Make Root is node 3

2) Zag : Zag Rotation this is simple rotation of splay tree. This rotation are found when root and right subtree first element are make as Root node of tree.

13452

View zag rotation of splay tree. for example insert following [1,3,4,5,2] data in newly splay tree. and search (find) [5] data . Try it yourself

1345 Zag2 Before Rotation After Rotation 13452

3) Zag Zig : ZagZig Rotation are perform in following tree.

1345 Zag Zig2

Find data [5] in given tree then found two operation first one is Zag Zig and second one is Zag. Try it yourself

1345 Zag Zig2 13452

4) ZigZig : Perform Zig Zig operation on this tree. view insertion Try it yourself.

1354 Zig Zig

If search data [1] then perform zig zig operation of given tree. After rotation zig zig . tree are.

1354

5) Zag Zag :

given below tree perform zag zag operation. for example search data is to [4] in this tree.

13 Zag Zag54

After perform zag zag rotation.

5431

6) Zig Zag :

given below tree perform zig zag operation. for example search data is to [5] in this tree. view insertion Try it yourself.

3517

After perform zig zag rotation.

5431

Example of Splay tree

78443476789854532129767

Let's perform all operation on this given tree. Try it yourself


Another example

9257149512463521121110

Let's perform all operation on this given tree. Try it yourself


Comments