Trees & Searches

2 min read•1 page

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)

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 Depth/Height Limit

3.00

2 min read•1 page

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

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

Range Query Radius

4.50

Query Point X

0.00

2 min read•1 page

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)

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.

Construction Split Level

2.00

3 min read•1 page

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

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

Traversal Step Index

0.00

Related Concepts

Algorithms

Computational geometry algorithms, spatial structures, and physical simulations

Explore concept →

Spatial Trees

KD-Trees, Octrees, and BVHs.

Explore concept →

Binary Trees

Binary node structures, BST insertions, searches, and traversal pathways.

Explore concept →