Trees & Searches

1 min read•1 page

A tree is a hierarchical data structure consisting of nodes connected by directed edges. It has a single Root node, internal Nodes, and terminal Leaves.

Tree(root):

1. Root: The top node in the tree. 2. Leaf: A node with no children. 3. Height: The length of the longest path from the root to a leaf. 4. Depth: The length of the path from a node to the root.

python

1class Node:
2    def __init__(self, value):
3        self.value = value
4        self.children = [] # Dynamic list of child nodes
5
6    def add_child(self, child_node):
7        self.children.append(child_node)
8
9    def is_leaf(self) -> bool:
10        return len(self.children) == 0
11
12    def get_height(self) -> int:
13        if self.is_leaf():
14            return 0
15        return 1 + max(child.get_height() for child in self.children)

Tree Depth/Height Limit

3.00

2 min read•1 page

Spatial partition trees optimize queries by dividing coordinate spaces. This allows fast execution of fundamental geographic and geometric lookup operations.

SearchTypes:

1. Nearest Neighbor (NN): Finds the single closest node to a query coordinate. 2. Range Query: Retrieves all nodes situated within a specified radius or bounding box. 3. Collision/Clash Detection: Checks if bounds or primitives overlap.

python

1class SpatialSearch:
2    def range_query(self, query_point, radius, points) -> list:
3        """Finds all points within a certain radius."""
4        results = []
5        for p in points:
6            dist = query_point.distance_to(p)
7            if dist <= radius:
8                results.append(p)
9        return results
10
11    def nearest_neighbor(self, query_point, points):
12        """Finds the single closest point in space."""
13        closest_point = None
14        min_dist = float('inf')
15        for p in points:
16            dist = query_point.distance_to(p)
17            if dist < min_dist:
18                min_dist = dist
19                closest_point = p
20        return closest_point

Range Query Radius

4.50

Query Point X

0.00

2 min read•1 page

Building a spatial tree requires recursively partitioning a set of coordinates. At each step, a splitting axis is chosen, points are sorted, and the space is subdivided.

TreeBuild(Points, Depth):

1. Pivot Selection: Often the median coordinate along the splitting axis to ensure a balanced tree. 2. Recursive Splitting: Left child gets coordinates lower than the pivot; right child gets coordinates higher. 3. Stopping Criteria: Subdivision terminates when depth limit is met or leaf capacity falls below a threshold.

python

1def build_spatial_tree(points, depth=0, max_depth=3):
2    if len(points) == 0 or depth >= max_depth:
3        return LeafNode(points)
4        
5    # Alternating splitting axis
6    axis = depth % 2 # 0 for X, 1 for Y
7    
8    # Sort points to find median
9    points.sort(key=lambda p: p[axis])
10    median_idx = len(points) // 2
11    pivot = points[median_idx]
12    
13    # Partition points
14    left_points = points[:median_idx]
15    right_points = points[median_idx:]
16    
17    # Recursively build children
18    left_child = build_spatial_tree(left_points, depth + 1, max_depth)
19    right_child = build_spatial_tree(right_points, depth + 1, max_depth)
20    
21    return SplitNode(pivot, axis, left_child, right_child)

Construction Split Level

2.00

3 min read•1 page

Querying spatial trees is accelerated by recursive backtracking and pruning. By checking bounding planes first, we can skip whole subtrees without searching their nodes.

QueryTraversal(node, query):

1. Descending Branch: Walk down to the leaf node containing the query point. 2. Backtracking: Climb back up, evaluating distance to parent node coordinates. 3. Pruning: If distance to splitting boundary exceeds current best distance, skip opposite sub-tree.

python

1def search_tree(node, query_point, best_dist=float('inf'), best_node=None):
2    if node is None:
3        return best_node, best_dist
4        
5    # Calculate distance to current node
6    dist = query_point.distance_to(node.point)
7    if dist < best_dist:
8        best_dist = dist
9        best_node = node
10        
11    # Decide which branch to search first
12    axis = node.axis
13    if query_point[axis] < node.point[axis]:
14        first_branch = node.left
15        second_branch = node.right
16    else:
17        first_branch = node.right
18        second_branch = node.left
19        
20    # Search closer branch recursively
21    best_node, best_dist = search_tree(first_branch, query_point, best_dist, best_node)
22    
23    # Pruning: check if we need to search opposite branch
24    plane_dist = abs(query_point[axis] - node.point[axis])
25    if plane_dist < best_dist:
26        # Opposite branch might contain closer points
27        best_node, best_dist = search_tree(second_branch, query_point, best_dist, best_node)
28        
29    return best_node, best_dist

Traversal Step Index

0.00