树搜索算法
Tree searching algorithm
我正在寻找有关搜索树状数据结构的策略的建议。
结构是一棵树，其中每个元素都是一个字符串，每个分支都是一个句点，路径是从根开始的几个字符串和句点的串联。根和根的边是一种特殊情况，它们后面没有字符串。
所以给定这棵树，
</p>
<pre><code> {root}
/ \
A X
/ \ /
B C Y
有效路径是字符串 "A"、"A.B"、"A.C"、"X" 和 "X.Y".
我们有一组字符串，我们需要在这棵树中搜索并找到终止每个字符串的元素。并非集合中的所有字符串都出现在树中。当我们找到所有字符串时，我们停止搜索。我们需要多次 运行 此搜索，但每次的树可能不同。不过，要搜索的字符串集每个 运行 都是相同的。
目前我们正在使用深度优先搜索，但如果所有字符串都在根下的最后一个分支下，这不是很有效。我觉得应该有更好的方法来做到这一点。
执行此重复搜索的好的算法是什么？在这里也可以利用多线程吗？
这是一个有趣的问题；通常人们会想象在一棵树上搜索一组可变的字符串。这里的情况是相反的：字符串的集合是固定的，树是高度可变的。
我认为您最多只能构建一个 trie 来表示字符串集。这样，您只需为任何给定的前缀搜索一次树。 （因此，对于您提到的示例字符串，您只需要找到一次 "A" 前缀和一次 "X" 前缀。）有很多 trie 数据结构和算法可以从集合中构建它们字符串，但由于这是针对此问题的一次性操作，因此我不会太担心这种预处理的成本。
我正在寻找有关搜索树状数据结构的策略的建议。
结构是一棵树，其中每个元素都是一个字符串，每个分支都是一个句点，路径是从根开始的几个字符串和句点的串联。根和根的边是一种特殊情况，它们后面没有字符串。
所以给定这棵树，
</p>
<pre><code> {root}
/ \
A X
/ \ /
B C Y
有效路径是字符串 "A"、"A.B"、"A.C"、"X" 和 "X.Y".
我们有一组字符串，我们需要在这棵树中搜索并找到终止每个字符串的元素。并非集合中的所有字符串都出现在树中。当我们找到所有字符串时，我们停止搜索。我们需要多次 运行 此搜索，但每次的树可能不同。不过，要搜索的字符串集每个 运行 都是相同的。
目前我们正在使用深度优先搜索，但如果所有字符串都在根下的最后一个分支下，这不是很有效。我觉得应该有更好的方法来做到这一点。
执行此重复搜索的好的算法是什么？在这里也可以利用多线程吗？
这是一个有趣的问题；通常人们会想象在一棵树上搜索一组可变的字符串。这里的情况是相反的：字符串的集合是固定的，树是高度可变的。
我认为您最多只能构建一个 trie 来表示字符串集。这样，您只需为任何给定的前缀搜索一次树。 （因此，对于您提到的示例字符串，您只需要找到一次 "A" 前缀和一次 "X" 前缀。）有很多 trie 数据结构和算法可以从集合中构建它们字符串，但由于这是针对此问题的一次性操作，因此我不会太担心这种预处理的成本。