删除 BK 树中的节点
Deleting a node in a BK Tree
我在 many different languages 中看到了 BK 树的许多不同实现，从字面上看，其中 none 似乎包含一种从树中删除节点的方法。
甚至 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 树中的节点，但是否可以在 linear/sublinear 时间内完成？
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-Tree 中物理删除它，那么我想不出一种方法可以在所有情况下在线性时间内完成此操作。考虑删除节点时的 2 个场景。请注意，我没有考虑与计算 Levenshtein 距离相关的时间复杂度，因为该操作不依赖于单词的数量，尽管它也需要一些处理时间。
删除非根节点
- 在树中找到节点的父节点。
- 保存节点的子节点。
- 使父节点对节点的引用无效。
- 重新添加每个子节点，就好像它是一个新节点一样。
这里，即使步骤 1 可以在 O(1) 中完成，步骤 2 和 4 的成本要高得多。插入单个节点是 O(h)，其中 h 是树的高度。更糟糕的是，必须对原始节点的每个子节点都执行此操作，因此它将是 O(k*h)，其中 k 是子节点的数量。
删除根节点
- 在不使用之前的根节点的情况下从头开始重建树。
重建一棵树在最好的情况下至少需要 O(n)，否则为 O(h*n)。
备选方案
这就是为什么最好不要物理删除节点，而是将其保留在树中并将其标记为 deleted。这样它将像以前一样用于插入新节点，但将被排除在拼写错误的单词的建议结果之外。这可以在 O(1) 中完成。
我在 many different languages 中看到了 BK 树的许多不同实现，从字面上看，其中 none 似乎包含一种从树中删除节点的方法。
甚至 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 树中的节点，但是否可以在 linear/sublinear 时间内完成？
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-Tree 中物理删除它，那么我想不出一种方法可以在所有情况下在线性时间内完成此操作。考虑删除节点时的 2 个场景。请注意，我没有考虑与计算 Levenshtein 距离相关的时间复杂度，因为该操作不依赖于单词的数量，尽管它也需要一些处理时间。
删除非根节点
- 在树中找到节点的父节点。
- 保存节点的子节点。
- 使父节点对节点的引用无效。
- 重新添加每个子节点，就好像它是一个新节点一样。
这里，即使步骤 1 可以在 O(1) 中完成，步骤 2 和 4 的成本要高得多。插入单个节点是 O(h)，其中 h 是树的高度。更糟糕的是，必须对原始节点的每个子节点都执行此操作，因此它将是 O(k*h)，其中 k 是子节点的数量。
删除根节点
- 在不使用之前的根节点的情况下从头开始重建树。
重建一棵树在最好的情况下至少需要 O(n)，否则为 O(h*n)。
备选方案
这就是为什么最好不要物理删除节点，而是将其保留在树中并将其标记为 deleted。这样它将像以前一样用于插入新节点，但将被排除在拼写错误的单词的建议结果之外。这可以在 O(1) 中完成。