KD-tree

释义 Definition

KD-tree（k-d tree）：一种用于在k 维空间中组织点数据的树形数据结构，常用于最近邻搜索、范围查询等（尤其在低到中等维度时效果较好）。

发音 Pronunciation (IPA)

/ˌkeɪˈdiː triː/

例句 Examples

We built a KD-tree to speed up nearest-neighbor searches.
我们构建了一棵 KD-tree 来加速最近邻搜索。

In computer graphics, a KD-tree can organize 3D points so that range queries and collision checks become more efficient.
在计算机图形学中，KD-tree 可以组织三维点数据，从而让范围查询与碰撞检测更高效。

词源 Etymology

KD-tree 中的 k 表示 “k-dimensional（k 维的）”，d 是 “dimension（维度）” 的缩写；整体意思就是“用于 k 维空间的树”。该结构作为多维数据索引方法之一，在计算几何与检索问题中被广泛使用。

相关词 Related Words

• Binary Tree
• Bst
• Nearest Neighbor
• Range Query
• Spatial Index
• R-tree
• Quadtree
• Ball Tree

文献与作品 Literary / Notable Works

• Jon Louis Bentley：“Multidimensional Binary Search Trees Used for Associative Searching”（1975）——KD-tree 的经典提出与讨论论文
• **Mark de Berg et al.**：Computational Geometry: Algorithms and Applications ——在多维搜索、范围查询等章节中讨论 KD-tree
• **Thomas H. Cormen et al.**：Introduction to Algorithms（CLRS）——在与几何数据结构/多维检索相关内容中提及 KD-tree（不同版本章节安排略有差异）