--- title: 'Multidimensional Trees' source: 'https://academia.sh/en/courses/data-structures/multidimensional-trees' course: 'Data Structures' language: en updated: '2026-08-17T18:08:03+00:00' license: 'CC BY-SA 4.0' --- # Multidimensional Trees Spatial queries, alternating splits in a k-d tree, nearest-neighbor search, pruning, and the curse of dimensionality. The search structures covered so far ordered along a single axis: at every node, the question "smaller or larger" was answered against a single value. Some data does not fit on a single axis. A point on a map carries two coordinates, a sensor reading carries temperature and humidity, a document embedding carries hundreds of numbers. The questions asked of such data are different too: **"which record is nearest to this point"** or **"which points lie inside this rectangle"**. ## Why One-Dimensional Structures Fall Short If points are ordered only by their first coordinate, points that are close on that axis can be found. But two points close in the first coordinate can be far apart in the second; the ordering carries no information about actual proximity. Even if two separate indexes are kept — one per axis — the result does not change: each index yields a candidate list along one axis, but computing their intersection requires walking every candidate. What is needed is a structure that splits the space by considering **all dimensions together**. ## The k-d Tree A **k-d tree** is the multidimensional generalization of the binary search tree. Its only difference is which dimension the comparison at each node is made against: the split dimension is chosen **alternately, based on depth**. In a two-dimensional set, the root splits on the first coordinate, its children on the second, and its grandchildren on the first again. Every node divides the space in two with a line; the subtrees correspond to these half-planes. ```python class KdNode: def __init__(self, point: tuple[float, ...], axis: int) -> None: self.point = point self.axis = axis self.left: "KdNode | None" = None self.right: "KdNode | None" = None def build_kd(points: list[tuple[float, ...]], depth: int = 0) -> KdNode | None: """Builds a balanced k-d tree by choosing the median point.""" if not points: return None dim = len(points[0]) axis = depth % dim # alternating split ordered = sorted(points, key=lambda p: p[axis]) mid = len(ordered) // 2 node = KdNode(ordered[mid], axis) node.left = build_kd(ordered[:mid], depth + 1) node.right = build_kd(ordered[mid + 1:], depth + 1) return node points = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)] root = build_kd(points) print(root.point, root.axis) # (7, 2) 0 print(root.left.point, root.right.point) # (5, 4) (9, 6) ``` The median point is chosen during construction, so the two subtrees end up equal in size and height stays at $O(\log n)$. When the median is selected via sorting, construction takes $O(n \log^2 n)$; with a linear-time selection algorithm, it drops to $O(n \log n)$. Selection algorithms are a topic of the **Algorithms** course. ## Nearest-Neighbor Search The core idea of the search is pruning: a subtree is never visited if it is certainly farther than the best candidate found so far. The steps are: 1. Descend the tree by checking which side the query point falls on; the leaf reached is the first candidate. 2. On the way back up, test at each node whether the node itself is closer. 3. If the distance to the splitting line is **smaller** than the best distance found so far, the other subtree is also visited; if it is larger, the entire subtree is ruled out. The third step provides all the efficiency: the distance to the splitting line is a lower bound on the distance to any point on that side. ```python def sq_dist(a: tuple[float, ...], b: tuple[float, ...]) -> float: """Squared distance; taking the square root would not change the ordering.""" return sum((x - y) ** 2 for x, y in zip(a, b)) def nearest(node: KdNode | None, target: tuple[float, ...], best=None, counter=None): """Returns (nearest point, number of nodes visited).""" counter = {"n": 0} if counter is None else counter if node is None: return best, counter["n"] counter["n"] += 1 if best is None or sq_dist(node.point, target) < sq_dist(best, target): best = node.point axis = node.axis diff = target[axis] - node.point[axis] near, far = (node.left, node.right) if diff < 0 else (node.right, node.left) best, _ = nearest(near, target, best, counter) # near side first if diff ** 2 < sq_dist(best, target): # pruning test best, _ = nearest(far, target, best, counter) return best, counter["n"] print(nearest(root, (9, 2))) # ((8, 1), 3) print(nearest(root, (4, 6))) # ((4, 7), 3) ``` In the first query, only three nodes of the six-point tree were visited; three nodes were pruned away. Squared distance is used to avoid computing a square root — an unnecessary operation as long as the ordering does not change. ## Range Query A rectangle (or multidimensional box) query uses the same pruning logic: if the node's splitting line lies entirely on one side of the query box, the other subtree is never visited. This is the spatial counterpart of the idea behind segment trees: the query is covered by a subset of the nodes in the tree. ## The Curse of Dimensionality The k-d tree's promise holds in low dimensions. As the number of dimensions grows, pruning stops working. The reason is intuitive: in a high-dimensional space, distances between points converge toward one another, and the distance to the splitting line comes out smaller than the best candidate almost every time. The pruning condition is never met, both subtrees are visited, and the search degenerates into a linear scan. The practical rule of thumb is: $n \gg 2^{k}$ must hold ($k$ being the number of dimensions). With twenty dimensions and a thousand points, a k-d tree is no faster than a linear scan — and it uses extra memory besides. This is not merely a data-structure detail; it is a general property of high-dimensional data, and it also sets the limit for distance-based methods in machine learning. Insertion and deletion are also possible, but a k-d tree cannot maintain its balance under these operations: no repair operation like rotation is defined for it. If the data changes frequently, the tree is rebuilt at intervals. ## Other Spatial Structures | Structure | Split shape | Suitable use | |---|---|---| | Grid | Fixed-size cells | Uniformly distributed data, fixed-radius queries | | Quadtree | Every node splits the area into four | Two-dimensional, uneven density | | k-d tree | Alternating single axis | Moderate dimension, point data | | R-tree | Bounding rectangles | Area data, not points; disk-based indexes | For high-dimensional data — such as document and image embeddings — exact nearest-neighbor search is abandoned in favor of **approximate** methods. These methods give probabilistic guarantees, much like the skip list from the linear structures topic, and form the basis of vector databases; they are covered in the AI Engineering curriculum. ## Summary - Spatial queries cannot be answered with one-dimensional ordering; proximity depends on all dimensions together. - A k-d tree chooses the split dimension alternately based on depth; every node divides the space in two. - Choosing the median point keeps height logarithmic. - Nearest-neighbor search uses the distance to the splitting line as a lower bound and prunes subtrees. - Squared distance is used to avoid computing a square root; it does not change the ordering. - As the number of dimensions grows, pruning loses its effect and the search degenerates into a linear scan; the practical rule of thumb is $n \gg 2^k$. ## Next Step Trees were acyclic, single-parent structures. When that constraint is lifted — when a node can have more than one "parent" and cycles are allowed — the resulting structure is far more general, and it is the natural model for problems such as networks, maps, and dependency relationships. The course's final topic covers graphs.