Range Tree Search

Range tree search answers orthogonal range queries over points in multiple dimensions. It extends balanced binary search trees by storing secondary structures at each node.

For two dimensions, each node in the primary tree stores a secondary tree over the remaining coordinate.

Problem

Given a set of points $(x, y)$ and a query rectangle:

[x_1, x_2] \times [y_1, y_2]

return all points such that:

x_1 \le x \le x_2 \quad \text{and} \quad y_1 \le y \le y_2

Structure

A 2D range tree consists of:

level	structure
primary tree	balanced BST on x coordinate
secondary structure	BST on y coordinates stored per subtree

Each node stores all points in its subtree sorted by y.

Algorithm

First, locate the canonical decomposition of the x range in the primary tree. Then query each associated secondary structure.

range_tree_search(node, x1, x2, y1, y2, result):
    if node is null:
        return

    if node.x is fully inside [x1, x2]:
        report_all(node.secondary_tree, y1, y2, result)
        return

    if x1 <= node.x:
        range_tree_search(node.left, x1, x2, y1, y2, result)

    if node.x <= x2:
        range_tree_search(node.right, x1, x2, y1, y2, result)

Secondary query:

report_all(tree, y1, y2, result):
    if tree is null:
        return

    if tree.node.y in [y1, y2]:
        add all matching points in subtree

Example

Points:

point
(2, 3)
(4, 7)
(5, 1)
(7, 6)
(8, 2)

Query:

[3, 7] \times [1, 5]

Matches:

point	inside
(5, 1)	yes
(7, 6)	no
(4, 7)	no

Result:

{(5, 1)}

Correctness

The primary tree partitions points by x coordinate. Any node whose subtree lies fully inside the x range contributes all its points without further filtering.

For partially covered nodes, recursion ensures all relevant subtrees are explored.

The secondary structure guarantees that only points with y values in the query range are reported.

Since every point is stored in exactly one subtree per level and is checked against both x and y constraints, all and only valid points are returned.

Complexity

Let $n$ be number of points and $k$ number of reported points.

dimension	time
2D query	$O(\log^2 n + k)$

Space complexity:

O(n \log n)

due to secondary structures.

When to Use

Range trees are useful when:

multidimensional orthogonal range queries are needed
data is static or semi static
query performance is more important than update cost
computational geometry problems are involved

Compared to k d trees, range trees provide more predictable worst case bounds but require more memory.

Implementation

class Node:
    def __init__(self, x):
        self.x = x
        self.left = None
        self.right = None
        self.secondary = []  # sorted by y
        self.points = []

def report_all_secondary(points, y1, y2, result):
    for p in points:
        if y1 <= p[1] <= y2:
            result.append(p)

def range_tree_search(node, x1, x2, y1, y2, result):
    if node is None:
        return

    if x1 <= node.x <= x2:
        report_all_secondary(node.secondary, y1, y2, result)

    if x1 < node.x:
        range_tree_search(node.left, x1, x2, y1, y2, result)

    if node.x < x2:
        range_tree_search(node.right, x1, x2, y1, y2, result)

type Point struct {
	X int
	Y int
}

type Node struct {
	X        int
	Left     *Node
	Right    *Node
	Secondary []Point
}

func reportAll(points []Point, y1, y2 int, res *[]Point) {
	for _, p := range points {
		if p.Y >= y1 && p.Y <= y2 {
			*res = append(*res, p)
		}
	}
}

func RangeTreeSearch(node *Node, x1, x2, y1, y2 int, res *[]Point) {
	if node == nil {
		return
	}

	if node.X >= x1 && node.X <= x2 {
		reportAll(node.Secondary, y1, y2, res)
	}

	if x1 < node.X {
		RangeTreeSearch(node.Left, x1, x2, y1, y2, res)
	}

	if node.X < x2 {
		RangeTreeSearch(node.Right, x1, x2, y1, y2, res)
	}
}