algorithm - 删除 BK 树中的节点

Question

我在 many 中看到了许多不同的 BK 树实现。 different languages ，而且实际上它们似乎都没有包含从树中删除节点的方法。

偶the original article where BK Trees were first introduced没有提供有关节点删除的有意义的见解，因为作者只是建议标记要删除的节点，以便将其忽略:

The deletion of a key in Structures 1 [the BK Tree] and 2 follows a process similar to that above, with special consideration for the case in which the key to be deleted is the representative x° [root key]. In this case, the key cannot simply be deleted, as it is essential for the structure information. Instead an extra bit must be used for each key which denotes whether the key actually corresponds to a record or not. The search algorithm is modified correspondingly to ignore keys which do not correspond to records. This involves testing the extra bit in the Update procedure.

虽然理论上可以正确删除 BK 树中的节点，但是否可以在线性/亚线性时间内这样做？

Answer 1

While it may be theoretically possible to properly delete a node in a BK Tree, is it possible to do so in linear/sublinear time?

如果您想从 BK 树中物理删除它，那么我想不出一种方法可以在所有情况下在线性时间内执行此操作。考虑 2场景，当一个节点被删除时。请注意，我没有考虑与计算 Levenshtein 距离相关的时间复杂度，因为该操作不依赖于单词的数量，尽管它也需要一些处理时间。
删除非根节点

在树中查找节点的父节点。

保存节点的子节点。

取消父节点对节点的引用。

重新添加每个子节点，就好像它是一个新节点一样。

在这里，即使步骤 1可以在 O(1) 中完成，步骤 2和 4更贵。插入单个节点是 O(h)，其中 h 是树的高度。更糟糕的是，这必须为原始节点的每个子节点完成，因此它将是 O(k*h)，其中 k 是子节点的数量。
删除根节点

不使用之前的根节点从头开始重建树。

在最好的情况下，重建一棵树至少需要 O(n)，否则需要 O(h*n)。
替代方案
这就是为什么最好不要物理删除节点，而是将其保留在树中并将其标记为 deleted .这样，它会像以前一样用于插入新节点，但会从拼写错误的单词的建议结果中排除。这可以在 O(1) 中完成。