字典树

定义

---

字典树

字典树（Trie）是一种高效的树形数据结构，主要用于统计、排序和保存大量的字符串。
核心思想是利用字符串的公共前缀来减少查询时间。

字典树

+−⟲

Link to original

插入

一开始让$node$为根节点。
对于字符串$s$的每个字符$s[i]$，检查$node$的$next[s[i]-{}^{\prime }{a}^{\prime }]$是否为$null$，若是则插入新节点表示$s[i]$。
在插入结束时将最后一个节点的$is\_end$标记为$true$。

实现

---

struct Trie  
{  
    Trie* next[26];  
    bool is_end;  
  
    Trie()  
    {  
       is_end = false;  
       for (int i = 0; i < 26; ++i)  
          next[i] = nullptr;  
    }  
  
    void insert(string& s)  
    {  
       Trie* node = this;  
       for (int i = 0; i < s.length(); ++i)  
       {  
          char c = s[i];  
          if (node->next[c - 'a'] == nullptr)  
             node->next[c - 'a'] = new Trie();  
          node = node->next[c - 'a'];  
       }  
       node->is_end = true;  
    }  
  
    bool search(string& s)  
    {  
       Trie* node = this;  
       for (int i = 0; i < s.length(); ++i)  
       {  
          char c = s[i];  
          if (node->next[c - 'a'] == nullptr)  
             return false;  
          node = node->next[c - 'a'];  
       }  
       return node->is_end;  // 如果不是结尾说明只是存在s这个前缀而不是存在s这个字符串
    }  
    
    bool is_prefix_exist(string& s)
    {  
       Trie* node = this;  
       for (int i = 0; i < s.length(); ++i)  
       {  
          char c = s[i];  
          if (node->next[c - 'a'] == nullptr)  
             return false;  
          node = node->next[c - 'a'];  
       }  
       return true;  // 某个字符串包括s这个前缀或者s本身就是字符串都表示包含s这个前缀
    }
};