首先，什麽是字典樹（Trie樹）？顧名思義，就是像字典壹樣按照壹定的排序順序標準和步驟訪問樹的節點。舉個簡單的例子，如果妳在英語詞典中查找單詞“he”，妳必須首先按照a-z的順序找到H的第壹個字母，然後按照相同的順序找到E。博主要介紹的字典樹是壹種類似於字典的結構。
上述查找單詞的過程是不斷查找與被搜索單詞具有相同前綴的字符串，直到找到被搜索單詞的最後壹個字母。因此，字典樹也被稱為前綴樹。
以hell、hi、new和nop為例構建字典樹，其構造如下。
根據上述內容，可以獲得字典樹的結構性質。
根據以上三點構建壹個字典樹。
字典樹的構造其實比較簡單，和壹般樹的構造沒有太大區別。接下來，將分析和解釋插入、刪除和查詢字典樹的操作。
當沒有字典樹時，我們需要先構建壹個字典樹。
以插入地獄為例:
然後插入單詞hit，過程如下，檢查=》如果存在，訪問/如果不存在，建立壹個新的節點並再次訪問=》直到要插入的單詞到達最後壹個字符。
字典樹的插入操作比較簡單，不需要考慮太多的排序問題。
如上所述，按照壹定的標準查詢目標字符串，每個節點存儲壹個字符，從根節點到子節點的路徑形成的字符串就是對應的字符串，因此在查詢目標字符串時，從根節點開始壹步步訪問對應字符所在的節點，這實際上就是匹配字符串前綴的過程。
如下所示，在字典樹中，查詢“地獄”，
【圖像上傳失敗...（圖像-f028c 4-1611057619223）】
如果在字典中查不到
刪除操作比插入和查詢稍微復雜壹點，但也非常簡單。刪除的前提是該單詞已經存在於詞典樹中。
刪除字典樹節點需要考慮目標字符串的最後壹個字符是否是樹中的葉節點。
因為壹個單詞可能是另壹個單詞的前綴部分，如果它不是葉節點，我們只需要清空該單詞的單詞標誌位，而無需刪除整個“分支”。
例如，您想刪除單詞“no”
例如，如果您要刪除單詞“hell”，它與第壹次刪除相同，只是節點刪除操作從最後壹個節點開始，並且“L”節點是葉節點。
比如妳想刪除“hi”，其實和前兩個是壹樣的。您可以訪問葉節點“I”，刪除葉節點，然後向上訪問“h”。由於“h”在刪除“I”後仍不是葉節點，因此您不會繼續刪除該節點。
例如，如果您想刪除“nop”，與前面的操作類似，您首先訪問葉節點“p”以刪除它，然後向上移動發現“o”是葉節點，但“o”有壹個單詞標簽，因此此處不會繼續刪除。
上面有幾個刪除操作，我們得到了刪除的標準:
了解了字典樹的這麽多操作，相信妳對字典樹的使用有了大致的了解。字典樹最大的功能是匹配= =字符串、前綴匹配（模糊搜索）、字符串搜索（字典）等等。
博主只輸入了四個關鍵詞“涓涓清泉”，他們的搜索列表返回了許多以涓涓清泉為首的選項。
顧名思義，它只是壹本簡單的字典，例子很少。
字典樹的構造利用空間換時間的思想和字符串的公共前綴減少了無效的字符串比較操作，從而提高了插入和查找字符串的效率。插入或查找字符串的時間復雜度為O（n），n是字符串的長度。
當然，字典樹也有它的缺點。當插入的單詞沒有很多公共前綴時，字典樹的構造變得非常復雜和低效。
字典樹不是很難，但它是壹種非常有用的數據結構。掌握了它之後，對解決壹些關於字符串匹配和公共前綴的問題很有幫助。
當然，我們也說過字典樹有它自己的缺點。因為空間是用時間換來的，如果用壹堆公共前綴很少的詞來構造詞典樹，空間需求會很大。