K-d tree

As explained in Advanced Algorithms and Data Structures

A k-d tree is a binary space-partitioning tree that organizes points in k-dimensional space by alternating coordinate-based comparisons at successive levels.

Suppose a warehouse service must find the closest hub to a location on a map. Scanning every warehouse for every request is costly. A k-d tree indexes points so that nearest-neighbor and region queries can skip parts of the search space. section 10.1 section 8.3

A k-d tree is a binary search tree of k-coordinate points. At depth i, a node compares coordinate i mod k. Its point acts as a pivot: points on one side of the resulting split go left, and points on the other side go right. In two dimensions, splits alternate between x and y, partitioning the plane into progressively smaller regions. section 9.2.1 section 9.2

Figure 9.8 An example k-d tree for a 2-D dataset. On the left, the tree representation. On the right, a visualization of (a portion of) the 2-D Cartesian plane, where the origin is at the center of the square. The vertical lines pass through nodes A, D, and E and correspond to splits along the x coordinate. The horizontal lines are drawn through nodes B, C, and F, and correspond to splits along the y coordinate.

Compare each node’s position in the tree with its vertical or horizontal split in the plane. section 9.3

The split rule drives the main operations:

• For exact search, check the whole point for equality, then use the current split coordinate to choose a child. Insertion follows the same path and adds a node at an empty child; the shown implementation ignores duplicate points. section 9.3.1 section 9.3.2
• For nearest-neighbor search, visit the target’s side first while tracking the best distance. Backtrack into the opposite side when its split plane is closer than the best candidate; otherwise prune that branch. Several nearest neighbors can be tracked with a bounded priority queue. section 9.3.5
• Deletion requires more care than ordinary BST deletion: promoting a child changes its split level, while a replacement minimum for a chosen coordinate may lie deep in a subtree. section 9.3.4

Shape matters. An unfortunate insertion order can produce linear height; a balanced tree gives logarithmic-height search and insertion. If the points are known in advance, recursively select a median on the current split coordinate and build the two subtrees. This construction takes O(n log n) time and O(n) memory. Later updates do not automatically preserve balance. section 9.2.2 section 9.3.3

For a balanced tree, exact search and insertion take O(log n) time. Nearest-neighbor search can still inspect every point in an adverse case, although pruning helps in practice. Its advantage weakens as dimension grows; frequent updates, poor memory locality, and non-point objects are further reasons to consider another index. section 9.3.7 section 9.4

Assigning points to centroids

In k-means, build a k-d tree over the current centroids and query it for each point’s nearest centroid. Rebuild the tree each iteration because the centroids change. This trades construction work for faster classification when there are enough centroids; tests with very few centroids favored brute force. section 12.2.4

How Advanced Algorithms and Data Structures covers it

How deep it goes

Develops split-coordinate construction and recursive operations, including deletion, balanced construction, nearest-neighbor backtracking, and complexity limits.

Examples

Uses mapped warehouses, two-dimensional tree diagrams, RGB color matching, and centroid assignment.

What it assumes

Assumes basic binary search tree familiarity while defining coordinate cycling and showing how it partitions multidimensional space.

What you can do after

Build it from scratch to index points and implement exact and nearest-neighbor search while judging when balancing or dimensionality limits its value.

How it connects

Connects binary search trees, spatial partitioning, nearest-neighbor search, range queries, and k-means clustering.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Machine Learning for Tabular Data: XGBoost, Deep Learning, and AIA k-dimensional tree, or KDTree, is a space-partitioning data structure that organizes points for efficient multidimensional nearest-neighbor queries.
• 

  liveBookmanning.com
  Outlier Detection in PythonKDTree is a binary space-partitioning tree that recursively divides points by coordinate dimensions to support nearest-neighbor and range queries.

Compare how 3 books explain k-d tree →

Related concepts

• data structurekind of · A data structure is an organized representation of data and its relationships that supports defined operations for storing, accessing, or modifying it.
• similarity searchuses · Similarity search is a retrieval technique that finds or ranks items by comparing their representations with a query according to a similarity or distance measure.
• binary search treekind of · A binary search tree is a binary tree whose nodes follow an ordering relation placing keys in designated left and right subtrees relative to each node.
• ball treealternative to · A ball tree is a hierarchical metric-space data structure that recursively partitions points into nested balls for efficient spatial queries.
• SciPyimplemented by · SciPy is an open-source Python library providing algorithms and numerical utilities for scientific and technical computing.
• brute-force searchalternative to · Brute-force search systematically tests many or all candidates in a defined search space, without relying on selective shortcuts to narrow it.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.