K-d树

维基百科,自由的百科全书
跳转至: 导航搜索
一个三维k-d树。第一次划分(红色)把根节点(白色)划分成两个节点,然后它们分别再次被划分(绿色)为两个子节点。最后这四个子节点的每一个都被划分(蓝色)为两个子节点。因为没有更进一步的划分,最后得到的八个节点称为叶子节点。

计算机科学里,k-d树k-维的缩写)是在k欧几里德空间组织的数据结构。k-d树可以使用在多种应用场合,如多维键值搜索。k-d树是二叉树的一种特殊情况。

简介[编辑]

k-d树是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两部分。在超平面左边的点代表节点的左子树,在超平面右边的点代表节点的右子树。超平面的方向可以用下述方法来选择:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照x轴划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样,超平面可以用该x值来确定,其法矢为x轴的单位向量

外部链接[编辑]