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