R Tree Search

R tree search is a spatial indexing method for multidimensional objects such as rectangles or bounding boxes. It organizes data into a balanced tree of minimum bounding rectangles (MBRs), enabling efficient spatial queries.

It is widely used in databases and geographic information systems.

Problem

Given a set of spatial rectangles and a query rectangle $Q$, find all rectangles that intersect $Q$:

$$ R \cap Q \neq \emptyset $$

Structure

Each node stores a bounding rectangle that covers all its children.

field	meaning
MBR	minimum bounding rectangle
children	child nodes or data entries

Each node satisfies:

$$ MBR(node) = \text{bounding box of all children} $$

Algorithm

Search prunes subtrees whose bounding rectangles do not intersect the query.

r_tree_search(node, Q, result):
    if node is null:
        return

    if not intersects(node.MBR, Q):
        return

    if node is leaf:
        for entry in node.entries:
            if intersects(entry.MBR, Q):
                add entry to result
        return

    for child in node.children:
        r_tree_search(child, Q, result)

Example

Rectangles:

rectangle
[1,1] to [3,3]
[2,2] to [5,5]
[6,6] to [8,8]

Query:

$$ [2,2] \to [4,4] $$

Matches:

rectangle	overlap
[1,1]–[3,3]	yes
[2,2]–[5,5]	yes
[6,6]–[8,8]	no

Correctness

Each node's MBR fully contains all rectangles in its subtree. If a node's MBR does not intersect the query rectangle, then none of its children can intersect it either, so pruning is safe.

If the node is a leaf, each stored rectangle is checked explicitly. Therefore all intersecting rectangles are reported, and no non intersecting rectangle is included.

Complexity

Let $n$ be number of entries and $k$ number of results.

case	time
average query	$O(\log n + k)$
worst case	$O(n)$

Space complexity:

$$ O(n) $$

When to Use

R trees are useful when:

• indexing spatial objects (GIS, maps)
• rectangles, polygons, or regions are queried
• dynamic insertions and deletions are required
• range and overlap queries are frequent

Compared to k-d trees, R trees handle rectangles directly rather than points.

Implementation

class Node:
    def __init__(self, mbr):
        self.mbr = mbr
        self.children = []
        self.entries = None

def intersects(a, b):
    return not (a[2] < b[0] or a[0] > b[2] or a[3] < b[1] or a[1] > b[3])

def r_tree_search(node, Q, result):
    if node is None:
        return

    if not intersects(node.mbr, Q):
        return

    if node.entries is not None:
        for e in node.entries:
            if intersects(e.mbr, Q):
                result.append(e)
        return

    for child in node.children:
        r_tree_search(child, Q, result)

type Rect struct {
	X1, Y1, X2, Y2 float64
}

type Node struct {
	MBR      Rect
	Children []*Node
	Entries  []Rect
}

func intersects(a, b Rect) bool {
	return !(a.X2 < b.X1 || a.X1 > b.X2 || a.Y2 < b.Y1 || a.Y1 > b.Y2)
}

func RTreeSearch(node *Node, Q Rect, res *[]Rect) {
	if node == nil {
		return
	}

	if !intersects(node.MBR, Q) {
		return
	}

	if node.Entries != nil {
		for _, e := range node.Entries {
			if intersects(e, Q) {
				*res = append(*res, e)
			}
		}
		return
	}

	for _, child := range node.Children {
		RTreeSearch(child, Q, res)
	}
}