本页使用了标题或全文手工转换

K-d树

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

计算机科学里,k-d树k-维的缩写)是在k欧几里德空间组织的数据结构。k-d树可以使用在多种应用场合,如多维键值搜索(例:范围搜寻及最邻近搜索)。k-d树是空间二分树Binary space partitioning )的一种特殊情况。

简介[编辑]

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

==k-d树的运算

建立k-d树[编辑]

有很多种方法可以选择轴垂直分割面( axis-aligned splitting planes ),所以有很多种建立k-d树的方法。 最典型的方法如下:

  • 随着树的深度轮流选择轴当作分割面。(例如:在三维空间中根节点是 x 轴垂直分割面,其子节点皆为 y 轴垂直分割面,其孙节点皆为 z 轴垂直分割面,其曾孙节点则皆为 x 轴垂直分割面,依此类推。)
  • 点由垂直分割面之軸座標的中位数区分并放入子树

這個方法產生一個平衡的k-d樹。每個葉節點的高度都十分接近。然而,平衡的樹不一定對每個應用都是最佳的。

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;
        
    // Sort point list and choose median as pivot element
    select median by axis from pointList;
        
    // Create node and construct subtrees
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

插入元素[编辑]

移除元素[编辑]

平衡[编辑]

最鄰近搜索[编辑]

最鄰近搜索用來找出在樹中與輸入點最接近的點。

k-d樹最鄰近搜索的過程如下:

  1. 從根節點開始,遞迴的往下移。往左還是往右的決定方法與插入元素的方法一樣(如果输入点在分区面的左邊則進入左子節點,在右邊則進入右子節點)。
  2. 一旦移動到葉節點,將該節點當作"目前最佳點"。
  3. 解開遞迴,並對每個經過的節點執行下列步驟:
  1. 如果目前所在點比目前最佳點更靠近輸入點,則將其變為目前最佳點。
  2. 檢查另一邊子樹有沒有更近的點,如果有則從該節點往下找
  1. 當根節點搜尋完畢後完成最鄰近搜尋

外部链接[编辑]