基數樹節點

Question

我一直在研究一個基數樹的實現（對於字符串/字符數組），但我有點困惑，想出如何存儲哪些樹節點是特定樹節點的子節點。

我已經看過Trie中使用的鏈表實現（有點類似於基數樹），可能還有一些基數樹（自從我上次研究這個主題後已經有一段時間了），但是看起來它會表現得非常好尤其是如果你有一組包含大量通用前綴的數據。

現在我想知道使用其他數據結構（例如二進制搜索樹）是更好的設計選擇嗎？我認爲當存在大量通用前綴的數據時，在簡單鏈接列表（O(log(n))與O(n)）之間可以看到顯着的速度提升，但在其他地方的性能可能會有一些實質性的妥協？

特別是我擔心的情況是，如果沒有大量的通用前綴或任何其他可能導致人們在二叉搜索樹上選擇鏈接列表的障礙。

或者，是否有更好的（即更快/使用更少的內存）方法來存儲子節點？

Answer 1

你想找一個卡丁車。一個卡丁車特里使用一個簡單哈希的BST數據結構。你可以在這裏找到描述：http://code.dogmap.org/kart。

Answer 2

您可以使用trie替代BST或列表。對於BST，你將不得不計算一個散列，這個散列可能和遍歷該trie一樣昂貴（我正在考慮一個帶有指向兒童的指針數組，在這裏你使用一個字符作爲索引）。你會以嘗試的方式結束。更好的解決方案可能是構建一個trie，然後壓縮不是分支的鏈接。