Splay TreesBinary Search TreesSelf Adjusting TreesAmortized costPros and ConsHow to Restructure?Bad Sequences for Move to Root and Single RotationSlide 8The restructuring heuristicThe Splay operationThen …Slide 12Splay Operations (1)Splay Operations (2)Splay Operations (3)AnalysisSlide 17Access LemmaSlide 19Slide 20Proof, continuedSlide 22Decrease in PotentialBalance TheoremStatic Optimality TheoremSlide 26Splay Trees 1Splay TreesCSCI 2720Spring 2007Splay Trees 2Binary Search TreesRandom binary search trees can have worst case time bound of O(n) per operation for an n-node treeBalanced trees have worst case bound of O(lg n) per operationHowever, balanced trees are not as efficient as possible if the access pattern is non-uniform. Also require extra storage for balance informationOptimum search trees guarantee minimum average access timeHowever, this is only under assumption of fixed, known access probabilities and no correlation among accesses.Construction requires dynamic programming for efficiency.Splay Trees 3Self Adjusting TreesTree itself is a simple binary search treeAlgorithms for Lookup, Insert, Delete, do “something special”After each operation, apply a simple restructuring heuristic intended to improve future performanceNOT guaranteed to operate in O(log n)but we do have a guarantee of amortized costMuch simpler to code than AVL, Red-black, etc.Splay Trees 4Amortized costFor a tree with n nodes, any sequence of m operations, starting from an empty tree, is guaranteed to take a total of O(m log n)Amortized cost is average cost per operation, which is O(log n)Some operations may cost Ω(n)Splay Trees 5Pros and ConsAdvantages:Can be much more efficient if usage pattern is skewed. Good heuristics can have amortized running time similar to the running time of the best structureRequire less space as no balance information is requiredDisadvantages:More local adjustments during look-up operations (balanced trees only make adjustments during updates)Individual operations can be expensive – drawback for real-time applicationsSplay Trees 6How to Restructure?Primitive operation is rotation Rotation preserves order of the BST.Candidates:Single rotation: After accessing item i in node x, rotate parent(x) to move x one step closer to the rootMove to root: After accessing item i in node x, repeatedly rotate parent(x) until x is the root Both candidates can have worst case amortized cost of (n) per access. Desirable to have a restructuring heuristic with better worst case properties!Splay Trees 7Bad Sequences for Move to Root and Single RotationFor Move to Root, the input sequence 1,2,3,4,5,....,n will result in the following treen4321Splay Trees 8Next inputs of 1,2,3,...,nAccess to i takes n-i+1 steps(n2) for 2n operations, so amortized cost of (n) per operation.Bad sequence for single rotation is the same, except rotation of element i is repeated n-i times to get it to the root. Total cost is (n3) for O(n2) operations, so amortized cost of (n) per operation.n4321n4312n4123Splay Trees 9The restructuring heuristicA version of the Move-to-Front heuristic that we applied to listsEach time a key is the object of a successful search, we move it to the rootSplay Trees 10The Splay operationGiven a binary search tree, T, and a key, K, Splay(K,T) modifies T so that:If K is in the tree, K is now the rootIf K is not in the tree, then the root is the in-order successor or in-order predecessorT remains a binary search tree on the same keysSplay Trees 11Then …Lookup(K,T)Splay(K,T)Examine root – does it contain K?Insert(K,I,T)Splay(K,T)Examine root:If root == K, update root with info IIf root != K, create new node contain (K,I), break one link to add new rootSplay Trees 12Then …Delete(K,T)Splay(K,T)Examine rootIf root != K do nothingElse Concat(T1,T2) (two subtrees of root)Concat(T1,T2)Splay(+inf, T1)T1 now has no right subtreeAttach T2 as right child of T1Splay Trees 13Splay Operations (1)Instead of repeatedly using rotation to move x to the root, use the following three types of splaying operations to move x to the rootCase 1:Zig: If parent(x) is the root, rotate parent(x) to get x to the root (This is a terminal case).A BCyxAB CyxSplay Trees 14Splay Operations (2)Case 2:Zig-zig: If parent(x) is not the root and x and parent(x) are both left or both right children, rotate grandparent(x) followed by rotate parent(x).A BCyxDzDCByzAxSplay Trees 15Splay Operations (3)Case 3:Zig-zag: If parent(x) is not the root and x is a left child and parent(x) a right child or vice-versa, rotate parent(x) and then rotate the new parent(x).AB CyxDzA BCyxDzSplay Trees 16AnalysisLet n denote the number of nodes and m denote the number of look-up operations.Use potential method. Let a be the amortized cost of an operation a = t + ’ - , where t is the actual cost, is the potential before an operation and ’ is the potential after the operation. Thenm0m1jjj1-jm1jjm1jjΦΦa )ΦΦ(at Sum of actual costSum of amortized costDecrease inpotentialSplay Trees 17For item i, define positive weight w(i) which is arbitrary but fixed.Define size s(x) of a node x to be the sum of the weights of all items in the subtree rooted at x.Define rank r(x) to be floor(lg s(x)).The potential is the sum of the ranks of all the nodes in the tree.The cost of an operation is the number of rotations done, or one if there are no rotations.Splay Trees 18Access LemmaLemma 1: The amortized cost to splay a tree with root t at a node x is at most 3(r(t)-r(x)) + 1 = O(lg(s(t)/s(x))).Proof:No rotation case is immediateAssume at least one rotation. Consider one splaying step. Let s and s’, r and r’ denote the size and rank functions just before and just after splaying. Let y be parent of x and z be parent of y before the step.Splay Trees 19Claim: The amortized time for one step is at most 3(r’(x)-r(x))+1 for step 1 and 3(r’(x)-r(x)) for steps 2 and 3.Since each step of splaying except the last one has amortized cost at most 3(r’(x)-r(x)) and the last has cost at most 3(r’(x)-r(x))+1, the sum telescopes to obtain a bound of at most 3(r(t)-r(x))+1.Proof of claim:Case 1: Only one rotation in case 1. Amortized cost is r(x)r'(x)
View Full Document