KD-Tree
A space-partitioning BST alternating split axes; nearest-neighbour and range search in k dimensions.
(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.
What you will see
Splitting lines drawn on the plane alternate vertical and horizontal; a search prunes half-planes.
Cost
| build | O(n log n) |
|---|---|
| nearest neighbour | O(log n) average |
| range query | O(sqrt(n) + k) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Related
Taught by the same lesson
Interval, kd and Range Trees covers these too, in the same run.