我经历了尝试和三元搜索树，我对它们有一些疑问。我已经用谷歌搜索了答案，但我无法得到具体的答案。所以，这是我的问题。
如果尝试空间效率低且 TST 结合了 BST 和尝试的优点，这是否意味着实际上根本不使用尝试？
假设 TST 用于自动完成，..在谷歌的情况下如何工作？我的意思是实际上我们没有一组固定的单词等，..那么如何构建 TST 的树？
问问题
8773 次
1 回答
20
尝试和三元搜索树代表时间/空间权衡。如果您的字母表中有 k 个符号，则 trie 中的每个节点都包含 k 个指针以及一个额外的位，用于判断该节点是否对单词进行编码。查找长度为 L 的单词总是需要时间 O(L)。三元搜索树为每个节点存储三个指针，加上一个字符和一个位，用于判断该节点是否对一个词进行编码。查找长度为 L 的单词需要时间 O(L log k)。（如果你有一个静态三元搜索树，你可以使用权重平衡树来构建 TST ，这将查找时间缩短到 O(L + log k)，但插入的代价非常高。）
对于 trie 中的每个节点都使用其大部分子节点的情况，Trie 比三叉树搜索树的空间效率和时间效率要高得多。如果每个节点存储的子节点相对较少，则三叉搜索树的空间效率要高得多。通常来说，尝试比三元搜索树快得多，因为需要的指针间接更少。
所以在排序上，没有一种结构严格来说比另一种更好。这取决于存储的单词。
稍微混淆一下，简洁的尝试开始成为上述两种方法的可行替代方案。尽管查找时间往往要慢得多，但它们的空间利用率比尝试更好。同样，这取决于应用程序它们是否会比其他两个选项更好或更差。
至于如何构建它们 - 尝试和三元搜索树都支持单个单词的有效插入。它们不需要预先从一组固定的单词中构建出来。
希望这可以帮助！
于 2012-06-10T17:14:04.500 回答