KDTREE简介及算法实现

简介：
K-D Tree是一种高效的多维空间数据结构，用于存储和查询k维空间中的点。本篇文章将简要介绍其原理，并探讨其实现方法。 Over the past six weeks, we have explored a variety of STL container classes. Weve examined linear vectors and deques as well as associative maps and sets. A common property among all these containers is that they are exact: an element either exists in a set or it does not; a value either appears at a specific position within a vector or it doesnt. For most applications, this behavior is precisely what we need. However, there are scenarios where the question of interest shifts from Is X present in this container? to What value within the container is most similar to X?. Queries like these frequently occur in data mining, machine learning, and computational geometry. In this assignment, you will implement a specialized data structure called a kd-tree (short for “k-dimensional tree”), which efficiently supports such similarity queries.