前缀树/字典树/trie树

定义

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

前缀树的性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同

常用操作：

• 类定义

class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    ...
};

• 插入单词

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

• 时间复杂度 O(m)，其中 m 为键长。

• 空间复杂度：O(m)。最坏的情况下，新插入的键和 Trie 树中已有的键没有公共前缀。此时需要添加 m 个结点，使用 O(m) 空间。

• 查找单词

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

• 时间复杂度 : O(m)。算法的每一步均搜索下一个键字符。最坏的情况下需要 mm 次操作。

• 空间复杂度 : O(1)。

• 前缀匹配

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

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

• 时间复杂度 : O(m)。
• 空间复杂度 : O(1)。