这是一个关于实践中通常要做什么的问题。
假设我们有一个有一个条目的基数树（无论出于何种原因，都可以将其视为一个单独的条目进行演示）：
"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"one_answers"sts真的…"创建新的字符串（字符数组，不管怎样）。这需要许多操作，即使我们的新词"team"很短。
或者，我们可以使用"te"one_answers"sts真的…"标签，标签可以包含对同一原始字符串的引用，以及开始/结束值，即：
[0, 2] for "te"
和
[2, <whatever it is>] for "sts are really..."
这样我们就避免了任何复制，并且"团队"的插入时间只取决于"团队"长度，而不取决于其他字符串的长度，即在这种情况下"测试真的……"。
因此，问题在于O(k)中的k是指插入的字符串的长度，还是迄今为止最长的字符串。
显然，后一种实现更难，并且在实践中可能会使用更多的内存（因为端点的存储），但理论上最坏的情况time似乎得到了改进。
我想知道是否有人知道在实践中通常会做什么？
感谢
编辑：我想后一种实现的一个问题是删除。如果你后来插入了"心灵感应"，但删除了"测试真的很难……"，"te"边缘将保留，并且仍然引用了比所需长度长得多的字符串。
删除键的算法是找到其叶节点，将其删除，如果该节点的父节点正好有另一个子节点，则将这两个节点拼接。
假设边缘标签作为索引对存储到整个密钥中，则可以通过调整剩余子项的较低索引来完成拼接。若要"垃圾收集"已删除密钥的所有其他实例，可以向根扫描，重写涉及已删除键的边缘标签以引用同级。在最坏的情况下，我们必须一直扫描回根，渐近运行时间不会增加，但对于随机操作，预期的重写次数是恒定的。目前尚不清楚这些开销是否值得保存副本。