KD-Tree
A space-partitioning BST alternating split axes. Nearest-neighbour and range search in k dimensions.
Interval, kd and Range Trees: kd-tree range search across alternating splits
(10,10) splits on x = 10. It is inside the rectangle: report it. The rectangle's x range is 4-13, so it crosses the split: both sides must be searched.
Cost
- Build
- O(n log n)
- Nearest neighbour
- O(log n) average
- Range query
- O(sqrt(n) + k)
- Space
- O(n)
Before this
Related
Taught by the same lesson
Interval, kd and Range Trees covers these too, in the same run.