ID range searching In ld. the query is an interval First solution using ideas we know Interval trees Represent each point x by the interval [x,x Obtain a dynamic structure that can list k answers in a query in O(k Ig n) time c 2001 by erik D. Demaine Introduction to Ago orns Day 21 L12.6
© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.6 1D range searching In 1D, the query is an interval: First solution using ideas we know: • Interval trees • Represent each point x by the interval [x, x]. • Obtain a dynamic structure that can list k answers in a query in O(k lg n) time
ID range searching In ld. the query is an interval Second solution using ideas we know Sort the points and store them in an array Solve query by binary search on endpoints Obtain a static structure that can list k answers in a query in O(k + Ig n)time Goal: obtain a dynamic structure that can list k answers in a query in O(k+lg n)time c 2001 by erik D. Demaine Introduction to Agorithms Day 21 L12.7
© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.7 1D range searching In 1D, the query is an interval: Second solution using ideas we know: • Sort the points and store them in an array • Solve query by binary search on endpoints. • Obtain a static structure that can list k answers in a query in O(k + lg n) time. Goal: Obtain a dynamic structure that can list k answers in a query in O(k + lg n) time
ID range searching In ld. the query is an interval New solution that extends to higher dimensions Balanced binary search tree New organization principle Store points in the leaves of the tree Internal nodes store copies of the leaves to satisfy binary search property Node x stores in key the maximum key of any leaf in the left subtree ofx c 2001 by erik D. Demaine Introduction to Algorithms Day 21 L12. 8
© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.8 1D range searching In 1D, the query is an interval: New solution that extends to higher dimensions: • Balanced binary search tree • New organization principle: Store points in the leaves of the tree. • Internal nodes store copies of the leaves to satisfy binary search property: • Node x stores in key[x] the maximum key of any leaf in the left subtree of x
Example of a lD range tree 43 681214 261354142 5961 c 2001 by erik D. Demaine Introduction to Algorithms Day 21 L12.9
© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.9 Example of a 1D range tree 11 66 88 1212 1414 1717 2626 3535 4141 4242 4343 5959 6161
Example of a lD range tree 42 14 35 43 2)17(26)(41)43(59 681214 261354142 5961 c 2001 by erik D. Demaine Introduction to Algorithms Dav2112.10
© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.10 Example of a 1D range tree 11 1212 66 88 1212 1414 1717 2626 3535 4141 4242 4343 5959 6161 66 2626 4141 5959 11 1414 3535 4343 88 4242 1717 xx ≤ x > x