4

我试图建立一个 kd-tree 来搜索一组点,但我对维基百科文章中“中位数”的使用感到困惑。为了便于使用,维基百科文章将 kd-tree 构造的伪代码声明为:

function kdtree (list of points pointList, int depth)
{
    if pointList is empty
        return nil;
    else
    {
        // 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;
    }
}

我对“选择中位数...”行感到困惑,仅仅是因为我不太确定在这里应用中位数的“正确”方法是什么。

据我所知,奇数(排序)数字列表的中位数是中间元素(又名,对于 5 个事物的列表,元素编号 3 或标准从零开始的数组中的索引 2),并且偶数大小数组的中位数是两个“中间”元素的总和除以 2(也就是,对于 6 个事物的列表,中位数是元素 3 和 4 - 或 2 和 3,如果为零 -索引 - 除以 2。)。

但是,当我们使用一组不同的点时,这个定义肯定在这里不起作用吗?那么如何为偶数大小的数字列表选择正确的中位数,尤其是长度为 2 的列表?

我感谢任何和所有的帮助,谢谢!

-斯蒂芬

4

2 回答 2

3

在我看来,您理解中位数的含义,但您对其他内容感到困惑。你是什​​么意思是不同的点集?

维基百科提供的代码是一个递归函数。您有一组点,因此您创建一个根节点并选择该组的中值。然后递归调用该函数 - 对于左子树,您传入一个参数,其中所有点都小于原始列表的分割值(中位数),对于右子树,您传入相等和更大的点。然后为每个子树创建一个节点,其中发生相同的事情。它是这样的:

First step (root node):
Original set: 1 2 3 4 5 6 7 8 9 10
Split value (median): 5.5

Second step - left subtree:
Set: 1 2 3 4 5
Split value (median): 3

Second step - right subtree:
Set: 6 7 8 9 10
Split value (median): 8

Third step - left subtree of left subtree:
Set: 1 2
Split value (median): 1.5

Third step - right subtree of left subtree:
Set: 3 4 5
Split value (median): 4

等等。

因此,根据进入该子树的一组数字(点、数据)为树中的每个节点选择中值。希望这可以帮助。

于 2010-05-28T07:32:14.223 回答
0

您必须选择一侧元素数量多于另一侧元素的轴。如果点的数量是奇数或点的位置不可能,只需选择一个轴以提供尽可能均匀的重新分区。

于 2010-05-28T07:13:37.697 回答