Augnenting data structuresDynamic order statistic (ith element)Slide 3Slide 4Slide 5Insertion operationSlide 7How to augment a data structureAugmenting a red-black treeInterval tree: dynamic set of intervalsHow to implement?Slide 12Slide 13Slide 14Slide 15Augnenting data structures •Augment an existing data structure to apply to a new problem.•Red-black tree as an example.Dynamic order statistic (ith element)•Chapter 9, O(n) algorithm•Red-black tree gives a total order via inorder traversal, i.e., reflecting the rank of an element.–Two additional operations:•Find ith smallest element.•Find the rank of an element.•How to modify it? Add a field, size in every node, i.e., size[x] is the size of the subtree rooted at x, including x. So assume sentinel’s size size[NIL]=0, then, size[x]=size[left[x]]+size[right[x]]+1.If so, easy to find the ith element, or the rank of an element in log(n) time. (page 304, 305).How to maintain size field during insertion or deletion?Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Loop invariant: at start of each iteration, r is the rank of key[x] in the subtree rooted at y.Insertion operation•Same two passes:–Insert x into tree, by going down, increase size by 1 for each node visited.–Modify the color and rotation by going up.•Only the rotation will affect the size of some nodes,•Fortunately, local modification.•Same for deletion operation.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.How to modify the size field of left-rotation: size[y]=size[x], size[x]=size[left[x]]+size[left[y]]+1.How to augment a data structure1. Choosing an underlying DS2. Determining additional information to be maintained in the underlying DS3. Verifying that the additional information can be maintained for the basic modification operations on the underlying DS4. Developing new operationsAugmenting a red-black tree•Theorem 14.1 (page 309):–Let f be a field that augments a red-black tree T of n nodes, and suppose the f of a node x can be computed using only the information in node x, left[x], right[x], including f[left[x]] and f[right[x]]. Then we can maintain all values of f in all nodes during insertion and deletion without asymptotically affecting the O(log(n)).Interval tree: dynamic set of intervals•Intervals•Closed intervals, open intervals, half-intervals.•New operations:–INTERVAL-INSERT(T,x), x=[t1,t2].–INTERVAL-DELETE(T,x), x=[t1,t2].–INTERVAL-SEARCH(T,i), return a pointer x such that the interval of x overlaps with i.How to implement?•Select a underlying DS, red-back tree–The node x contains interval int[x], and the low[int[x]] is the node’s key.•Additional information: max•Maintain the information:–max[x]=max(high[int[x]],max[left[x]],max[right[x]]). –By Theorem 14.1, can be done in log(n).•Implementation of INTERVAL-SEARCH.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.If go to right, then safe since there is no interval in the left overlapping with i.If go to left, either there is an interval in the left overlapping with I or there isno overlaps. In the latter, we can prove that there will also be no overlapsin the right.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or
View Full Document