kdtree介绍与算法实现

kd树很基本的算法介绍和实现方法概括。全英文的文档。 Over the past six weeks, we've explored a wide array of STL container classes. You've seen the lin- ear vector and deque, along with the associative map and set. One property common to all these containers is that they are exact. An element is either in a set or it isn't. A value either appears at a particular position in a vector or it does not. For most applications, this is exactly what we want. However, in some cases we may be interested not in the question “is X in this container,” but rather “what value in the container is X most similar to?” Queries of this sort often arise in data mining, machine learning, and computational geometry. In this assignment, you will implement a special data structure called a kd-tree (short for “k-dimensional tree”) that efficiently supports this opera- tion.