我正在寻找有关搜索树状数据结构的策略的建议 .
结构是一个树，其中每个元素都是一个字符串，每个分支都是一个句点，一个路径是从根开始的几个字符串和句点的串联 . 根的根和边是一种特殊情况，它们后面没有字符串 .
所以给了树， `{root} / \ A X / \ / B C Y`
有效路径是字符串“A”，“A.B”，“A.C”，“X”和“X.Y” .
我们拥有的是一组字符串，我们需要在此树中搜索并找到终止每个字符串的元素 . 并非集合中的所有字符串都显示在树中 . 当我们找到所有字符串时，我们停止搜索我们需要多次运行此搜索，但树木每次都可能不同 . 每次运行时，要搜索的字符串集是相同的 .
目前我们正在使用深度优先搜索，但如果所有字符串都位于根目录下的最后一个分支之下，则效率不高 . 我觉得应该有更好的方法来做到这一点 .
进行重复搜索的算法是什么？是否有可能在这里利用多线程？
1 回答
这是一个有趣的问题;通常可以想象一个树正在搜索一组可变的字符串 . 这种情况是相反的：字符串集是固定的，树是高度可变的 .
我认为你能做的最好的事情是 Build 一个代表字符串集的trie . 这样，您只需针对任何给定的前缀搜索一次树 . （因此，对于您提到的示例字符串，您只需要找到一次"A"前缀和"X"前缀一次 . ）有很多用于从一组字符串构建它们的trie数据结构和算法，但是从那以后's a one-time operation for this problem, I wouldn' t过分担心这种预处理的成本 .