DOC PREVIEW
UGA CSCI 2720 - splay1

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 TreesRandom binary search trees can have worst case time bound of O(n) per operation for an n-node treeBalanced trees have worst case bound of O(lg n) per operationHowever, balanced trees are not as efficient as possible if the access pattern is non-uniform. Also require extra storage for balance informationOptimum search trees guarantee minimum average access timeHowever, 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 TreesTree itself is a simple binary search treeAlgorithms for Lookup, Insert, Delete, do “something special”After each operation, apply a simple restructuring heuristic intended to improve future performanceNOT guaranteed to operate in O(log n)but we do have a guarantee of amortized costMuch simpler to code than AVL, Red-black, etc.Splay Trees 4Amortized costFor 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 ConsAdvantages: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 structureRequire less space as no balance information is requiredDisadvantages: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 rootMove 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 RotationFor Move to Root, the input sequence 1,2,3,4,5,....,n will result in the following treen4321Splay Trees 8Next inputs of 1,2,3,...,nAccess 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 heuristicA version of the Move-to-Front heuristic that we applied to listsEach time a key is the object of a successful search, we move it to the rootSplay Trees 10The Splay operationGiven 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 rootIf K is not in the tree, then the root is the in-order successor or in-order predecessorT 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 IIf root != K, create new node contain (K,I), break one link to add new rootSplay Trees 12Then …Delete(K,T)Splay(K,T)Examine rootIf root != K do nothingElse Concat(T1,T2) (two subtrees of root)Concat(T1,T2)Splay(+inf, T1)T1 now has no right subtreeAttach 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 rootCase 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 16AnalysisLet 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 17For 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 LemmaLemma 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 immediateAssume 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 19Claim: 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

UGA CSCI 2720 - splay1

Documents in this Course
Load more
Download splay1
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view splay1 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view splay1 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?