0

这是一个关于在实践中通常会做什么的问题。

假设我们有一个带有一个条目的基数树（无论出于何种原因，将其视为一个用于演示的条目）：

"tests are really hard, no one likes taking tests, they're the worst"

然后我们要输入第二个条目

"team"

我们希望最终得到来自根的边缘

"te"

和两个边缘的，一个与

"sts are really hard, no one likes taking tests, they're the worst"

和一个

"am"

天真地，我们可以为“te”和“sts are really...”创建新的字符串（字符数组等）。这需要很多操作，即使我们的新词“团队”很短。

或者，我们可以让“te”和“sts are really...”标签可以包含对相同原始字符串的引用，以及开始/结束值，即：

[0, 2] for "te"

和

[2, <whatever it is>] for "sts are really..."

这样我们就避免了任何复制，并且“team”的插入时间仅取决于“team”的长度，而不取决于其他字符串的长度，即“tests are really...”在这种情况下。

所以问题在于kinO(k)是指插入的字符串的长度，还是迄今为止最长的字符串。

显然，后一种实现更难，并且在实践中可能会使用更多内存（因为存储端点），但似乎理论上最坏情况的时间得到了改善。

我想知道是否有人知道在实践中通常会做什么？

谢谢

编辑：我想后一种实现的一个问题会随着删除而出现。如果您稍后插入“心灵感应”，但随后删除了“测试真的很难......”，则“te”边缘将保留，并且仍然对字符串的引用比需要的要长得多。

4

1 回答 1

1

删除密钥的算法是找到它的叶子节点，将其删除，如果该节点的父节点恰好有另一个子节点，则将两者拼接。

假设边缘标签作为索引对存储到整个键中，则可以通过调整剩余孩子的较低索引来完成拼接。要“垃圾收集”已删除键的所有其他实例，可以向根方向扫描，重写涉及已删除键的边缘标签以引用同级。在最坏的情况下，我们必须一直扫描到根，不增加渐近运行时间，但对于随机操作，预期的重写次数是恒定的。目前尚不清楚这种开销是否值得保存的副本。

于 2014-09-05T16:12:47.547 回答