R-Trees

1 min read•1 page

An R-Tree is a dynamic height-balanced tree structure designed to index multi-dimensional spatial objects. Unlike KD-trees or Octrees, the bounding regions in an R-Tree can overlap.

RTreeNode:

1. MBR (Minimum Bounding Rectangle): The smallest bounding box enclosing all child elements. 2. Overlapping Bounds: Subtrees are allowed to overlap, avoiding rigid coordinate subdivision. 3. B-Tree Derivative: Nodes have variable capacity limits, splitting when full.

python

1class RTreeNode:
2    def __init__(self, is_leaf=False):
3        self.is_leaf = is_leaf
4        self.mbr = MinimumBoundingRectangle() # MBR enclosing all children
5        self.children = [] # List of RTreeNodes or spatial objects
6        
7    def get_enclosing_mbr(self) -> 'MinimumBoundingRectangle':
8        if not self.children:
9            return MinimumBoundingRectangle()
10        union_mbr = self.children[0].mbr.clone()
11        for child in self.children[1:]:
12            union_mbr.expand_to_include(child.mbr)
13        return union_mbr

2 min read•1 page

R-Trees insert elements dynamically. To insert a new object, the algorithm recursively traverses down by picking the child bounding box that requires the least area enlargement.

ChooseLeaf(node, new_object):

1. Enlargement Cost: Calculate area difference after enclosing the new object. 2. Least Area Enlargement: Route the object to the node with minimal enlargement cost. 3. Tie Breaking: Choose child node with smaller overall area on tie.

python

1def choose_leaf(node, new_object) -> RTreeNode:
2    if node.is_leaf:
3        return node
4        
5    best_child = None
6    min_enlargement = float('inf')
7    
8    for child in node.children:
9        # Calculate area expansion if child MBR expands to enclose new_object
10        area_before = child.mbr.area()
11        area_after = child.mbr.union(new_object.mbr).area()
12        enlargement = area_after - area_before
13        
14        if enlargement < min_enlargement:
15            min_enlargement = enlargement
16            best_child = child
17            
18    return choose_leaf(best_child, new_object)

New Object Position X

-1.50

1 min read•1 page

R-Tree search processes overlaps recursively. If the query region intersects a node's Minimum Bounding Rectangle, we descend; otherwise, the entire branch is pruned.

SearchRTree(node, query_rect):

1. MBR Intersection: Check if query boundaries overlap the node's bounds. 2. Branch Pruning: Skip searching child branches whose bounding boxes do not overlap. 3. Multiple Branches: Because child bounds can overlap, we may need to traverse multiple branches.

python

1def search_rtree(node, query_rect, results):
2    # Base Case: check if node's MBR intersects the query rectangle
3    if not node.mbr.intersects(query_rect):
4        return # Prune this branch immediately
5        
6    if node.is_leaf:
7        for obj in node.children:
8            if obj.mbr.intersects(query_rect):
9                results.append(obj)
10    else:
11        for child in node.children:
12            search_rtree(child, query_rect, results)

Query Box Position X

-1.00

2 min read•1 page

Deletion in R-Trees handles node underflow (fewer than $m$ entries) differently than B-Trees. Instead of adjacent borrowing, underflowed R-Tree nodes are deleted entirely, and their remaining elements are re-inserted into the tree from the root. This forces global reconstruction, keeping bounding boxes tightly bound.

CondenseTree(node, reinsert_list):

1. Underflow check: If child entries drop below minimum $m$, remove the node from parent. 2. Re-insertion queue: Collect orphaned child elements into a list. 3. Root Re-insertion: Re-insert elements normally, optimizing area expansion.

python

1def delete_rtree(node, entry, reinsert_list=None) -> bool:
2    if reinsert_list is None:
3        reinsert_list = []
4
5    # 1. Find leaf and remove element
6    if node.is_leaf:
7        if entry in node.children:
8            node.children.remove(entry)
9            return True
10        return False
11
12    # 2. Traverse down child nodes
13    for child in node.children:
14        if overlaps(child.mbr, entry.mbr):
15            if delete_rtree(child, entry, reinsert_list):
16                # Handle underflow: node drops below minimum capacity m
17                if len(child.children) < m:
18                    node.children.remove(child)
19                    reinsert_list.extend(child.get_all_elements())
20                return True
21
22    return False

Delete Object Index

0.00