Splay tree

Algorithm and data structures topic is Splay Tree.
A full comparison between splay tree and AVL tree and learn to create splay tree with expamples

1. SPLAY TREE By, Ambooj Yadav , Anam Iqbal & Hina Firdaus M.Tech CSE Ist year, Ist Semester Advance Datastructure Algorithm and Analysis Jamia Hamdard University, New Delhi-62

2. Introduction Definition :- Splay trees another variation of the binary search tree, invented by Robert Tarjan and Daniel Sleator . Splay means “ to rearrange, so that the desired element is placed at the root " Splay trees support all the operations of binary trees. A  splay tree  is a self-adjusting binary search tree Novel characteristics It performs basic operations such as insertion, look-up and removal. Does not require any accounting information (color, level, height, etc.) Worst case for any single operation : O(N)   Average case for all operation: O(log N) Frequently-accessed keys are moved up so that they are near the root. Easier to perform comparison with 2-3-4 tre es.

3. General question What is difference between AVL trees and splay trees? On what basis do we select these tress? What are positive's and negative's of these trees? What are the performances of these trees in terms of big O notation?

4. 1. What is difference between AVL trees and splay trees? Splay trees always try to be balanced after every operation. Because of this rest operation take less time to perform They are cool…

5. 2. On what basis do we select these tress? Splay trees are always better than binary search trees when, your application deals with a lot of data in the tree but, will need access to a subset of the data very frequently than others.  In this case the data you access frequently will come near the root as a result of the splay.  Because of this, any node can then be accessed with less time than before.

6. 3. What are positive's and negative's of these trees? Positive Negative Positives for both is that you get around log(n) in both these data structures theoretically. Splay trees have average log(n) over a number of operations. Getting n times complexity for an operation in a set, but it can be compensated while accessing frequent items.  In binary search tree, you need to be lucky to have log(n) always. If the keys are not random, then the tree will reduce to a list like form with only one side.

7. 4. What are the performances of these trees in terms of big O notation? AVL tree insertion, deletion, and lookups take O(log n) time for each. Splay tree do take same time in amortized sense. Any long sequence of operations will take at most O(n log n) time, but individual operations might take as much as O(n) time in splay trees.

8. Splay tree Two varieties to approach splay trees are :- Bottom up : first search the tree and rotate at same iteration. Top down: first search the tree and rotate in another iteration There are three case :- ZIG ZIG-ZAG (Bottom-up approach) ZIG-ZIG (Top-down approach)

9. Case 1: ZIG When p is the root. The tree is rotated on the edge between x and p . We rotate x over y, making x’s children be the node y and one of x’s former children u, so as to maintain the relative inorder relationships of the nodes in tree T.

10. Case 2: Zig - Zag Left-right or right-left The order of rotations: bottom-up approach , which guarantees that the tree height is reduced by one at each zig-zag rotation. The tree is rotated on the edge between p and x, and then rotated on the resulting edge between x and g.

11. Case 3: Zig-Zig Left–left or right–right The order of rotations: top-down, which guarantees that the distance to every node encountered (except the root) is reduced to half. When p is not the root and x and p are either both right children or are both left children. The tree is rotated on the edge joining p with its parent g , then rotated on the edge joining x with p .

12. Insertion To insert a value x into a splay tree: Insert x as with a normal binary search tree. when an item is inserted, a splay is performed. As a result, the newly inserted node x becomes the root of the tree. Algorithm: insert(node) { 1. Insert the new node. 2. Let n be the length of the path traversed for the insertion. Then, a. If n = 2m (i.e., even number) then perform m double rotations. b. If n = 2m+1 (i.e., odd number) then perform one single rotation followed by m double rotations. }

13. Let’s solve it! Insert 5, 10, 15, 6, 9,7,11,4,12

14. Deletion 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 . Delete(x, T): ∗ Splay(x, T) and remove root → tree falls into T1 and T2. ∗ Splay(x, T1) ∗ Make T2 right son of new root of T1 after splay

15. find(x) L R x L R > x < x delete x Deletion (cont.)

16. Join Join(L, R): given two trees such that L < R, merge them Splay on the maximum element in L, then attach R L R R splay

17. T find(x) L R x delete x L R > x < x Join(L,R) T - x Deletion (cont.)

18. Delete Example 9 1 6 4 7 2 Delete( 4 ) find(4) 9 6 7 1 4 2 1 2 6 7 1 2 9 6 7 9 Split tree Join Tree

19. Try your own! Delete object(11) from the tree

20. SEARCH The search operation in splay trees does the standard BINARY SEARCH TREE SEARCH. In addition to that it SPLAYS. Splay trees are very effective search trees relatively simple: 1. No extra fields required 2. Excellent locality properties: frequently accessed keys are cheap to find (near top of tree) infrequently accessed keys stay out of the way (near bottom of tree)

21. Rules of splaying: Search If the search is successful, then the node that is found is splayed and becomes the new root. If the search is unsuccessful, the last node accessed prior to reaching the NULL pointer is splayed and becomes the new root. Search ( i , t) If item i is in tree t, return a pointer to the node containing i ; otherwise return a pointer to the null node. Search down the root of t, looking for i . If the search is successful and we reach a node x containing i , we complete the search by splaying at x and returning a pointer to x. If the search is unsuccessful, i.e., we reach the null node, we splay at the last non-null node reached during the search and return a pointer to null. If the tree is empty, we omit any splaying operation.

