Home PageTitle PageContentsJJ IIJ IPage 1 of 15Go BackFull ScreenCloseQuitIntroduction to Splay Trees• Want to guarantee worst case time O(n log n) for n dictionaryoperations, irrespective of what sequence the operations come in• Vanilla BST is embarrassing when data is in increasing order• AVL trees are easy to describe and do what we want but– Do not provide ‘easy wins’: If the same key is queried upon, wedo not take advantage of the work we did in finding the key– Need to have extra balancing information at each node, whichneeds to be constantly updated– Other balanced or pseudo-balanced trees have similar problems• Splay trees are a neat alternative.– They are vanilla BST (no balancing, color information)– Adversary can cause bad behavior: A particular operation couldcost O(n) time– But cannot cause this repeatedlyHome PageTitle PageContentsJJ IIJ IPage 2 of 15Go BackFull ScreenCloseQuitIntuition Behind Splay TreeA simple idea: Rotate to rootDoes not work! Cost is n +Pn2i ∈ Θ(n2)Home PageTitle PageContentsJJ IIJ IPage 3 of 15Go BackFull ScreenCloseQuitBasic Splay PrimitivesA splay(x) is implemented using three simple primitives counted as atmost two rotationsThe zigzag case (x moves two levels up)The zig case (p is the root and has no parent)Home PageTitle PageContentsJJ IIJ IPage 4 of 15Go BackFull ScreenCloseQuitBasic Splay PrimitivesThe zig-zig case can be thought of as two calls to the restructure()method. (x moves two levels up)Home PageTitle PageContentsJJ IIJ IPage 5 of 15Go BackFull ScreenCloseQuitDifference Between Splaying And Rotate-to-RootThree zig-zigs, and 2 winds up halfway up the treeHome PageTitle PageContentsJJ IIJ IPage 6 of 15Go BackFull ScreenCloseQuitA Complete Splay ExampleHome PageTitle PageContentsJJ IIJ IPage 7 of 15Go BackFull ScreenCloseQuitImplementing Dictionary Operations• A find(x) is performed by searching forx.– If x is found, then we issue splay(x)– If x is not found, then we splay thelast non-null node. This is neces-sary, otherwise an adversary coulddefeat splaying by issuing multiplecalls to −∞ on a degenerate tree• An insert(x) is performed as in vanillaBST. We then issue splay(x). Thisis necessary, otherwise an adversarycould defeat splayingHome PageTitle PageContentsJJ IIJ IPage 8 of 15Go BackFull ScreenCloseQuitImplementing Dictionary Operations• A remove(x) is performed by searching for x. x is now at the rootof the tree with two subtrees L and R– If L is empty, R becomes the new tree– We issue find(x) on L. Now root w of new L has no right child– We hook R as the right child and return w as the root• deleteMin() and deleteMax() can also be easily implementedHome PageTitle PageContentsJJ IIJ IPage 9 of 15Go BackFull ScreenCloseQuitDoes Splaying Work?• The real cost of a splay operation is proportional to the height ofthe tree. The adversary can force a high real cost• The increase in balance is the extent to which the splay helpsadjusting the tree. If the real cost is high, the balance also increases,so in the future, high real cost is not possible• Consider the zigzag case and suppose we splay(x)– If B is heavy (say more than half the elements are in B) thesplay brings a lot of nodes to the top. Future real costs for a lotof nodes is going to be low– If B is light (we have more than half the nodes in A or D) sowe bypassed a lot of nodes. The real cost could not be highHome PageTitle PageContentsJJ IIJ IPage 10 of 15Go BackFull ScreenCloseQuitAmortized Analysis: Proving Splaying Works• Consider the abstract data type (ADT) MStack which supports theoperations Push(k) and Pop() and also supports MultiPop() (whichpops all existing items in the stack)• Consider the time T for an arbitrary sequence of n operations onMStack– If the ith operation was a MultiPop(), it would take O(i) time,thus T =Pi ∈ O(n2)– While true this analysis is conservative since there can’t be morepops than pushes.– A more careful analysis would prove this formally. Let M0,. . . Mn−1be the series of operations, and let Mi0, . . . Mik−1bethe MultiPop() calls. The running time of Mijis ij− ij−1− 1which when summed over all MultiPop() proves that T ∈ O(n)Home PageTitle PageContentsJJ IIJ IPage 11 of 15Go BackFull ScreenCloseQuitThe Potential Method• The O(n) behaviour is easy to prove for MStack, but in more com-plicated data structures, it is harder to visualize the interdependenceof multiple operations• The potential method is a technique which glosses over fine detailsin the data structure in the attempt to prove a reasonable costestimate– Let c(i) denote the running time of the ith operation– Denote φ(i), termed potential, to be an arbitrary function– Define the amortized time c0(i) = φ(i) − φ(i − 1) + c(i)– Observe that T =Pc(i) =Pc0(i) + φ(n) − φ(0)– The actual time T is less than the total amortized time if thenet change in potential is positive• For MStack, define φ(i) to be the number of items before the ithoperation. Since c0(i) ∈ O(1) no matter what operation, T ∈ O(n)Home PageTitle PageContentsJJ IIJ IPage 12 of 15Go BackFull ScreenCloseQuitMore on Amortized Analysis• The potential function must be carefully chosen so as to prove theresult we are interested• Consider an extendable array (of size m) that may be used, forexample, in inserting items during hashing– Rule: If the load factor becomes half, double the size– Assume hash functions so that find() and remove() takes O(1)time– An insert takes O(1) time quite often. Except, of course, whenthe load factor equals 0.5. Then it takes O(m) time to rehashthe 0.5m keys• In fact, starting with a size of 4, a sequence of n = 2p− 1 arbitraryoperations takes cumulatively O(n) time• Choosing φ(i) to be the number of items in the array doesn’t helpus prove the result since amortized cost of a single insert is Θ(m)Home PageTitle PageContentsJJ IIJ IPage 13 of 15Go BackFull ScreenCloseQuitExtendible Array ExampleWe apply the previous rule on an array of size 4, and insert 15 (p = 4)items and count only the effort in rehashing since the cost of an actualinsert otherwise is O(1)Operation Number Rehash Cost Size of Array1 0 42 2 83 04 4 165–7 0 168 8 329–15 0 32Notice that the actual total cost is 14. For 2p− 1 inserts, actual totalis 2(2p−1− 1) < 2pwhich is ‘linear.’Home PageTitle PageContentsJJ IIJ IPage 14 of 15Go BackFull ScreenCloseQuitAnalyzing Zigzag primitive for