Pav*_*avi 16 string algorithm autocomplete trie data-structures
我已经通过尝试和三元搜索树,我对它们有一些问题.我用Google搜索了答案,但我无法得到具体答案.所以,这是我的问题.
如果尝试空间效率低并且TST结合了最好的BST和尝试,这是否意味着尝试几乎根本不使用？
假设TST用于自动完成,那么对于Google来说,它会如何运作？我的意思是,实际上我们没有一套固定的单词等等,所以如何构建TST的树？
tem*_*def 17
尝试和三元搜索树代表时间/空间权衡.如果你的字母表中有k个符号,则trie中的每个节点都有k个指针加上一个额外的位,表示节点是否编码一个字.查找长度为L的单词总是需要时间O(L).三元搜索树每个节点存储三个指针,加上一个字符和一个位用于节点是否编码一个字.查找长度为L的单词需要时间O(L log k).(如果你有一个静态三元搜索树,你可以使用权重平衡树来构建TST ,这会将查找时间提高到O(L + log k),但会使插入过于昂贵.)
对于trie中的每个节点都使用其大部分子节点的情况,Trie比三元搜索树具有更高的空间效率和时间效率.如果每个节点存储相对较少的子节点,则三元搜索树的空间效率更高.通常来说,尝试比三元搜索树快得多,因为需要更少的指针间接.
所以在排序方面,两种结构都不比其他结构严格好.这取决于存储的单词.
为了简单起见,简洁的尝试开始成为上述两种方法的可行替代方案.尽管查找时间往往要慢得多,但它们的空间使用效果要好于尝试.同样,它取决于应用程序是否会比其他两个选项更好或更差.
至于如何构建它们 - 尝试和三元搜索树都支持有效插入单个单词.它们不需要事先用固定的单词构建.
希望这可以帮助!