哪個節點的數據結構要用於一個trie

Question

我是第一次使用trie。我想知道哪個是用於trie的最佳數據結構，同時決定哪個是應該遍歷的下一個分支。我正在尋找一個數組，一個散列表和一個鏈表。

Answer 1

這些選項各有其優點和缺點。

如果您將子節點存儲在數組中，那麼只需索引數組，就可以非常高效地查找要訪問的子節點。但是，每個節點的空間使用率會很高：O（| Σ |），其中Σ是您的單詞可以由其組成的一組字母，即使這些孩子中的大多數都爲空。

如果將子節點存儲在鏈接列表中，則查找子節點所需的時間爲O（| Σ |），因爲您可能需要掃描鏈表的所有節點以查找你想要的孩子。另一方面，空間效率會非常好，因爲您只儲存您正在使用的孩子。您也可以考慮在這裏使用固定大小的陣列，它具有更好的空間使用率，但會導致非常昂貴的插入和刪除操作。

如果將子節點存儲在散列表中，則查找子節點的（預計）時間將爲O（1），並且內存使用量僅與您擁有的子節點數成比例（大致）。有趣的是，因爲事先知道你將要散列的值是什麼，所以你可以考慮使用dynamic perfect hash table來確保最壞情況的O（1）查找，代價是一些預計算。

另一種選擇是將子節點存儲在二叉搜索樹中。這產生了ternary search tree數據結構。此選擇位於鏈表和散列表選項之間 - 空間使用率較低，可以高效地執行前置查詢和後續查詢，但由於BST中的搜索成本，執行查找的成本略有增加。如果你有一個永遠不會發生插入的靜態線索，你可以考慮在每個點使用weight-balanced trees作爲BST;這爲搜索提供了極好的運行時間（O（n + log k），其中n是要搜索的字符串的長度，k是trie中的單詞總數）。

簡而言之，數組查找速度最快，但在最糟糕的情況下其空間使用率最差。一個靜態大小的數組具有最好的內存使用情況，但是昂貴的插入和刪除。哈希表具有快速查找和良好的內存使用情況（平均而言）。二叉搜索樹位於中間的某處。我會建議在這裏使用哈希表，但如果你對空間進行溢價並且不關心查找時間，那麼鏈表可能會更好。另外，如果你的字母表很小（比如你正在製作一個二進制的trie），那麼數組的開銷不會太壞，你可能想要使用它。

希望這會有所幫助！

Answer 2

如果你正在嘗試構建字符串的trie，我會建議使用數組，然後使用particia樹（空間優化trie）。 http://en.wikipedia.org/wiki/Radix_tree

這將允許您快速查找數組，並且不會浪費太多的空間，如果某些節點的分支因子很低。