CS241 Study Guide - Quadtree, Range Tree, Dissociation Constant
Document Summary
Recursively divide square r into 4 equal quadrants (split x and y in half) until each quadrant contains no more than one point. Points will fall in ne, se, sw, nw. Check every quadrants that overlaps with the range. When at the leaf check if point is in the range. Worst case: o(n), visit every partition and node in the tree. Partition points in half by their x value, then their y-value, then z-value (if applicable. Check if the partition value lies within the dimension"s range. If it does not, visit the lower/higher node depending on if the partition value is greater/less than the dimension range. Range query time dependent on dimensionality of data. Do range search on x-value as if its a bst. Visit both children if node is within range, right if its less than range, left if it"s greater than range. If the current node is in range, keep track.
