我很困惑如何Trie實施節省空間&以最緊湊的形式存儲數據！Trie節省空間，但是如何？
如果你看看下面的樹。在任何節點上存儲字符時，還需要存儲對該字符串的每個字符的引用，以便存儲其引用。 好吧，我們在普通字符到達時保存了一些空間，但是在存儲對該字符節點的引用時我們失去了更多空間。
那麼維護這棵樹本身沒有太多的結構性開銷嗎？相反，如果使用TreeMap來替代這個，可以說實現一個字典，這可以節省更多的空間，因爲字符串將保存在一塊，因此在存儲引用時不會浪費空間，不是嗎？當你很多的話要由樹表示
你可能會推斷出它節省的空間是在一個理想的機器上，每個字節都被有效分配。然而，真正的機器分配對齊的內存塊（在Java上是8個字節，在某些C++上是16個字節），因此它可能不會節省任何空間。
Java字符串和集合增加了相對較高的數量，因此百分比差異可能非常小。
除非您的結構非常大，否則您的超時值會加重使用最簡單，最標準，最容易維護收集的內存成本。例如你的時間可以很容易地勝過你試圖保存的內存值的1000倍或更多。
例如假設你有10000個名字，你可以使用一個trie來保存16個字節。 （假設這可以在不花費更多時間的情況下證明），這相當於16 KB，在今天的價格是0.1美分。如果您的時間花費您的公司每小時30美元，則編寫一行測試代碼的成本可能爲1美元。
如果您已經考慮更長時間以節省16 KB的時間，那麼它不太可能在PC上值得。 （移動設備是一個不同的故事，但同樣的論點適用恕我直言）
編輯：您啓發了我補充更新http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of-main-memory.html
特里將更快，節省空間。對於15K條目，它可以爲您節省0.2美分的內存和CPU。如果你看到在路的另一邊可能會有0.2美分，你會跨過去撿起來嗎？如果需要大約一秒的時間，我只會這樣做。鑑於TreeMap是一個內置的，經過良好測試的文檔，並且被任何人支持你的代碼所理解，它將爲你節省更多的時間，而不僅僅是在內存中花費的時間（除非你使用許多設備將限制內存） –
如果您正在編寫部署到數千或數百萬用戶的庫，那麼0.2美分就有多個，而當部署到按使用量收費的服務器時，0.2美分有另一個倍數。 「性能無關緊要」不是解決方案，而是意識形態。 – Ajax
如果您在總計2000美元的100萬臺機器中節省0.2美分。這值得花費幾天甚至一週的時間。如果只有幾十個小時甚至一天的時間，它只有100K臺機器。如果只有10K臺機器，你只需要幾分鐘的時間。如果只有一千臺或更少的機器，你可能會浪費你的時間來擔心它。規模確實很重要，大多數項目都沒有部署到足夠的機器上，擔心少量資源是一個好主意。 –
空間被保存。因爲許多單詞在樹中共享相同的路徑;你有更多的話，你會節省更多的空間。
但是如果您想節省空間，那麼會有更好的數據結構。 Trie並沒有像directed acyclic word graph (DAWG)那樣節省空間，因爲它在整個結構中共享公共節點，而trie不共享節點。 wiki entry解釋了這個細節，所以看看它。
這裏是Trie樹和DAWG之間的差（以圖形方式）：
字符串 「抽頭」， 「輕敲」， 「頂」 和 「強」 存儲在字典樹（左）和DAWG（右），EOW代表詞末。
左邊的樹是Trie，右邊的樹是DAWG。比較它們並觀察DAWG如何有效節省空間。 Trie具有代表相同字母/子字的重複節點，而DAWG每個字母/子字恰好有一個節點。
要使用字典樹時節省空間，可以使用一個compressed trie（也稱爲帕特里夏字典樹或基數樹）中，其中一個節點可以代表多個字符：
在計算機科學中，基數樹（還有patricia trie或radix trie） 是一個空間優化的trie數據結構，其中只有一個 子節點的每個節點都與其子節點合併。結果是每個內部節點 至少有兩個孩子。與常規嘗試不同的是，邊緣可以是 ，標有字符序列以及單個字符。 這使得它們對於小集合（尤其是如果 字符串很長）以及共享長前綴的字符串集更有效。基數樹的
實施例：
。注意，線索通常用作一個有效的數據結構，用於前綴匹配的一組串。一個trie還可以用作關聯數組（如哈希表），其中的關鍵字是一個字符串。
我看了一下Patricia Trie的實現，但它是否是Guava和Apache Commons等流行庫的一部分？我無法弄清楚它在Guava/apache commons集合中的實現 –
@Marcos在Guava中沒有任何實現，儘管有一個長期運行的問題需要添加一個，所以最終可能會發生。 – ColinD
冷卻。感謝您的澄清！ –
這不是關於內存中的廉價空間，而是關於文件或通信鏈接中的寶貴空間。使用構建該特里結構的算法，我們可以發送三位左右的「十」。與24比特相比，'十'會佔用未壓縮的空間，這是寶貴的磁盤空間或傳輸帶寬的巨大節省。
這真的是一個很大的優勢！ –
所以，僅僅爲了在內存結構中不需要傳輸數據，而是爲了獲得大約10,000個名稱的電話名稱目錄的搜索建議的高性能和空間有效的解決方案，是否會使用Trie在TreeMap上推薦？ –
番石榴確實可以存儲在每個級別的關鍵，但實現的一點是，密鑰並不需要存儲，因爲節點的路徑完全定義了該節點的密鑰。所有實際需要存儲在每個節點的是一個布爾值，指示這是否是葉節點。
像任何其他結構一樣，嘗試擅長存儲某些類型的數據。具體而言，嘗試最好是存儲共享公共根的字符串。例如，考慮存儲全路徑目錄列表。
如果一個節點需要16個字節，但在16個以上的字符串（8個Java）中重用，它節省了空間。那麼這只是一個問題，你是否節省了更多的空間而不是浪費。假設您的示例中的藍色數字是重複計數，與簡單的字符串數組相比，節省量確實會比浪費的空間大。但是在這種情況下，用重複計數存儲完整的字符串會更好。 – han