Trie（前缀树）C++的基本实现

0x01.说明

• 前缀树是是一种树的数据结构，是一种非典型的多叉树结构，每个结点的分支数量可能有多个。
• 前缀树主要用于检索字符串数据集中的键。
• 前缀树也叫做字典树，前缀树，单词查找树等。
• Trie [traɪ] 读音和 try 相同

0x02.前缀树的应用

这个高效的数据结构用途非常广泛：

• 搜索引擎自动补全。
• 拼写检查。
• 打字预测。

0x03.前缀树的优势

平衡树和哈希表也可以使我们能够在字符串数据集中搜索单词，但是功能局限，且随着哈希表的增大，出现的冲突会增加，效率会退化。

• 前缀树找到具有同一前缀的全部键值。
• 前缀树可以按词典序枚举字符串的数据集。

0x04.结构

前缀树主要有两个字段：

• 指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。（一般为26个）
• 布尔字段，指定节点是对应键的结尾还是只是键前缀。

struct TrieNode {
    bool isEnd; //该结点是否是一个串的结束
    TrieNode* next[26]; //字母映射表
};

0x05.基本操作

插入

向前缀树中插入一个单词。

从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，不断开辟新的结点，直到插入完 word 的最后一个字符，再加上isEnd的值。

  void insert(string word) {
        Trie*node=this;
        for(char c:word){
            if(node->next[c-'a']==NULL){
                node->next[c-'a']=new Trie();               
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }
    

查询

查找 Trie 中是否存在单词 word。

根结点的子结点开始，一直向下匹配，如果出现空结点就返回false，如果匹配到了最后一个字符，只需判断node->isEnd。

bool search(string word) {
        Trie*node=this;
        for(char c:word){
            node=node->next[c-'a'];
            if(node==NULL) return false;
        }
        return node->isEnd;
    }
    

前缀匹配

判断 Trie 中是或有以 prefix 为前缀的单词。

bool startsWith(string prefix) {
        Trie*node=this;
        for(char c:prefix){
            node=node->next[c-'a'];
            if(node==NULL) return false;
        }
        return true;
    }
    

0x06.完整的类

class Trie {
private:
    bool isEnd;
    Trie*next[26];
public:
    /** Initialize your data structure here. */
    Trie() {
        isEnd=false;
        memset(next, 0, sizeof(next));
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie*node=this;
        for(char c:word){
            if(node->next[c-'a']==NULL){
                node->next[c-'a']=new Trie();               
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie*node=this;
        for(char c:word){
            node=node->next[c-'a'];
            if(node==NULL) return false;
        }
        return node->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie*node=this;
        for(char c:prefix){
            node=node->next[c-'a'];
            if(node==NULL) return false;
        }
        return true;
    }
};
/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

ATFWUS --Writing By 2020–03–21