Overview
A k-d Tree alternates or chooses split dimensions to organize points for nearest-neighbor and range queries.
CoreSource checked
k-d Tree
Indexes points by recursively splitting space along coordinate axes.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Spatial Index
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 8
- Code example
- Ready
- Visualization
- Ready
- Aliases
- KD Tree
Core Concepts
axis splitmedian partitionnearest-neighbor pruningbounding distance
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n) average query
Worst
O(n)
Space
O(n)
When to Use
- Use when nearest-neighbor or range search is needed in low-dimensional numeric space.
- Use when nearest-neighbor search is a central requirement.
When Not to Use
- Avoid when dimension is high enough that pruning becomes ineffective.
- Avoid when a simpler array, map, or list already meets the access pattern.
What It Does
- Splits points by axis
- Builds a binary spatial tree
- Prunes query regions by distance or bounds
Use Cases
- Nearest-neighbor search
- Range queries
- Low-dimensional point indexing
Inputs
- k-dimensional points
Outputs
- Binary spatial index
Key Formulas (1)
Prune test
skip far branch if distanceto split plane ≥ bestdistance
skip far branch if distance_to_split_plane >= best_distanceAvoids searching a branch that cannot contain a closer point.
Pseudocode
- 1.Choose a split axis
- 2.Partition points around a median
- 3.Build left and right subtrees recursively
- 4.During queries, visit near side first and prune far side when possible
Canonical Example
- Input
- points = [(1,2), (4,5), (2,3)]
- Output
- root split by x around (2,3)
- Explanation
- The tree partitions space so queries can skip far regions.
Implementation Notes
- Build from medians when static data is available.
- Keep update operations small and test invariants after insertions and deletions.
- Keep a tiny example with known output beside the implementation.
- Test updates and queries as sequences, not only one operation at a time.
Common Pitfalls
- A badly unbalanced tree can lose most query benefits.
- The advertised performance depends on maintaining the structure's invariants.
- Not defining boundary, empty, or degenerate inputs before implementation.
- Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow points split by alternating vertical and horizontal lines.
Step 1 of 4: Choose a split axis
data-structureNotes
k-d Trees work best in low or moderate dimensions.
Sources (1)
What each reference supports for this entry.
Bentley K-D Tree
PaperOriginal k-d tree reference for multidimensional associative search.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsBalanced KD-Tree Construction
Data Structures · Core
Balanced construction is a k-d tree build strategy that controls depth with median splits.
Compare with thisAlternative toQuadtree
Data Structures · Core
k-d trees split by coordinate axes, while quadtrees split space into fixed quadrants.
Compare with thisAlternativesRange Tree
Data Structures · Core
Range trees and k-d trees are alternative multidimensional indexing structures with different storage and range-query tradeoffs.
Compare with thisAlternativesSpatial Hash
Data Structures · Core
Spatial hashing and k-d trees are alternative spatial indexing strategies for nearby-object lookup.
Compare with thisRelationships
View full relationship pageAlternative toQuadtree
k-d trees split by coordinate axes, while quadtrees split space into fixed quadrants.
Related Algorithms
Tags
Data StructureTreeSpatial IndexNearest Neighbor