Trie（字典樹）詳解與C++實作

文章目錄

• • 參考資料
  • Trie Introduction（介紹字典樹）
  • C++實作
  • Trie 應用

參考資料

1. 甜姨的力扣題解：https://zhuanlan.zhihu.com/p/120150816
2. 力扣官方題解：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/
3. https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/

1.2.資料都是基于Java來對Trie進行實作，3.是c++的實作，原理都介紹的非常棒！

Trie Introduction（介紹字典樹）

Trie也叫字典樹、字首樹、單詞查找樹等等，它常用來存儲單詞（和語種無關），相比于HashMap等操作，Trie能在存儲多個具有相同字首的鍵時，使用較少的空間。并且Tire樹隻需要O(M)的時間複雜度，其中M為鍵長。

下圖示範了一個儲存8個單詞的字典樹結構，8個單詞分别是：“A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”。（藍色節點表示單詞的結尾字元）

【示例來自參考資料1】

說明

root節點為Null；

把從root節點出發到藍色節點的路徑上所表示的字元連接配接起來，就構成一個單詞；

從root節點出發，都是單詞清單裡某個單詞/某些單詞的字首；

如果某個字元串沒有出現在這棵樹的路徑上，那說明其不是所給出單詞清單的字首。

然後相比一般的多叉樹，Trie在節點的資料結構設計上也有很多不同。

class Trie{
private:
    bool flag;
    Trie* next[R];
};
           

其中val表示的是該節點是否為尾節點（是不是對應鍵的結尾），

next[R]

表示的是指向R個子節點的連結。比如我們現在要表示英語單詞的話，R就為26。

說明

因為

flag

隻用來表示該節點是否為一個單詞的結尾，然後

next[R]

可以看做是指向26個字母的映射表，儲存了對于目前節點而言，下一個可能出現的字元連結。是以，上面的圖并不是字典樹真正的存儲形式，我們看下圖：

這是一個包含三個單詞‘sea’，‘she’，‘sells’的字典樹完整形式。

【示例來自參考資料3】

可以看到，Trie中一般含有大量的空連結。

C++實作

class Trie{
private:
    // 定義節點
    bool flag = false;
    Trie* next[26] = {nullptr};
public：
    Trie(){}    // 構造函數

    void insert(string word){   // 插入
        Trie* node = this;
        for(int i=0; i<word.length(); i++){
            char c = word[i];
            if(node->next[c-'a']==nullptr){
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->flag = true;  // 單詞串的尾節點為true
    }

    bool search(string word){   // 查找單詞是否存在Trie中
        Trie* node = this;
        for(int i=0; i<word.length(); i++){
            char c = word[i];
            if(node->next[c-'a']==nullptr)  return false;
            node = node->next[c-'a'];
        }
        return node->flag;  // 如果該節點是串尾節點，則為true
    }

    bool starsWith(string prefix){  //查找字首
        Trie * node = this;
        for(int i=0; i<prefix.length(); i++){
            char c = prefix[i];
            if(node->next[c-'a']==nullptr)  return false;
            node = node->next[c-'a'];
        }
        return true;
    }
};
           

說明：

最常用的有三個操作，插入單詞、搜尋單詞是否在字典樹中、搜尋字首是否在字典樹中。

插入單詞：node指向根節點，從單詞的第一個字元開始判斷，該字元是否在節點指向的字母映射表中出現（不為

nullptr

空指針），如果沒有出現過就建立對應的記憶體空間，然後node指向對應字母的連結。重複操作，直到該單詞全部插入完，再另最後的尾結點

node->flag=true()

（表示一個單詞的結尾）。有點類似連結清單的插入。

查找單詞是否在字典樹中：同樣，node先指向根節點，然後從單詞的第一個字元開始判斷，該字元是否在node指向的字母映射表中出現，如果沒有出現直接

return false

，否則node指向對應字母的連結，重複操作，直至單詞全部查詢完。最後再判斷

node->flag == true?

，如果不為true，則表示并不是單詞的結尾（該單詞沒有出現在字典樹中，隻是字首包含了該單詞）。

查找字首是否出現在字典樹中 ：跟上面查找單詞是一樣的，隻是最後不用再判斷flag。

對應的LeetCode練習：LeetCode208. 實作Trie（字首樹）

Trie 應用

1. 自動補全

   

2. 拼寫檢查

   

3. IP路由