2

我想扩展一个 kd-tree (2D) 类，以便能够删除节点（点）。这种移除应该在不必重建树的大部分部分的情况下进行。这些幻灯片中描述的算法，在幻灯片 13 上似乎是我所追求的。但是，按照幻灯片 7 中的“findmin()”描述，我遇到了麻烦，该描述用于节点删除算法。

问题

  1. 倒数第二行的“i”是什么意思？（也许这是作者的一个错误，因为它没有在其他地方引用？）

  2. “whichAxis”到底是什么？它是我们想要最接近的分裂超平面的深度吗？

  3. 什么是“最小（）”，最小化？我虽然这将是到轴的距离，但在我看来，作者正在最小化这些点，这对我来说没有意义。

4

2 回答 2

4

(1) 我认为 i是一个错字；在我的实现中我没有任何类似的东西，而且它似乎工作正常（着名的遗言......）。

(2) whichAxis是您要在其中搜索最小值的平面。因此在二维数据中，它将是 x 或 y。例如，对于点 (20,40) 和 (40,20)，一个是 x 中的最小值，另一个是 y 中的最小值。当您开始搜索替换节点时，您应该知道必须在哪个分割平面中搜索。

(3) 幻灯片写的有点奇怪。您想在适当的平面中找到最小值。也许这会澄清一点（c＃）。我的实现是针对使用东距和北距作为 x 和 y 的数据集。minAxis 只是一个布尔值，因为我只有两个平面。

bool winner = minAxis ? (left.Easting < right.Easting) : (left.Northing < right.Northing);
return winner ? left : right;

...其中left和right是从我们所在节点的左右子树中递归搜索的最小值。如果它更清晰，我可以发布完整的函数:-)

于 2010-03-17T11:55:07.223 回答
2

如果要删除给定 kd-tree 中的 nodeA

(1) 如果 nodeA 是叶节点，则将其设为 null

(2) 如果nodeA不是叶子节点 

Assume nodeA split by x , you have two choice

1. find the largest nodeB (whose X is the largest) in left   
2. find the minimum nodeB (whoes X is the minimum) in right  (This pdf prefer it)

笔记：

如果你把 nodeB 等于 nodeA 放在 nodeA.right 下，你应该选择 2

如果你把 nodeB 等于 nodeA 放在 nodeA.left 下，你应该选择 1

之后，将 nodeA 替换为 nodeB 并删除 nodeB 。

于 2013-05-22T04:23:33.307 回答