我有一个包含单词所有后缀的三元搜索树。在这个结构中构造和搜索单词的时间复杂度是多少？
例子：
一个单词banana$，有后缀banana$,anana$,nana$,ana$,na$,a$,$ 并且按照词典顺序$,a$,ana$,anana$,banana$,na$,nana$ .
以平衡形式在三元搜索树中插入所有后缀为：anana$,a$,$,ana$,na$,banana$,nana$。
问问题
230 次
1 回答
0
一般来说，将某些内容插入 TST 所需的时间是 O(L log |Σ|)，其中 L 是字符串的长度，而 Σ 是字符串中允许的字符集。这样做的原因是添加每个单独的字符需要时间 O(log |Σ|) 因为您将每个字符添加到最多 |Σ| 的 BST 中。元素。对于您描述的示例，您要添加长度为 1、2、3、...、n 的字符串，因此运行时间为 O(n 2 log |Σ|)。
也就是说，我认为您可以通过更间接的路线来加快速度。三叉搜索树可以被认为是一个 trie，其中每个节点的子指针存储在一个二叉搜索树中。如果您只想尝试所有后缀，则可能需要查看专门用于表示该信息的后缀树。对于长度为 n 的字符串，它们可以在 O(n) 时间内构建。
于 2015-11-18T17:30:28.617 回答