AlgoScope

KD-Tree

A space-partitioning BST alternating split axes. Nearest-neighbour and range search in k dimensions.

Data structures, data structure, advanced
(10,10): Both sides.(3,7) x(5,15) y(8,18) x(10,10) x(15,5) y(12,12) x(18,8) ynode

Interval, kd and Range Trees: kd-tree range search across alternating splits

Decision, step 2 of 8

(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.

How interval, kd and range trees works

Cost

Build
O(n log n)
Nearest neighbour
O(log n) average
Range query
O(sqrt(n) + k)
Space
O(n)

Taught by the same lesson

Interval, kd and Range Trees covers these too, in the same run.