UNIT-III
Splay Trees
SK. YAKOOB
Associate Professor
Splay Tree
Splay tree is another variation of BST
Splay tree is self-adjusted BST in which every operation on an
element rearranges the tree, so that its elements placed at the
root position of the tree.
All the operations on a splay tree are involved with common
operation called “ Splaying”.
Splaying of an element is the process of bringing it to be Root
position by performing suitable rotation operations.
With the help of Splaying of an element ,we can bring out most
frequently used elements closer to the root of tree i.e Splaying
operation automatically brings the most frequently used
elements closer to the Root of the tree.
The time complexity is O(log n).
Splay Tree Operations
We perform following operations
1. Search
2. Insertion
3. Deletion
Splay Tree
Search Operation:
The search operation in Splay tree does the standard BST search, in
addition to search, it also splays (move a node to the root).
If the search is successful, then the node that is found is splayed and
becomes the new root, else the last node accessed prior to reaching
the NULL is splayed and becomes the new root.
There are following cases for the node being accessed.
1) Node is root We simply return the root, don’t do anything else as
the accessed node is already root.
2) Zig: Node is child of root (the node has no grandparent). Node is
either a left child of root (we do a right rotation) or node is a right child
of its parent (we do a left rotation).
T1, T2 and T3 are subtrees of the tree rooted with y (on left side) or x
(on right side)
Splay Tree
Search Operation:
2) Zig: Node is child of root (the node has no grandparent). Node is
either a left child of root (we do a right rotation) or node is a right child
of its parent (we do a left rotation).
T1, T2 and T3 are subtrees of the tree rooted with y (on left side) or x
(on right side)
Splay Tree
Search Operation:
3) Node has both parent and grandparent. There can be following subcases.
……..3.a) Zig-Zig and Zag-Zag Node is left child of parent and parent is also left child
of grand parent (Two right rotations) OR node is right child of its parent and parent is
also right child of grand parent (Two Left Rotations).
Splay Tree
Search Operation:
3) Node has both parent and grandparent. There can be following subcases.
....3.b) Zig-Zag and Zag-Zig Node is left child of parent and parent is right child of grand
parent (Left Rotation followed by right rotation) OR node is right child of its parent and
parent is left child of grand parent (Right Rotation followed by left rotation).
Splay Tree
Insertion Operation:
The insert operation is similar to Binary Search Tree insert with
additional steps to make sure that the newly inserted key becomes
the new root.
1) Check Whether Tree is Empty or Not
2) If the tree is empty then insert the new node as root node and exit
from the operation
3) If the tree is not empty , then insert the new node as a leaf node using
binary search tree logic
4) After insert ,Splay the new node.
Splay Tree
Insertion Operation:
I we insert 7 in the tree .
5 5
Splay 7
6
6 3 6
3 Zag- Zag
5
2 4 7
2 4
3
2 4
Splay Tree
Deletion Operation:
In a splay tree ,the delete operation is similar to BST deletion ,but before deleting
the element , first we need to splay that node,then delete it from the root , then join
the remaining tree.
1) Check Whether Tree is Empty or Not
2) If the tree is not empty ,splay the deleted node to Root position
3) Then delete the node using binary search tree logic
Splay Tree
Deletion Operation:
I we delete 6 in the tree .
6
5 Delete 6 5
Splay 6 5
3 6
Zag 3
3
2 4
2 4
2 4
Thank you