樹搜索算法

Question

我正在尋找有關搜索樹狀數據結構策略的建議。

該結構是一棵樹，其中每個元素是一個字符串，每個分支是一個句點，並且一個路徑是幾個字符串和從根開始的句點的連接。根的根和邊是一個特殊的情況，在它們後面沒有字符串。

所以給出的樹，

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

有效路徑字符串 「A」， 「A·B」， 「A.C」， 「X」 和 「X.Y」。

我們擁有的是一組字符串，我們需要在此樹中搜索並找到終止每個字符串的元素。並非所有的字符串都出現在樹中。當我們找到所有字符串時我們停止搜索。我們需要多次執行此搜索，但每次樹木可能會有所不同。儘管如此，要搜索的字符串集合是相同的。

目前我們使用的是深度優先搜索，但如果所有字符串均屬於根下的最後一個分支，則效率不高。我覺得應該有更好的方式來做到這一點。

什麼是一個很好的算法來做這個重複搜索？在這裏也可以利用多線程嗎？

Answer 1

這是一個有趣的問題;通常人們會想象一個單一的樹正在搜索一組可變字符串。這裏的情況是相反的：字符串集是固定的，並且樹高度可變。

我認爲你可以做的最好的事情是建立一個代表字符串集合的trie。這樣，您只需爲任何給定的前綴搜索一次樹。 （因此，對於您提到的示例字符串，您只需要找到一次「A」前綴和一次「X」前綴）。有許多用於從一組字符串構建它們的trie數據結構和算法，但因爲這是這個問題的一次性操作，所以我不會太擔心這個預處理的成本。