Which points lie in x 4-13, y 6-14? A kd-tree is a BST that compares x at even depths and y at odd depths, so each node is a splitting line, vertical or horizontal, marked after its point. A range search visits a node, reports it if it is inside, and descends only into the sides the rectangle actually reaches across the split.
The code
Interval, kd and Range Trees, in Python
class Interval:
def __init__(self, lo, hi):
self.lo, self.hi = lo, hi
def overlap_search(n, q): # nodes keyed by lo, n.max = largest hi below
if n is None:
return None
if n.lo <= q.hi and q.lo <= n.hi: # found one
return n.interval
if n.left is not None and n.left.max >= q.lo: # something on the left can reach q
return overlap_search(n.left, q)
return overlap_search(n.right, q) # otherwise only the right side can
def kd_range(n, depth, r, out): # axis = depth % 2: 0 is x, 1 is y
if n is None:
return
if n.p in r:
out.append(n.p)
axis = depth % 2
v = n.p[axis]
if r.lo[axis] <= v: # the rectangle reaches the low side
kd_range(n.left, depth + 1, r, out)
if r.hi[axis] >= v: # and / or the high side
kd_range(n.right, depth + 1, r, out)
def range_query(root, x1, x2, y1, y2): # node.ys: subtree y values, sorted
split = root
while not split.leaf and (x2 < split.x or x1 > split.x):
split = split.left if x2 < split.x else split.right
count = 0
# walk down both sides from the split node; every subtree hanging off the path towards the
# range is canonical, and each is answered by a binary search in its sorted y list
for c in canonical_subtrees(split, x1, x2):
count += count_in_range(c.ys, y1, y2)
return count # O(log^2 n) with plain binary search
Interval, kd and Range Trees, in JavaScript
class Interval {
constructor(lo, hi) {
this.lo = lo;
this.hi = hi;
}
}
function overlapSearch(n, q) { // nodes keyed by lo, n.max = largest hi below
if (n === null) return null;
if (n.lo <= q.hi && q.lo <= n.hi) return n.interval; // found one
if (n.left !== null && n.left.max >= q.lo) return overlapSearch(n.left, q); // something on the left can reach q
return overlapSearch(n.right, q); // otherwise only the right side can
}
function kdRange(n, depth, r, out) { // axis = depth % 2: 0 is x, 1 is y
if (n === null) return;
if (r.contains(n.p)) out.push(n.p);
const axis = depth % 2;
const v = n.p[axis];
if (r.lo[axis] <= v) kdRange(n.left, depth + 1, r, out); // the rectangle reaches the low side
if (r.hi[axis] >= v) kdRange(n.right, depth + 1, r, out); // and / or the high side
}
function rangeQuery(root, x1, x2, y1, y2) { // node.ys: subtree y values, sorted
let split = root;
while (!split.leaf && (x2 < split.x || x1 > split.x)) split = x2 < split.x ? split.left : split.right;
let count = 0;
// walk down both sides from the split node; every subtree hanging off the path towards the
// range is canonical, and each is answered by a binary search in its sorted y list
for (const c of canonicalSubtrees(split, x1, x2)) count += countInRange(c.ys, y1, y2);
return count; // O(log^2 n) with plain binary search
}
Interval, kd and Range Trees, in Kotlin
class Interval(val lo: Int, val hi: Int)
fun overlapSearch(n: Node?, q: Interval): Interval? { // nodes keyed by lo, n.max = largest hi below
if (n == null) return null
if (n.lo <= q.hi && q.lo <= n.hi) return n.interval // found one
return if (n.left != null && n.left.max >= q.lo) overlapSearch(n.left, q) // something on the left can reach q
else overlapSearch(n.right, q) // otherwise only the right side can
}
fun kdRange(n: Node?, depth: Int, r: Rect, out: MutableList<Point>) { // axis = depth % 2: 0 is x, 1 is y
if (n == null) return
if (n.p in r) out += n.p
val axis = depth % 2; val v = n.p[axis]
if (r.lo[axis] <= v) kdRange(n.left, depth + 1, r, out) // the rectangle reaches the low side
if (r.hi[axis] >= v) kdRange(n.right, depth + 1, r, out) // and / or the high side
}
fun rangeQuery(root: Node, x1: Int, x2: Int, y1: Int, y2: Int): Int { // node.ys: subtree y values, sorted
var split = root
while (split.leaf == false && (x2 < split.x || x1 > split.x)) split = if (x2 < split.x) split.left else split.right
var count = 0
// walk down both sides from the split node; every subtree hanging off the path towards the
// range is canonical, and each is answered by a binary search in its sorted y list
for (c in canonicalSubtrees(split, x1, x2)) count += c.ys.countInRange(y1, y2)
return count // O(log^2 n) with plain binary search
}