树结构算法总结(1) 二叉树的遍历
 树结构算法总结(2) 线段树Segment Tree

树结构算法总结(3) 字典树Trie Tree

字典树的数据结构

定义

字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

字典树是一种存储字典（中文或英文都可以）的树结构，创建/添加/查询单词的时间复杂度都为O(h)，h为树高度。

字典树

应用

串的快速匹配：在建立的字典树里可以快速查找到想要的单词，以判定词在不在熟词表里。
串的排序：对Trie树进行前序遍历，就是串排序结果。
最长公共前缀：可以求出两个或多个字串的最大公共前缀。

数据结构

一般的字典树的节点单元包含：

count：存储该单词在词典中出现的次数
word：存储该节点的单词
isword：判定该节点是否是一个有效单词
next：存储该节点的所有孩子节点（如果只包含小写字母，则为26个）

我们直接通过lintcode上面的题目来实现简单的Trie树结构。

class TrieNode {
public:
    // Initialize your data structure here.
    bool isword;
    int count;
    // string word;
    vector<TrieNode*> next;
    TrieNode() {
        isword = false;
        next = vector<TrieNode*>(26, NULL);
        // count = 0;
    }
};

字典树的单词添加和查找

考虑字典树的结构特性，我们通过如下方式实现添加和查找。

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode* r = root;
        for(auto i:word){
            if(r->next[i-'a']==NULL)
                r->next[i-'a'] = new TrieNode();
            r = r->next[i-'a'];
            // r->count++;
        }
        // r->word = word;
        r->isword = true;
        // r->count++;
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode* r = root;
        if(r==NULL)
            return false;
        for(auto i:word){
            if(r->next[i-'a']==NULL)
                return false;
            r = r->next[i-'a'];
        }
        if(r==NULL)
            return false;
        return r->isword;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* r = root;
        if(r==NULL)
            return false;
        for(auto i:prefix){
            if(r->next[i-'a']==NULL)
                return false;
            r = r->next[i-'a'];
        }
        return true;
    }

private:
    TrieNode* root;
};

现在再增加一点新的东西，比如在查找过程中单词除了小写字母外，还包含’.’代表匹配任意一个字母，则实现方法如下（和上面的有些不太一样）。

class TrieNode{
public:
    int count;
    vector<TrieNode*> next;
    TrieNode(){
        count=0;
        next=vector<TrieNode*>(26, NULL);
    }
};

class WordDictionary {
public:
    WordDictionary(){
        root = new TrieNode();
    }
    // Adds a word into the data structure.
    void addWord(string word) {
        // Write your code here
        TrieNode* r = root;
        for(auto i:word){
            if(!r->next[i-'a'])
                r->next[i-'a'] = new TrieNode();
            r = r->next[i-'a'];
        }
        r->count++;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        // Write your code here
        return searchPoint(word, root, 0);
    }
    bool searchPoint(string& word, TrieNode* cur, int start){
        if(cur&&start==word.size())
            return cur->count>0;
        if(!cur)
            return false;
        char c = word[start];
        if(c=='.'){
            for(auto child:cur->next){
                if(child&&searchPoint(word, child, start+1))
                    return true;
            }
            return false;
        }
        else{
            if(cur->next[c-'a'])
                return searchPoint(word, cur->next[c-'a'], start+1);
            else
                return false;
        }
    }
private:
    TrieNode* root;
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

Previous

树结构算法总结(3) 字典树Trie Tree

字典树的数据结构

定义

应用

数据结构

字典树的单词添加和查找