前缀（字典）树

前缀树(trie)就是常常听到的字典树，也成为单词查找树。常用于统计，排序和保存大量的字符串，所以常常被搜索引擎系统用于文本词频统计。比如：搜索时的自动补全，编辑器的拼写检查，IP路由（最长前缀匹配）。

特点：利用公共前缀来减少查询时间

构建前缀树：

trie树

结点数据结构：

class TrieNode {
public:
    int end;
    int path;
    TrieNode* map[26];
    TrieNode() : end(0), path(0) { memset(map, 0, sizeof(map)); }
    ~TrieNode() {}
};

插入：

// 将单词插入Trie，可重复插入
void insertWord(string word) {
    if (word.empty())
        return;
    TireNode *temp = root;
    for (int i = 0; i < word.size(); i++) {
        int index = word[i] - 'a';
        if (temp->map[index] == nullptr) {
            temp->map[index] = new TireNode();
        }
        temp = temp->map[index];
        temp->path++;
    }
    temp->end++;
}

删除：

void deleteWord(string word) {
    if (!searchW(word))
        return;
    TireNode *temp = root;
    for (int i = 0; i < word.size(); i++) {
        int index = word[i] - 'a';
        if (--temp->map[index]->path == 0) {
            delete(temp->map[index]);
            temp->map[index] = nullptr;
            return;
        }
        temp = temp->map[index];
        
    }
    if (--temp->end == 0)
        delete(temp);
}

查询：

bool searchW(string word) {
    if (word.empty())
        return false;
    TireNode *temp = root;
    for (int i = 0; i < word.size(); i++) {
        int index = word[i] - 'a';
        if (temp->map[index] == 0)
            return false;
        temp = temp->map[index];
    }
    return true;
}

查询前缀数量：

int prefixNumber(string pre) {
    if (pre.empty())
        return 0;
    TrieNode *temp = root;
    for (int i = 0; i < pre.size(); i++) {
        int index = pre[i] - 'a';
        if (temp->map[index] == 0)
            return 0;
        temp = temp->map[index];
    }
    return temp->path;
}

Talk is cheap. Show me the code!

源代码：

/* 字典树（前缀树）的实现  
 * 【题目】字典树又称为前缀树或Trie树，是处理字符串常见的数据结构。 
 * 假设组成所有单词的字符仅是“a”~“z”，请实现字典树结构， 并包含以下四个主要功能。 
 * void insert(String word)：添加word，可重复添加。
 * void delete(String word)：删除word，如果word添加过多次，仅删除一个。
 * bool search(String word)：查询word是否在字典树中。
 * int prefixNumber(String pre)：返回以字符串pre为 前缀的单词数量
*/
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class TrieNode;

class TrieNode {
public:
    int end;
    int path;
    TrieNode* map[26];
    TrieNode() : end(0), path(0) { memset(map, 0, sizeof(map)); }
    ~TrieNode() {}
};

class Trie {
private:
    TrieNode* root;
public:
    Trie() : root(new TrieNode()) {}
    void insertWord(string word) {
        if (word.empty())
            return;
        TrieNode *temp = root;
        for (int i = 0; i < word.size(); i++) {
            int index = word[i] - 'a';
            if (temp->map[index] == nullptr) {
                temp->map[index] = new TrieNode();
             }
            temp = temp->map[index];
            temp->path++;
        }
        temp->end++;
    }

    void deleteWord(string word) {
        if (!searchWord(word))
            return;
        TrieNode *temp = root;
        for (int i = 0; i < word.size(); i++) {
            int index = word[i] - 'a';
            if (--temp->map[index]->path == 0) {
                delete(temp->map[index]);
                temp->map[index] = nullptr;
                return;
            }
            temp = temp->map[index];
            
        }
        if (--temp->end == 0)
            delete(temp);
    }

    bool searchWord(string word) {
        if (word.empty())
            return false;
        TrieNode *temp = root;
        for (int i = 0; i < word.size(); i++) {
            int index = word[i] - 'a';
            if (temp->map[index] == 0)
                return false;
            temp = temp->map[index];
        }
        return true;
    }

    int prefixNumber(string pre) {
        if (pre.empty())
            return 0;
        TrieNode *temp = root;
        for (int i = 0; i < pre.size(); i++) {
            int index = pre[i] - 'a';
            if (temp->map[index] == 0)
                return 0;
            temp = temp->map[index];
        }
        return temp->path;
    }
};

int main() {
    Trie *trie = new Trie();
    cout << trie->searchWord("zoo") << endl;
    trie->insertWord("zoo");
    cout << trie->searchWord("zoo") << endl;
    trie->deleteWord("zoo");
    cout << trie->searchWord("zoo") << endl;
    trie->insertWord("zoo");
    trie->insertWord("zoo");
    trie->deleteWord("zoo");
    trie->deleteWord("zoo");
    cout << trie->prefixNumber("zoo") << endl;
    trie->insertWord("zooa");
    trie->insertWord("zoov");
    trie->insertWord("zoos");
    trie->insertWord("zooa");
    trie->insertWord("zooc");
    trie->insertWord("zood");
    trie->insertWord("zooe");
    trie->insertWord("zoof");
    cout << trie->prefixNumber("zoo") << endl;
    return 0;
}

学会了吗？学会了可以尝试Leetcode：208

Leetcode：208. 实现 Trie (前缀树)

class Trie {
private:
    int path;
    int end;
    vector<Trie*> nexts;
public:
    /** Initialize your data structure here. */
    Trie() : path(0), end(0) {
        nexts = vector<Trie*>(26, nullptr);
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie *t = this;
        for (int i = 0; i < word.size(); i++) {
            int index = word[i] - 'a';
            if (t->nexts[index] == nullptr)
                t->nexts[index] = new Trie();
            t = t->nexts[index];
            t->path++;
        }
        t->end++;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie *t = this;
        for (int i = 0; i < word.size(); i++) {
            int index = word[i] - 'a';
            if (t->nexts[index] == nullptr)
                return false;
            t = t->nexts[index];
        }
        return t->end != 0;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie *t = this;
        for (int i = 0; i < prefix.size(); i++) {
            int index = prefix[i] - 'a';
            if (t->nexts[index] == nullptr)
                return false;
            t = t->nexts[index];
        }
        return true;
    }
};