Splay Tree Visualization

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

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

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.

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

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

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

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

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

5) Zag Zag :

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

After perform zag zag rotation.

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.

After perform zig zag rotation.