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