树搜索算法

Question

我正在寻找有关搜索树状数据结构策略的建议。

该结构是一棵树，其中每个元素是一个字符串，每个分支是一个句点，并且一个路径是几个字符串和从根开始的句点的连接。根的根和边是一个特殊的情况，在它们后面没有字符串。

所以给出的树，

 {root} 
    /  \ 
    A   X 
/ \ /
B  C Y 

有效路径字符串 “A”， “A·B”， “A.C”， “X” 和 “X.Y”。

我们拥有的是一组字符串，我们需要在此树中搜索并找到终止每个字符串的元素。并非所有的字符串都出现在树中。当我们找到所有字符串时我们停止搜索。我们需要多次执行此搜索，但每次树木可能会有所不同。尽管如此，要搜索的字符串集合是相同的。

目前我们使用的是深度优先搜索，但如果所有字符串均属于根下的最后一个分支，则效率不高。我觉得应该有更好的方式来做到这一点。

什么是一个很好的算法来做这个重复搜索？在这里也可以利用多线程吗？

Answer 1

这是一个有趣的问题;通常人们会想象一个单一的树正在搜索一组可变字符串。这里的情况是相反的：字符串集是固定的，并且树高度可变。

我认为你可以做的最好的事情是建立一个代表字符串集合的trie。这样，您只需为任何给定的前缀搜索一次树。 （因此，对于您提到的示例字符串，您只需要找到一次“A”前缀和一次“X”前缀）。有许多用于从一组字符串构建它们的trie数据结构和算法，但因为这是这个问题的一次性操作，所以我不会太担心这个预处理的成本。