1.8 splay tree

Data Structure-splay tree

1. Splay Trees
https://docs.google.com/presentation/d/1J8sIJDKi9DfnZJ5-VMeGtPqQ8nFfJ_mQVxz4oPEj-KA/edit#slide=id.p

2. Fundamental Concept
Carefully rearrange (using tree rotation
operation) the tree so that the recently
accessed elements are brought to the top and
at the same time, the tree is also
approximately balanced.

3. Splay Tree
Splay is a binary search tree in which recently accessed
keys are quick to access again.
When an element is accessed, it is moved to the root using
series of rotation operations so that it is quick to access
again.
The tree is also approximately balanced while rearranging.
The process of rearranging is called splaying.

4. Operations
•Splay tree includes all the operations of BST along with splay
operation.
•Splay operation rearranges the tree so that the element is placed
at the top of the tree.
•Let x be the accessed node and let p be the parent node of x.
Three types of splay steps:
•Zig step (one left rotation or one right rotation)
ocarried out when p is the root (last step in the splay operation)
•Zig-Zig step (left-left rotation or right-right rotation)
ocarried out when p is not the root and both x,p are either right
or left children.
•Zig-Zag step (left-right rotation or right-left rotation)
ocarried out when p is not the root and x is left and p is right or
vice versa

5. Operations (contd)
Insertion
•Insert the node using the normal BST insert procedure
•splay the newly inserted node to the root
Deletion
•delete using normal BST delete procedure
•splay the parent of removed node to the root
Search
•Search using normal BST search procedure
•splay the accessed item to the root

6. Splay Operation - Pseudo code
void splay(struct node *x)
{
struct node *p,*g;
/*check if node x is the root node*/
if (x->parent == NULL) { root = x; return; }
/*Performs Zig step*/
else if ( x->parent == root)
{
if(x == x->parent->left) rightrotation(root);
else
leftrotation(root);
}

7. else
{
p = x->parent; /*now points to parent of x*/
g = p->parent; /*now points to grand parent of x*/
/*when x is left and x's parent is left*/
if(x==p->left and p==g->left) //Zig-zig
{ rightrotation(g); rightrotation(p); }
/*step when x is right and x's parent is right*/
else if (x==p->right and p==g->right) //Zig-zig
{ leftrotation(g); leftrotation(p); }
/*when x's is right and x's parent is left*/
else if (x==p->right and p==g->left) // Zig-zag
{ leftrotation(p); rightrotation(g); }
/*when x's is left and x's parent is right*/
else if (x==p->left and p==g->right) //Zig-zag
{ rightrotation(p); leftrotation(g); }
splay(x);
}
}

8. Splay Trees and B-Trees - Lecture 9
8
• Let X be a non-root node with ³ 2 ancestors.
• P is its parent node.
• G is its grandparent node.
P
G
X
G
P
X
G
P
X
G
P
X
Splay Tree Terminology

9. Zig-Zig and Zig-Zag
Splay Trees and B-Trees - Lecture 9
9
4
G 5
1 P
Zig-zag
G
P 5
X 2
Zig-zig
X
Parent and grandparent
in same direction.
Parent and grandparent
in different directions.

10. Zig at depth 1 (root)
“Zig” is just a single rotation, as in an AVL tree
Let R be the node that was accessed (e.g. using
Find)
ZigFromLeft moves R to the top ®faster access
next time
Splay Trees and B-Trees - Lecture 9
10
ZigFromLeft
root

11. Zig at depth 1
Suppose Q is now accessed using Find
ZigFromRight moves Q back to the top
Splay Trees and B-Trees - Lecture 9
11
ZigFromRight
root

12. Zig-Zag operation
“Zig-Zag” consists of two rotations of the opposite
direction (assume R is the node that was accessed)
Splay Trees and B-Trees - Lecture 9
12
(ZigFromRight)
(ZigFromLeft)
ZigZagFromLeft

13. Zig-Zig operation
“Zig-Zig” consists of two single rotations of the same direction (R
is the node that was accessed)
Splay Trees and B-Trees - Lecture 9
13

(ZigFromLeft) (ZigFromLeft)
ZigZigFromLeft

14. Decreasing depth - "autobalance"
Splay Trees and B-Trees - Lecture 9
14
Find(T) Find(R)

15. Splay Tree Insert and Delete
Insert x
Insert x as normal then splay x to root.
Delete x
Splay x to root and remove it. (note: the node
does not have to be a leaf or single child node
like in BST delete.) Two trees remain, right
subtree and left subtree.
Splay the max in the left subtree to the root
Attach the right subtree to the new root of the left
subtree.
Splay Trees and B-Trees - Lecture 9
15

16. Example Insert
Inserting in order 1,2,3,…,8
Without self-adjustment
Splay Trees and B-Trees - Lecture 9
16
1
2
3
4
5
6
7
8
O(n
2
) time for n Insert

17. With Self-Adjustment
Splay Trees and B-Trees - Lecture 9
17
1
2
1 2
1
ZigFromRight
2
1 3
ZigFromRight
2
1
3
1
2
3

18. With Self-Adjustment
Splay Trees and B-Trees - Lecture 9
18
ZigFromRight
2
1
3
4
4
2
1
3
4
Each Insert takes O(1) time therefore O(n) time for n Insert!!

19. Example Deletion
Splay Trees and B-Trees - Lecture 9
19
10
155
2013
82
96
10
15
5
2013
8
2 96
splay
10
15
5
2013
2 96
remove
10
15
5
2013
2 9
6
Splay (zig)
attach
(Zig-Zag)

20. Advantages
Simple implementation (self optimizing)
Average case performance is as efficient as other trees
No need to store any bookkeeping data
Allows access to both the previous and new versions after an
update(Persistent data structure)
Stable sorting

21. How many squares can you create in this figure by connecting any 4 dots (the corners of a
square must lie upon a grid dot?
TRIANGLES:
How many triangles are located in the image below?

22. There are 11 squares total; 5 small, 4 medium, and 2 large.
27 triangles. There are 16 one-cell triangles, 7 four-cell triangles, 3 nine-cell
triangles, and 1 sixteen-cell triangle.

23. GUIDED READING

25. ASSESSMENT
After inserting 56,87,56,43,98 and 77 the
element 22 is inserted. Then the root node of
the resultant splay tree is
1.87
2.56
3.22
4.77

26. CONTD..
The Zig-zig corresponds to
1.left rotation followed by right rotation
2.right rotation followed by left rotation
3.left rotation followed by left rotation
4.only left rotation.

27. CONTD..
After inserting, 7,6,5,4,3,2 and 1 into a normal
binary search tree, a splay operation is
performed at node 1. Then, the left and right
child of the root node of the resultant tree are
1.6 and null respectively
2.null and 6 respectively
3.5 and null respectively
4.null and 5 respectively

28. CONTD..
Let x be the accessed node and p be the parent
node of x. Then Zig-Zag operation is performed
When
1.p is the root
2.p is not the root and both x,p are left child nodes
3.p is not the root and both x,p are right child nodes
4.p is not the root and x is left and p is right or vice versa

29. CONTD..
After inserting, 7,6,5,4,3,2 and 1 into splay tree,
a search operation is performed at
node1. Then, the left and right child of the root
node of the resultant tree are
1.null and 3 respectively
2.null and 4 respectively
3.null and 6 respectively
4.2 and 5 respectively