information-retrieval - 在 trie 中使用一个额外的字母存储相同的单词（例如：bull 和 bully）

Question

我们如何在同一个 trie 中存储像 (bull and bully) 和 (bid and bide) 这样的词？如果在bully 中的'y' 处有一个叶子节点，bull 是否仍然存储在同一个分支上？或者从第一个“l”开始会有两个分支，一个通向“l”，另一个通向“l”和“y”？

标签： information-retrievaltrie

Answer 1

从树的根节点，您可以通过将字符作为键传递给子节点来存储所有单词。我们知道如果有一个词尾布尔属性是真的，我们知道我们的 trie 中有那个词。

因此，对于“公牛”和“欺负”，我们首先有root > b > u > l > l分支，对于最后一个“l”节点，我们将词尾布尔属性设置为 true，我们将添加一个它的子节点是“y”节点，具有词尾布尔属性也为真。所以，我们最终会得到root > b > u > l > l > y；最后的 l 和 y 具有词尾布尔属性是真的，所以我们理解它们是词。

请查看这些页面以获得更清晰的信息：

• https://www.geeksforgeeks.org/trie-insert-and-search/
• https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014

干杯