All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

Augmenting AVL trees. How we’ve thought about trees so far. Good for determining ancestry Can be good for quickly finding an element. Other kinds of uses?. Any thoughts? Finding a minimum/maximum… (heaps are probably just as good or better) Finding an average?

Transcript

Augmenting AVL treesHow we’ve thought about trees so farGood for determining ancestryCan be good for quickly finding an elementOther kinds of uses?Any thoughts? Finding a minimum/maximum… (heaps are probably just as good or better) Finding an average? More complicated things?!!!11one Enter: idea of augmentinga treeAugmentingCan quickly compute many global properties that seem to need knowledge of the whole tree! Examples: size of any sub-tree height of any sub-tree averages of keys/values in a sub-tree min+max of keys/values in any sub-tree, … Can quickly compute any function f(x) so long as you only need to know f(x.left) and f(x.right)! Augmenting an AVL treeCan augment any kind of tree Only balanced trees are guaranteed to be fast After augmenting an AVL tree to compute f(x), we can still do all operations in O(lg n)! Simple first exampleWe are going to do one simple example Then, you will help with a harder one! Problem: augment an AVL tree so we can do: Insert(key): add key in O(lg n) Delete(key): remove key in O(lg n) Height(node): get height of sub-tree rooted at node in O(1) A regular AVL tree already does thisStore some extra data at each node… but what?How do we do this?Can we compute this function quickly?Function we want to compute: Height(u) = H(u) If someone gives us H(uL) and H(uR),can we compute H(u)? What formula should we use? If u = null then H(u) = 0 Else H(u) = max{H(uL), H(uR)}+1 uuLuRH(u)=?H(uL)H(uR)Augmenting AVL tree to compute H(u)Each node u contains key: the key left, right: child pointers h: height of sub-tree rooted at u How? The usual stuff…Secret sauce!d, 1d, 2d, 0d, 1d, 2d, 2Insert(d)a, 0a, 1b, 0b, 1e, 0e, 0Insert(a)Insert(e)b, 0c, 0c, 0a, 1a, 0Insert(b)c, 0Insert(c)Algorithm idea:From the last slide, we develop an algorithm Insert(u):1BST search for where to put u2Insert u into place like in a regular AVL tree3 Fix balance factors and rotate as you would in AVL insert, but fix heights at the same time. (Remember to fix heights all the way to the root. Don’t stop before reaching the root!)(When you rotate, remember to fix heights of all nodes involved, just like you fix balance factors!) Harder problem: overpaid employees!You have a record for each employee in your company with salary and age. We want to quickly find overpaid employees of age <= A. Breaking the problem downYou must design a data structure D of employee records to efficiently do: Insert(D; x): If x is a pointer to a new employee record, insert the record pointed to by x into D. Delete(D; x): If x is a pointer to an existing employee record in D, remove that record from D. MaxSal(D; A): Return the largest salary, amongst all employees in D whose age is <= A; if there is no such employee, then return -1. All functions must run in O(lg n) Part 1Give a precise and full description of your data structure Illustrate this data structure by giving an example of it on some collection of employee records of your own choice. Figuring out the data structureIterative process…hard to get it right the first time! What function do we want to compute? Maximum salary for employees with age <= A What info should we store at each node u? Maybe maximum salary for all employees in the sub-tree rooted at u? Let’s call this value MS(u). How can we compute MS(u) quickly (i.e., by looking at a small number of descendents of u)? Organizing nodes inside the treeHow can we turn maximum salary in a sub-tree into maximum salary for those with age <= A? For sure, need to relate age with sub-trees! Things are organized into sub-trees by key… So, age must be related to key. Let age be the key of each node… May have 2+ nodes with same key, but that’s okay. Answer to part 1Age Salary1100 310001247 290001590 280001590 480003801 4100017000 3600030000 9000030000 75000Age=17000, MS=Age=17000, salary=36000, MS=90000Age=17000, salary=36000, MS=Age=30000, salary=75000, MS=90000Age=1590, salary=28000, MS=Age=1590, MS=Age=24100, MS=Age=30000, salary=75000, MS=Age=1590, salary=28000, MS=48000Age=1100, salary=31000,MS=31000Age=1100, salary=31000,MS=Age=1100, MS=Age=3801, salary=41000, MS=Age=3801, MS=Age=3801, salary=41000, MS=48000Age=30000, salary=90000, MS=90000Age=30000, salary=90000, MS=Age=30000, MS=Age=1247, salary=29000,MS=Age=1247, MS=Age=1247, salary=29000,MS=29000Age=1590, salary=48000, MS=Age=1590, MS=Age=1590, salary=48000, MS=48000Part 2Explain how to implement Insert(D, x), Delete(D, x) and MaxSal(D, A) in O(log n) time Insert:1Do regular AVL-insert(D, <x.age, x.salary, MS=0>), except:As you move up the tree fixing balance factors, fix MS(u) for every node on the path to the root After each rotation, fix each MS(u) for each nodethat was involved in the rotation Remember to fix heights all the way to the root.(Don’t stop early, even if done balance factors/rotations!) Delete:Same as Insert, but “Do regular AVL-delete[…]”How do we do MaxSal???What does “fix MS(u)” mean?What formula do we use?Set MS(u) = max{u.salary, MS(uL), MS(uR)}How can we compute MaxSal?Write a recursive function! Recursion is often very natural for trees Big problem: want MaxSal(D, A) =largest salary for age <= A in tree Smaller problem: MaxSal(u, A) =largest salary for age <= A in sub-treerooted at u Recursive/inductive measure of problem size:size of sub-tree Therefore, smaller problem = smaller sub-tree. Code for MaxSal// u is a node, A is an ageMaxSal(u, A) if u = null then return -1 else if A < u.age then return MaxSal(uL, A) else return max{u.salary, MaxSal(uR,A), MaxSal(uR,A)}u: salary, age, MSuR: salary, age, MSuL: salary, age, MSCalling MaxSal on BOTH sub-trees can take O(n) time!Code for MaxSal// u is a node, A is an ageMaxSal(u, A) if u = null then return -1 else if A < u.age then return MaxSal(uL, A) else return max{u.salary, MaxSal(uR,A), MS(uL)}u: salary, age, MSuR: salary, age, MSuL: salary, age, MSWhy O(lg n) time?Insert/Delete: normal AVL operation = O(lg n) PLUS: update MS(u) for each u on path to the root Length of this path <= tree height, so O(lg n) in an AVL tree PLUS: update MS(u) for each node involved in a rotation At most O(lg n) rotations (one per node on the path from the root <= tree height) Each rotation involves a constant number of nodes Therefore, constant * O(lg n), which is O(lg n). MaxSal Constant work + recursive call on ONE child Single recursive call means O(tree height) = O(lg n)

Related Search

Similar documents

Advertisements

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks