Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 11 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 11 Prof. Erik Demaine
ynamic order statistics OS-SELECT(i, S): returns the i th smallest element in the dynamic set S. OS-RANK(, S): returns the rank ofx E S in the sorted order of s s elements IDEA: Use a red-black tree for the set S, but keep subtree sizes in the nodes ke Notation for nodes c 2001 by Charles E Leiserson Introduction to Agorithms Day20L11.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.2 Dynamic order statistics OS-SELECT(i, S): returns the ith smallest element in the dynamic set S. OS-RANK(x, S): returns the rank of x ∈ S in the sorted order of S’s elements. IDEA: Use a red-black tree for the set S, but keep subtree sizes in the nodes. key size key size Notation for nodes:
Example of an Os-tree P H size[]= sizelleftx+ size[right+ 1 c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 L11.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.3 Example of an OS-tree M 9 M 9 C 5 C 5 A 1 A 1 F 3 F 3 N 1 N 1 Q 1 Q 1 P 3 P 3 H 1 H 1 D 1 D 1 size[x] = size[left[x]] + size[right[x]] + 1
Selection Implementation trick: Use a sentinel (dummy record) for NIL such that sizeNIL]=0 OS-SELECT(x, 1)b ith smallest element in the subtree rooted at x k<size left+1 bk=rank(x) if i=k then return x if i<k then return os-select(left, 1) else return OS-SELECT(right i-k) (OS-RANk is in the textbook c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 Lll.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.4 Selection OS-SELECT(x, i) ⊳ ith smallest element in the subtree rooted at x k ← size[left[x]] + 1 ⊳ k = rank(x) if i = k then return x if i < k then return OS-SELECT(left[x], i) else return OS-SELECT(right[x], i – k ) Implementation trick: Use a sentinel (dummy record) for NIL such that size[NIL] = 0. (OS-RANK is in the textbook.)
E xample OS- SELECT(root, 5) k=6 i=5 k=2 A k 32 k=1 Running time=O(h)=o(g n) for red-black trees c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 L11. 5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.5 Example M 9 M 9 C 5 C 5 A 1 A 1 F 3 F 3 N 1 N 1 Q 1 Q 1 P 3 P 3 H 1 H 1 D 1 D 1 OS-SELECT(root, 5) i = 5 k = 6 M 9 M 9 C 5 C 5 i = 5 k = 2 i = 3 k = 2 F 3 F 3 i = 1 k = 1 H 1 H 1 Running time = O(h) = O(lg n) for red-black trees
Data structure maintenance Q. Why not keep the ranks themselves in the nodes instead of subtree sizes? A. They are hard to maintain when the red-black tree is modified Modifying operations: INSERT and delete Strategy: update subtree sizes when inserting or deleting c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 L11.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.6 Data structure maintenance Q. Why not keep the ranks themselves in the nodes instead of subtree sizes? A. They are hard to maintain when the red-black tree is modified. Modifying operations: INSERT and DELETE. Strategy: Update subtree sizes when inserting or deleting
Example of insertion INSERT( K) A T c 2001 by Charles E Leiserson Introduction to Agorithms Day20L11.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.7 Example of insertion M 9 M 9 C 5 C 5 A 1 A 1 F 3 F 3 N 1 N 1 Q 1 Q 1 P 3 P 3 H 1 H 1 D 1 D 1 INSERT(“K”) M 10 M 10 C 6 C 6 F 4 F 4 H 2 H 2 K 1 K 1
Handling rebalancing Dont forget that RB-INSERT and RB-DELETE may also need to modify the red-black tree in order to maintain balance Recolorings: no effect on subtree sizes Rotations: fix up subtree sizes in O(1)time Example:/E 16 RB-INSERT and rb-delete still run in odg n) time c 2001 by Charles E Leiserson Introduction to Algorithms Day 20 Lll. 8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.8 Handling rebalancing Don’t forget that RB-INSERT and RB-DELETE may also need to modify the red-black tree in order to maintain balance. • Recolorings: no effect on subtree sizes. • Rotations: fix up subtree sizes in O(1) time. Example: C 11 C 11 E 16 E 16 7 3 4 C 16 C 16 E 8 E 8 7 3 4 ∴RB-INSERT and RB-DELETE still run in O(lg n) time
Data-structure augmentation Methodology:(e.g, order-statistics trees) 1. Choose an underlying data structure(red- black trees) 2. Determine additional information to be stored in the data structure (subtree sizes) 3. Verify that this information can be maintained for modifying operations(RB INSERT, RB-DELETE--don't forget rotations) 4. Develop new dynamic-set operations that use the information(OS-SELECT and OS-RANK) The ese steps are guidelines, not rigid rules c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 Ll1.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.9 Data-structure augmentation Methodology: (e.g., order-statistics trees) 1. Choose an underlying data structure (redblack trees). 2. Determine additional information to be stored in the data structure (subtree sizes). 3. Verify that this information can be maintained for modifying operations (RBINSERT, RB-DELETE — don’t forget rotations). 4. Develop new dynamic-set operations that use the information (OS-SELECT and OS-RANK). These steps are guidelines, not rigid rules
Interval trees Goal: To maintain a dynamic set of intervals such as time intervals lowi=7 10=high[i 17 19 15··1822·°23 Query: For a given query interval i, find an interval in the set that overlaps i c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 Ll1.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.10 Interval trees Goal: To maintain a dynamic set of intervals, such as time intervals. low[i] = 7 10 = high[i] i = [7, 10] 5 4 15 22 11 17 8 18 19 23 Query: For a given query interval i, find an interval in the set that overlaps i