k-d tree

From Wikipedia, the free encyclopedia

(Redirected fromKd-tree)

Jump to:navigation,search

A 3-dimensional k-d tree. The first split (red) cuts the root cell (white) into two subcells, each of which is then split (green) into two subcells. Finally, each of those four is split (blue) into two subcells. Since there is no more splitting, the final eight are called leaf cells.

Incomputer science, a k-d tree (short for k-dimensionaltree) is aspace-partitioningdata structure for organizingpoints in a k-dimensionalspace. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g.range searches andnearest neighbor searches). k-d trees are a special case ofbinary space partitioning trees.

Informal description

The k-d tree is abinary tree in which every node is a k-dimensional point. Every non-leaf node can be thought of as implicitly generating a splittinghyperplane that divides the space into two parts, known as subspaces. Points to the left of this hyperplane represent the left sub-tree of that node and points right of the hyperplane are represented by the right sub-tree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right sub tree. In such a case, the hyperplane would be set by the x-value of the point, and itsnormal would be the unit x-axis.[1]