【算法】前缀树、单词查找树、字典树（C++）

前缀树，又称为单词查找树、字典树，英文单词是trie，作用是快速查找对应的字符串或字符串的前缀。具备以下两个性能：
1.查找命中所需的时间与被查找的键的长度成正比；
2.查找未命中只需检查若干个字符。

这样的性能对于便捷、快速地访问海量数据库是非常惊人的。

和各种查找树一样，单词查找树也是由链表的结点所组成的多叉树。在正常的链表中，每一个结点都含有next指针、prev指针，分别指向下一个结点和前一个结点。在前缀树中，每一个结点都具有26个指针，分别指向26个字母，这其中有一些是有意义的结点，有一些是空结点。

如上图所示，是一个存储了by、sea、sells、shells、the单词的前缀树，单词的末尾用黄色标记，其中省略了大量无意义的空节点。

class Trie {
private:
    vector children;		//指向26个子结点
    bool isEnd;					//是否是字符串结尾

public：
	Trie() : children(26), isEnd(false) {}

含有两个成员变量，一个是含有子结点指针的数组，在构造函数中元素数量初始化为26，代表26个字母，children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z；一个是isEnd标志位，代表该结点是否是单词的最后一个字符。

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

我们从前缀树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

• 子节点存在。沿着指针移动到子节点，继续处理下一个字符。
• 子节点不存在。创建一个新的子节点，记录在children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
  重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。

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

在前缀树中查找给定字符串是一个简单的过程，它是以被查找的键中的字符为导向的。前缀树的每一个子结点都代表着下一个可能出现的所有字符的链接。我们从前缀树的根节点开始查找单词的第一个字符，有两种情况：

• 子结点存在。沿着指针移动到子结点，继续搜索下一个字符。
• 子结点不存在。说明字典树不包含该单词，返回false；

若搜索到了该单词的最后一个字符，要判断该字符是否为字符串的末尾。若isEnd为真，说明前缀树存在该字符串。

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

该函数和单词查找函数相差无几，只是在返回时并不需要判断是否结尾，只要能找到最后一个字符，代表一定存在该前缀组成的单词。

时间复杂度：插入或查询的时间复杂度为O(∣S∣)，其中 |S|∣S∣ 是每次插入或查询的字符串的长度。
空间复杂度：O(∣T∣⋅Σ)，其中 ∣T∣ 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。

《算法 第4版》
《实现 Trie (前缀树)》力扣官方题解