CMSC 341 Splay Trees Problems 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 lists 21 12 32 20 15 24 37 40 55 56 77 8 3 2007 UMBC CMSC 341 SplayTrees 2 BST 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 2007 UMBC CMSC 341 SplayTrees 3 Splay 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 2007 UMBC CMSC 341 SplayTrees 4 Splay 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 2007 UMBC CMSC 341 SplayTrees 5 Splay 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 2007 UMBC CMSC 341 SplayTrees 6 Basic Single Rotation in a BST Rotating k1 around k2 Assuming 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 8 3 2007 UMBC CMSC 341 SplayTrees 7 Splay 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 8 3 2007 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 UMBC CMSC 341 SplayTrees 8 Node has no grandparent 8 3 2007 UMBC CMSC 341 SplayTrees 9 Node and Parent are Same Side Zig Zig Rotate P around G then X around P 8 3 2007 UMBC CMSC 341 SplayTrees 10 Node and Parent are Different Sides Zig Zag Rotate X around P then X around G 8 3 2007 UMBC CMSC 341 SplayTrees 11 Operations 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 path 8 3 2007 UMBC CMSC 341 SplayTrees 12 Operations 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 root 8 3 2007 UMBC CMSC 341 SplayTrees 13 Exercise find 65 50 40 20 60 43 70 65 16 63 8 3 2007 66 UMBC CMSC 341 SplayTrees 14 Exercise remove 25 50 40 20 16 60 43 70 65 25 63 8 3 2007 UMBC CMSC 341 SplayTrees 66 15 Insertion in order into a Splay Tree In 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 2007 UMBC CMSC 341 SplayTrees 16 An extreme example of splaying Title splay zig zag eps Creator fig2dev Version 3 2 Patchlevel 0 beta2 Preview This EPS picture was not saved with a preview included in it Comment This EPS picture will print to a PostScript printer but not to other types of printers 8 3 2007 UMBC CMSC 341 SplayTrees 17 Splay 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 2007 UMBC CMSC 341 SplayTrees 18 Top 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 time 8 3 2007 UMBC CMSC 341 SplayTrees 19
View Full Document
Unlocking...