DOC PREVIEW
IUPUI CS 580 - Augnenting data structures

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 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 15 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 15 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 15 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 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

IUPUI CS 580 - Augnenting data structures

Download Augnenting data structures
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 Augnenting data structures 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 Augnenting data structures 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?