algorithm - 从二维 kd 树中删除一个元素

Question

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

问题

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

2. “whichAxis”究竟是什么？是我们最接近的 split 超平面的深度吗？

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

Answer 1

(1) 我认为 i 是错字；我在实现它时没有类似的东西，而且它似乎工作正常(著名的遗言......)。

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

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

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

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