看圖輕鬆理解資料結構與算法系列(Trie樹)
推出一個新系列，《看圖輕鬆理解資料結構和演算法》，主要使用圖片來描述常見的資料結構和演算法，輕鬆閱讀並理解掌握。本系列包括各種堆、各種佇列、各種列表、各種樹、各種圖、各種排序等等幾十篇的樣子。
Trie樹
Trie樹，是一種搜尋樹，也稱字典樹或單詞查詢樹，此外也稱字首樹，因為某節點的後代存在共同的字首。它的key都為字串，能做到高效查詢和插入，時間複雜度為O(k)，k為字串長度，缺點是如果大量字串沒有共同字首時很耗記憶體。它的核心思想就是減少沒必要的字元比較，使查詢高效率，即用空間換時間，再利用共同字首來提高查詢效率。
Trie樹特點
- 根節點不包含字元，其他節點每個節點只包含一個字元。
- 從根節點到某一節點經過路徑的字元連起來即為該節點對應的字串。
- 每個節點的所有子節點字元都不相同。
插入操作
對he、him、his、she、her、hers六個字串進行插入，開始插入he字串，插入第一個字元是h，此時樹為空，所以先建立空的根節點，
接著從根節點開始，不存在h子節點，於是建立子節點h，
在h節點的基礎上繼續插入第二個字元e，
h節點不存在e子節點，建立子節點e，並將該節點標記為單詞標誌，完成he字串插入。
接著插入him字串，從根節點開始，發現h子節點已有，
移到h子節點，
繼續處理第二個字元i，h節點不存在i子節點，於是建立i子節點，
處理第三個字元m，i節點不存在子節點m，於是建立m子節點，並將該節點標記為單詞標誌，完成him插入。
接著插入his字串，從根節點開始，發現h子節點已有，
移到h子節點，
繼續處理第二個字元i，h節點已存在i子節點，於是移到i節點，
處理第三個字元s，i節點不存在子節點s，於是建立s子節點，並將該節點標記為單詞標誌，完成his插入。
繼續插入she字串，從根節點開始，首先處理第一個字元s，發現s子節點不存在，於是建立s節點，
接著處理第二個字元h，s節點不存在h子節點，建立h節點，
繼續處理第三個字元e，h節點不存在e子節點，建立e節點，並將該節點標記為單詞標誌，至此完成she字串插入。
類似地，將her、hers字串插入到樹中，最終為：
查詢操作
查詢hi字串，從根節點開始，
根節點存在h子節點，移動到h節點，
繼續找i子節點，存在，但i並沒有單詞標誌，所以hi字串不存在。
查詢his字串，從根節點開始，
根節點存在h子節點，移動到h節點，
h節點存在i子節點，移動到i節點，
繼續找s子節點，存在，而且s節點為單詞標誌，找到his字串。
而如果查詢hist字串，則最後的t找不到，所以不存在該字串。
刪除操作
情況一
刪除she字串，從根節點開始查詢第一個字元s，
找到s子節點，下移到s節點，繼續查詢字元h，
找到h子節點，下移到h節點，繼續查詢字元e，
找到e節點，已經找到she字串，將e節點的單詞標誌去掉，
此時發現e節點為葉子節點，將其刪除，
刪除後發現h節點為葉子節點，且其不是單詞標誌，將其刪除，
刪除後發現s節點為葉子節點，且其不是單詞標誌，將其刪除，完成she字串刪除操作。
情況二
刪除her字串，從根節點開始查詢第一個字元h，
找到h子節點，下移到h節點，繼續查詢字元e，
找到e子節點，下移到e節點，繼續查詢字元r，
找到r子節點，此時完成整個字串查詢，因為不是葉子節點，只需將其單詞標誌去掉即可。
