# R Tree Search

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

```text id="rt0k7q"
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

```python id="rt1m8v"
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)
```

```go id="rt2n7x"
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)
	}
}
```