CMSC 341Problems with BSTsBST Sequence of OperationsSplay Tree Sequence of OperationsSplay Tree Sequence of Operations (cont.)Splay TreesBasic “Single” Rotation in a BSTSplay OperationNode has no grandparentNode and Parent are Same Side Zig-ZigNode and Parent are Different Sides Zig-ZagOperations in Splay TreesOperations on Splay Trees (cont)Exercise - find( 65 )Exercise - remove( 25 )Slide 16Slide 17Splay Tree CodeTop-Down Splay TreesCMSC 341Splay Trees8/3/2007UMBC CMSC 341 SplayTrees2Problems with BSTsBecause the shape of a BST is determined by the order that data is inserted, we run the risk of trees that are essentially lists21122015322437405556778/3/2007UMBC CMSC 341 SplayTrees3BST Sequence of OperationsWorst case for a single BST operation can be O(N)Not so bad if this happens only occasionallyBUT...its not uncommon for an entire sequence of “bad” operations to occur. In this case, a sequence of M operations take O(M*N) time and the time for the sequence of operations becomes noticeable.8/3/2007UMBC CMSC 341 SplayTrees4Splay Tree Sequence of OperationsSplay trees guarantee that a sequence of M operations takes at most O( M * lg N ) time.We say that the splay tree has amortized running time of O( lg N ) cost per operation. Over a long sequence of operations, some may take more than lg N time, some will take less.8/3/2007UMBC CMSC 341 SplayTrees5Splay Tree Sequence of Operations (cont.)Does not preclude the possibility that any particular operation is still O( N ) in the worst case.Therefore, amortized O( lg N ) not as good as worst case O( lg N)But, the effect is the same – there is no “bad” sequence of operations or bad input sequences.If any particular operation is O( N ) and we still want amortized O( lg N ) performance, then whenever a node is accessed, it must be moved. Otherwise its access time is always O( N ).8/3/2007UMBC CMSC 341 SplayTrees6Splay TreesThe basic idea of the splay tree is that every time a node is accessed, it is pushed to the root by a series of tree rotations. This series of tree rotations is knowing as “splaying”.If the node being “splayed” is deep, many nodes on the path to that node are also deep and by restructuring the tree, we make access to all of those nodes cheaper in the future.8/3/2007UMBC CMSC 341 SplayTrees7Basic “Single” Rotation in a BSTAssuming that the tree on the left is a BST, how can we verify that the tree on the right is still a valid BST?Note that the rotation can be performed in either direction.Rotating k1 around k28/3/2007UMBC CMSC 341 SplayTrees8Splay OperationTo “splay node x”, traverse up the tree from node x to root, rotating along the way until x is the root. For each rotation:If x is root, do nothing.If x has no grandparent, rotate x about its parent. If x has a grandparent, if x and its parent are both left children or both right children, rotate the parent about the grandparent, then rotate x about its parent.if x and its parent are opposite type children (one left and the other right), rotate x about its parent, then rotate x about its new parent (former grandparent).8/3/2007UMBC CMSC 341 SplayTrees9Node has no grandparent8/3/2007UMBC CMSC 341 SplayTrees10Node and Parent are Same SideZig-ZigRotate P around G, then X around P8/3/2007UMBC CMSC 341 SplayTrees11Node and Parent are Different SidesZig-ZagRotate X around P, then X around G8/3/2007UMBC CMSC 341 SplayTrees12Operations in Splay Treesinsertfirst insert as in normal binary search treethen splay inserted nodeif there is a duplicate, the node holding the duplicate element is splayedfind/containssearch for nodeif found, splay it; otherwise splay last node accessed on the search path8/3/2007UMBC CMSC 341 SplayTrees13Operations on Splay Trees (cont)removesplay element to be removedif the element to be deleted is not in the tree, the node last visited on the search path is splayeddisconnect left and right subtrees from rootdo one or both of:splay max item in TL (then TL has no right child)splay min item in TR (then TR has no left child)connect other subtree to empty child of root8/3/2007UMBC CMSC 341 SplayTrees14Exercise - find( 65 )506070656366404320168/3/2007UMBC CMSC 341 SplayTrees15Exercise - remove( 25 ) 50607065636640432016258/3/2007UMBC CMSC 341 SplayTrees16Insertion in order into a Splay TreeIn a BST, building a tree from N sorted elements was O( N2 ). What is the performance of building a splay tree from N sorted elements?8/3/2007UMBC CMSC 341 SplayTrees17Title:splay.zig_zag.epsCreator:fig2dev Version 3.2 Patchlevel 0-beta2Preview:This EPS picture was not savedwith a preview included in it.Comment:This EPS picture will print to aPostScript printer, but not toother types of printers.An extreme example of splaying8/3/2007UMBC CMSC 341 SplayTrees18Splay Tree CodeThe splaying operation is performed “up the tree” from the node to the root. How do we traverse “up” the tree? How do we know if X and P are both left/right children or are different children?How do we know if X has a grandparent?What disadvantages are there to this technique?8/3/2007UMBC CMSC 341 SplayTrees19Top-Down Splay TreesRather than write code that traverses both up and down the tree, “top-down” splay trees only traverse down the tree. On the way down, rotations are performed and the tree is split into three parts depending on the access path (zig, zig-zig, zig-zag) takenX, the node currently being accessedLeft – all nodes less than XRight – all nodes greater than XAs we traverse down the tree, X, Left, and Right are reassembledThis method is faster in practice, uses only O( 1 ) extra space and still retains O( lg N ) amortized running