从二维 kd 树中删除元素
我想扩展 kd-tree (2D) 类以能够删除节点（点）。这种移除应该在不必重建树木的大部分的情况下进行。第 13 张幻灯片中描述的算法似乎就是我所追求的。然而，我在遵循幻灯片 7 上的“findmin()”描述时遇到了麻烦，该描述用于节点删除算法。
问题
倒数第二行中的“i”是什么意思？ （也许这是作者的一个错误，因为它没有在其他地方引用？）
“whichAxis”到底是什么？它是我们想要最接近的分裂超平面的深度吗？
什么是“minimum()”，最小化？我虽然这将是到轴的距离，但在我看来，作者正在最小化点，这对我来说没有意义。
I would like to extend a kd-tree (2D) class to be able to remove nodes (points). This removal should be conducted without having to rebuild large sections of the tree. The algorithm described in these slides, on slide 13 seems to be what I am after. However, I am trouble following the description of "findmin()" found on slide 7, which is utilized in the node removal algorithm.
Questions
What does the "i" mean on the second to last line? (Maybe this is a mistake by the author, as it is not referenced elsewhere?)
What exactly is "whichAxis"? Is it the depth of the splitting hyperplane we want to get nearest to?
What is "minimum()", minimizing? I though this would be the distance to the axis, but it looks to me like the author is minimizing the points, which doesn't make sense to me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
(1) 我认为i是一个拼写错误；我在实现它时没有类似的东西，而且它似乎工作得很好（著名的最后一句话......）。
(2) whichAxis 是您要搜索最小值的平面。因此在二维数据中，它将是 x 或 y。例如，对于点 (20,40) 和 (40,20)，一个是 x 中的最小值，另一个是 y 中的最小值。当你开始搜索替换节点时，你应该知道你必须在哪个分割平面中搜索。
(3) 幻灯片写得有点奇怪。您想要找到适当平面中的最小值。也许这会澄清一点（c#）。我的实现是针对使用 东距和北距 作为 x 和 y 的数据集。 minAxis 只是一个布尔值，因为我只有两个飞机。
...其中 left 和 right 是从我们所在节点的左子树和右子树中递归搜索的最小值。我可以发布完整的函数，如果它使它更清楚:-)
(1) I think i is a typo; I don't have anything like that in my implementation of it, and it appears to work fine (famous last words..).
(2) whichAxis is the plane you're searching for the minimum in. So in two-dimensional data, it'll be either x or y. E.g. for points (20,40) and (40,20), one is the minimum in x and the other in y. When you start searching for a replacement node, you should know which splitting plane you have to search in.
(3) The slide is written a little strangely. You want to find the minimum value in the appropriate plane. Maybe this will clarify a little (c#). My implementation is for a dataset using eastings and northings as x and y. minAxis is just a bool, as I only ever have two planes.
...where left and right are the minimum values recursively searched for from the left and right child trees of the node we're in. I can post the full function if it makes it clearer :-)
如果要删除给定kd树中的nodeA
(1) 如果nodeA是叶节点，只需将其设置为null
(2) 如果nodeA不是叶节点
注意：
如果你把nodeB等于nodeA放在nodeA.right下，你应该选择2
如果你把nodeB等于nodeA放在nodeA.left下，你应该选择1
之后，用nodeB替换nodeA并删除nodeB。
If you want to delete a nodeA in a given kd-tree
(1) if nodeA is a leaf node ,just make it to null
(2) if nodeA is not a leaf node
Note:
if you put the nodeB equals nodeA under nodeA.right ,you should choose 2
if you put the nodeB equals nodeA under nodeA.left , you should choose 1
After that ,replace nodeA with nodeB and delete nodeB .