KD树/K-D树

本文理解翻译自:http://en.wikipedia.org/wiki/K-d_tree

k-d树(k-d tree)

 来自维基百科,自由的百科全书

简介

k-d树是二叉树的一种,树中每个节点都是一个多维(k-dimension)的数据点。每个非叶子节点都可以看做是隐含的分割超平面,该平面将空间分成两部分(也叫半空间)。超平面左边的点由k-d树的左子树表示,右边的点由右子树表示。选择超平面的方式为:树中的每个节点对应K个维度中的一维,超平面会垂直这个维度的坐标轴。例如,如果选择X轴做分割,那么所有X值小当前树节点的点都在当前树节点的左子树中,所有X值大于当前树节点的点都在当前树节点的右子树中。在这种情况下,超平面是通过点的x值来设置,它的法向量(normal)就是单位X轴。[1]

 Read more