Interval, kd and Range Trees

Every other search here either follows an ordered key or has to try both children, so choosing a side on one max comparison looks like a guess. It is not: if the left subtree's max right endpoint is below q.lo, nothing on the left reaches the query and the right side is the only hope, and if it is not below, take the left interval i holding that max - should i itself miss the query, then i.hi >= q.lo forces i.lo > q.hi, and every interval in the right subtree starts at or after i.lo, so the right side cannot match either. The catch is that this buys exactly one answer, because the search returns the moment a node overlaps. Reporting all k matches means descending into both children whenever their stored max still reaches q.lo, which costs O(k log n), and questions about conflicting bookings or overlapping annotations almost always want the full set.

Splitting at the median of the chosen axis is what makes the depth log n, and every pruning argument above assumes that depth; split at the first point instead and sorted input builds a linked list. Cycling the axis by depth gives the clean depth % k rule but wastes a cut whenever the points barely vary along that axis, so a cloud that is wide in x and flat in y spends half its splits separating almost nothing, and the usual nearest-neighbour construction picks the axis of greatest spread at each node instead. scipy.spatial.KDTree exposes the same tension as a flag: balanced_tree=True splits at the median for a compact tree, and turning it off splits at the midpoint of the cell, which builds faster but can leave long thin cells that the prune test rarely rejects. Either way the tree is built once and not edited, because deleting a node needs the minimum along that node's own axis taken from the right subtree rather than the inorder successor, so a changing point set is handled by rebuilding.

The nodes you actually visit are the ones whose cell the query rectangle's boundary cuts through; a cell fully inside is reported wholesale and a cell fully outside dies on one comparison. Counting how many cells a single vertical line can cut gives Q(n) = 2 + 2Q(n/4), because the line misses two of the four grandchildren, and that recurrence solves to O(sqrt n). In d dimensions the same count is O(n^(1 - 1/d)), so at d = 20 the exponent is 0.95, the boundary crosses nearly every cell and the tree is a linear scan with pointer chasing on top. scikit-learn's own numbers line up: its docs put the KD tree's efficient range at D < 20 and say the cost climbs towards O(D*N) beyond that, and its automatic algorithm choice stops using a tree at all once D > 15 and falls back to brute force. That is the prune failing, not the implementation.

The x-tree on its own finds the x-strip in O(log n) plus the size of that strip, and the strip can hold far more points than the k inside the rectangle, so the y filter has to run inside the tree rather than over its output. Hence the sorted y list at every node. A point appears in one node per level, so those lists hold n log n entries between them: that is the entire space cost, and it is why the range tree is a build-once structure. The second log is the binary search repeated inside each of the O(log n) canonical lists, even though you are hunting the same y1 in all of them. Fractional cascading deletes that repetition by storing, next to each y in a node's list, where it falls in the two children's lists, so you binary search once at the top and follow pointers down for O(log n + k).