删除 BK 树中的节点

Question

我已经在许多 不同的 语言中看到了 BK 树的许多不同实现，实际上它们似乎都没有包含从树中删除节点的方法。

即使最初介绍 BK 树的原始文章也没有提供关于节点删除的有意义的见解，因为作者只是建议标记要删除的节点，以便将其忽略：

删除结构1[BK树]和2中的键遵循与上述类似的过程，特别考虑要删除的键是代表x°[根键]的情况。在这种情况下，不能简单地删除密钥，因为它对于结构信息是必不可少的。相反，每个键必须使用一个额外的位来表示该键是否实际上对应于一条记录。相应地修改搜索算法以忽略与记录不对应的键。这涉及测试更新过程中的额外位。

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

Answer 1

虽然理论上可以正确删除 BK 树中的节点，但是否可以在线性/亚线性时间内完成此操作？

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

删除非根节点

1. 在树中查找该节点的父节点。
2. 保存节点的子节点。
3. 取消父节点对该节点的引用。
4. 重新添加每个子节点，就像它是一个新节点一样。

在这里，即使步骤1可以在 O(1) 内完成，步骤2和 的4成本也更高。插入单个节点的时间复杂度为 O(h)，其中 h 是树的高度。更糟糕的是，必须对原始节点的每个子节点执行此操作，因此它将是 O(k*h)，其中 k 是子节点的数量。

删除根节点

1. 从头开始重建树，而不使用以前的根节点。

在最好的情况下重建一棵树至少是 O(n) ，否则是 O(h*n) 。

替代解决方案

这就是为什么最好不要物理删除节点，而是将其保留在树中并将其标记为deleted。这样，它将像以前一样用于插入新节点，但将被排除在拼写错误单词的建议结果之外。这可以在 O(1) 内完成。