22. 1 2 3 4 5 6 Q. Search(6) Now parent and grand parent are both on the same direction GRAND PARENT PARENT ZIG-ZIG 1 2 3 4 5 6

23. 1 2 3 4 5 6 For 6 parent and grand-parent are in same direction ZIG-ZIG 1 2 3 4 5 6 STILL SPLAYING….

24. 1 2 3 4 5 6 6 SPLAYED OUT…. 6’s PARENT IS THE ROOT ZIG 1 2 3 4 5 6

25. 1 2 3 4 5 6 Search(4) Zig-Zag Zig-Zag 1 3 4 2 5 6 4 1 5 2 3 6

26. HANDLING AN UNSUCCESSFUL SEARCH 50 30 30 40 60 20 15 90 70 100 Search(80) Not Found Last accessed node is 70 Splay 70

27. 50 30 30 40 60 20 15 90 70 100

28. 50 30 30 40 60 20 15 70 100 90

29. AMORTIZED ANALYSIS Amortized analysis is a technique for analyzing an algorithm's running time.  It is often appropriate  when one is interested in understanding asymptotic behavior over sequences of operations.  For  example, one might be interested in reasoning about the running time for an arbitrary operation to insert  an item into a binary search tree structure. In cases such as this, it might be straightforward to come up  with an upper bound by say, finding the worst-possible time required for any operation, them multiplying this by the number of operations in the sequence. However, many real data structures, such  as splay trees, have the property that it is impossible for every operation in a sequence to take the worst case time, so this approach can result in a horribly pessimistic bound! 

30. Amortized  analysis allows a tighter bound  that better reflects performance.  It does not  say anything about the cost of a specific operation in that sequence.  Amortized  analysis is concerned with the overall cost of arbitrary  sequences. An  amortized  bound will hold regardless of the specific sequence; for example, if the amortized cost of  insertion is O(log n),  it is so regardless of whether you  insert the  sequence '10,' '160,' '2' or the  sequence '2', '160', '10,' '399',  etc. An amortized  bound says nothing about  the cost of individual operations, it  may   be possible   that  one operation in the  sequence  requires a huge  cost. Practical   systems  in which it is important that all operations have low and/or comparable costs may require an algorithm with a worse amortized cost but a better worst ­case  per ­operation bound.

31. Amortized analysis can be understood to take advantage of the fact that  some expensive operations  may “pay” for future operations by somehow limiting the  number or cost of expensive operations that can happen in the near future. If  good amortized cost is a goal, an algorithm may be designed to explicitly  perform   this  “ clean up ” during expensive  operations! The  key to performing amortized analysis is picking a good “credit” or “ potential function” that captures how operations with different actual costs affect a data structure and allows the desired bound to be shown.

32. AMORTISED ANALYSIS OF SPLAY TREES Let S(x) denote subtree of S rooted at x. |S| = number of nodes in tree S. µ(S) = rank = floor(log |S|). P( i ) = ∑ tree node x rank(x ). P( i ) is potential after i’th operation. rank(x ) is computed after i’th operation. P(0 ) = Potential=10 2 1 8 4 3 6 5 7 10 9 |S| = 10 µ(2) = 3 µ(8) = 3 µ(4) = 2 µ(6) = 1 µ(5) = 0

33. CASE 1: If q = null or q is the root do nothing (splay is over). ∆P = 0 amortized cost = actual cost + ∆P = 0. CASE 2: If q is at level 2 do a one-level move and terminate the splay operation. r(x ) = rank of x before splay step. r'(x ) = rank of x after splay step.

34. ∆P = r'( p) + r'(q) − r(p) − r(q) ≤ r'( q ) − r(q ) amortized cost = actual cost + ∆ P ≤ 1+ r'(q) − r(q) p q b a c q c b a p Potential

35. s p q d a b c q a s p c d b r'(q) = r(s) r'(s) ≤ r’(q) r’(p) ≤ r ’(q) r(q ) ≤ r(p ) ∆ P = r’(s) +r’(p) + r’(q )− r(s) −r(p)−r(q) ≤ r '(q) + r '(q ) − r(q) − r(q ) = 2(r'(q)−r(q )) 2(r '(q)−r(q)) ≤ 3(r '(q)−r(q))−1 amortized cost = actual cost + ∆P ≤ 1+3(r '(q)−r(q))−1 = 3(r'(q)−r(q)) CASE 3: If q is at level 3

36. Putting it together We repeat the steps until X replaces the root R zig only happens once, so the 1 is only added once/ Each time, the last Rf (X) is cancelled by the next – Ri (X) The only terms left are: AT(total) <= 1 + 3*[ Rroot (X) – Rinitial (X)] Rinitial (X ) could be as low as 0, Rroot (X) as high as log N • Thus , total budget for whole sequence is O(log N) OPERATION COST AT( zig ) < = 1+ ∆R(X) <= 1 + 3 [ Rf (X) – Ri (X)] AT( zig-zag ) <= 2 ∆R(X) <= 3 [ Rf (X) – Ri (X)] AT( zig-zig ) <= 3 ∆R(X) <= 3 [ Rf (X) – Ri (X)]