我试图建立一个 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 的列表?
我感谢任何和所有的帮助,谢谢!
-斯蒂芬