K-Dimensional Tree in Data Structure

A K-D Tree (K-Dimensional Tree) is a binary tree used to organize points in a k-dimensional space, enabling efficient operations like nearest-neighbor search and range search.

How It Works

At each level of the tree, points are split along one of the k dimensions, cycling through dimensions as depth increases (e.g., split by x at depth 0, by y at depth 1, back to x at depth 2, and so on for 2D points). The median point along the chosen dimension becomes the node, dividing the remaining points into left and right subtrees.

class KDNode:
    def __init__(self, point, left=None, right=None):
        self.point = point
        self.left = left
        self.right = right

def build_kdtree(points, depth=0):
    if not points:
        return None
    k = len(points[0])
    axis = depth % k
    points.sort(key=lambda p: p[axis])
    median = len(points) // 2
    return KDNode(
        point=points[median],
        left=build_kdtree(points[:median], depth + 1),
        right=build_kdtree(points[median + 1:], depth + 1)
    )

Complexity

Applications

• Nearest-neighbor search in machine learning (e.g., k-NN classification).
• Spatial indexing in GIS and mapping applications.
• Collision detection in computer graphics and games.
• Database indexing for multi-dimensional data.