Trie树

今天做leetcode遇到trie树构建，学习了一下。

　　Trie树，前缀树，又称字典树，核心思想是把搜索过的字符串存储起来，这样如果以后搜索得字符串的前缀存在树中，那么这部分的搜索时间就可以节省了，极大提高了信息搜索的时间效率，是空间换时间的一个典型应用。

　　Trie树有这样几个特点：

1.根节点不包含字符，除根节点外，每个节点都只包含一个字符。

2.从根节点到某一个节点经过的路径连起来是一个加入的字符串。

3.每个节点的所有子节点包含的字符都不相同。

图例如下：

　　如图所示，从根节点遍历到某一个节点代表一个单词，如果节点标记为红色，说明要搜索的字符串存在。有共同前缀的单词共享前缀路径，叶子节点就是单词本身。

　　插入和查询操作是可以同步的，比如对于上图，要查询abe是否存在，步骤如下：

1、考察a是否存在，发现存在，则遍历到a，同理，b是a的子节点，沿这条路继续走；

2、考察ab的子节点有没有e，发现不存在，则创建ab的子节点abe，并把边ab->abe标记为e。

前缀树的应用也有很多，比如搜索引擎、拼写检查、IP路由（最长前缀匹配）、九宫格输入法等等。

实现代码：（leetcode#208）

class TrieNode{
    friend class Trie;
public:
    TrieNode(){
        memset(next, 0, sizeof(next));
        is_word = false;
    }
   
private: 
    TrieNode* next[26];
    bool is_word;
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
    
    ~Trie(){
        delete root;
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* p = root;
        int size = word.size();
        for(int i = 0; i < size; i++){
            if(p->next[word[i] - 'a'] == NULL){
                p->next[word[i] - 'a'] = new TrieNode;
                p = p->next[word[i] - 'a'];
            }
            else
                p = p->next[word[i] - 'a'];
        }
        p->is_word = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        return find(word) != NULL && find(word)->is_word;
        
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        return find(prefix) != NULL;
    }
    
    TrieNode* find(string word){
        TrieNode* p = root;
        int size = word.size();
        for(int i = 0; i < size; i++)
        {
            if(p->next[word[i] - 'a'] == NULL) return NULL;
            else p = p->next[word[i] - 'a'];
        }
        return p;
    }
    
private:
    TrieNode* root;
    
};

Trie树

推荐阅读