Trie树

什么是Trie树？

转载于https://www.cxyxiaowu.com/7535.html

Trie [traɪ] 读音和 try 相同，它的另一些名字有：字典树，前缀树，单词查找树等。

开始之前我们先看看来 Trie 树的几个常见的应用场景：

  1. Google、Baidu 等搜索引擎的搜索提示

三分钟基础：什么是 trie 树？

  1. 代码自动补全

三分钟基础：什么是 trie 树？

  1. IP路由查询使用的最长前缀匹配算法

三分钟基础：什么是 trie 树？

介绍 Trie

Trie 是一颗非典型的多叉树模型，多叉好理解，即每个结点的分支数量可能为多个。

为什么说非典型呢？因为它和一般的多叉树不一样，尤其在结点的数据结构设计上，比如一般的多叉树的结点是这样的：

struct TreeNode {
    VALUETYPE value;    //结点值
    TreeNode* children[NUM];    //指向孩子结点
};

而 Trie 的结点是这样的(假设只包含’a’~’z’中的字符)：

struct TrieNode {bool isEnd; //该结点是否是一个串的结束
    TrieNode* next[26]; //字母映射表
};

要想学会 Trie 就得先明白它的结点设计。我们可以看到TrieNode结点中并没有直接保存字符值的数据成员，那它是怎么保存字符的呢？

这时字母映射表next 的妙用就体现了，TrieNode* next[26]中保存了对当前结点而言下一个可能出现的所有字符的链接，因此我们可以通过一个父结点来预知它所有子结点的值：

for (int i = 0; i < 26; i++) {
    char ch = 'a' + i;
    if (parentNode->next[i] == NULL) {
        说明父结点的后一个字母不可为 ch
    } else {
        说明父结点的后一个字母可以是 ch
    }
}

我们来看个例子吧。

想象以下，包含三个单词”sea”,”sells”,”she”的 Trie 会长啥样呢？

它的真实情况是这样的：

三分钟基础：什么是 trie 树？来自算法4

Trie 中一般都含有大量的空链接，因此在绘制一棵单词查找树时一般会忽略空链接，同时为了方便理解我们可以画成这样：

三分钟基础：什么是 trie 树？实际并非如此，但我们仍可这样理解

接下来我们一起来实现对 Trie 的一些常用操作方法。

定义类 Trie

class Trie {private:
    bool isEnd;
    Trie* next[26];
public:
    //方法将在下文实现...
};

插入

描述：向 Trie 中插入一个单词 word

实现：这个操作和构建链表很像。首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾。

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

查找

描述：查找 Trie 中是否存在单词 word

实现：从根结点的子结点开始，一直向下匹配即可，如果出现结点值为空就返回false，如果匹配到了最后一个字符，那我们只需判断node->isEnd即可。

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

前缀匹配

描述：判断 Trie 中是或有以 prefix 为前缀的单词

实现：和 search 操作类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，那后面一定有单词是以它为前缀的。

bool prefixMatched(const string& prefix) {
    Trie* node = this;
    for (char c : prefix) {
        node = node->next[c - 'a'];
        if (node == NULL) {
            returnfalse;
        }
    }
    returntrue;
}

删除

描述：从 Trie 中删除一个单词 word

删除操作稍微有点抽象，不如先看个栗子吧！

由单词”ab”, “abc”, “aec” 构成的 Trie，单独删除 “abc” 或者 “ab” 或者 “aec” 之后会是啥样呢？

三分钟基础：什么是 trie 树？未进行删除三分钟基础：什么是 trie 树？只删除了单词”abc”三分钟基础：什么是 trie 树？只删除了单词”ab”三分钟基础：什么是 trie 树？只删除了单词”aec”

实现：我们首先要一直递归匹配到 word 的最后一个字符，并将最后一个字符对应结点的isEnd置为false，然后逐步删除并返回上一个结点。注意只有在当前结点的子结点都为空或者当前结点不是其它单词的结束结点时，才能将它删除。

void deleteWord(const string& word) {
    if (!search(word)) {
        return;
    }
    Trie* node = this;
    __deleteWord(node, word, 0);
}

void __deleteWord(Trie*& node, conststring& word, int d) {
    if (d == word.length()) {
        node->isEnd = false;
    } else {
        __deleteWord(node->next[word[d]-'a'], word, d+1);
    }
    if (node->isEnd) {
        return;
    }
    for (Trie* item : node->next) {
        if (item != NULL) {
            return;
        }
    }
    delete node;
    node = NULL;
}

到这我们就已经实现了对 Trie 的一些基本操作，这样我们对 Trie 就有了进一步的理解。完整代码我贴在了文末，里面额外实现了查找 Trie 中所有单词和查找以指定前缀开头所有单词的方法，同时还进一步简化了代码。

总结

通过以上介绍和代码实现我们可以总结出 Trie 的几点性质：

  1. Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。

  2. 查找或插入一个长度为 L 的单词，访问 next 数组的次数最多为 L+1，和 Trie 中包含多少个单词无关。

  3. Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m^n)。

最后，关于 Trie 希望你能记住 8 个字：一次建树，多次查询。(慢慢领悟叭~~)

全部代码

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

    //返回与前缀prefix匹配的最后一个结点的地址
    Trie* __prefix(conststring& prefix) {
        Trie* node = this;
        for (char c : prefix) {
            node = node->next[c - 'a'];
            if (node == NULL) {
                returnNULL;
            }
        }
        return node;
    }

    //获取以root为起始结点的所有单词void __getWords(Trie* root, string& word, vector<string>& allWords) {
        if (root == NULL) {
            return;
        }
        if (root->isEnd) {
            allWords.push_back(word);
        }
        for (int i = 0; i < 26; i++) {
            word.push_back(static_cast<char>('a'+i));
            __getWords(root->next[i], word, allWords);
            word.pop_back();
        }
    }

    //删除一个单词void __deleteWord(Trie*& node, conststring& word, int d) {
        if (d == word.length()) {
            node->isEnd = false;
        } else {
            __deleteWord(node->next[word[d]-'a'], word, d+1);
        }
        if (node->isEnd) {
            return;
        }
        for (Trie* item : node->next) {
            if (item != NULL) {
                return;
            }
        }
        delete node;
        node = NULL;
    }

public:
    //构造函数
    Trie() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }

    //插入函数void insert(const string& word) {
        Trie* node = this;
        for (char c : word) {
            if (node->next[c-'a'] == NULL) {
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;
    }

    //查询函数bool search(const string& word) {
        Trie* node = __prefix(word);
        if (node == NULL) {
            returnfalse;
        }
        return node->isEnd;
    }

    //前缀匹配函数bool prefixMatched(const string& prefix) {
        Trie* node = this;
        for (char c : prefix) {
            node = node->next[c - 'a'];
            if (node == NULL) {
                returnfalse;
            }
        }
        returntrue;
    }

    //获取以prefix为前缀的所有单词vector<string> getAllWordsOfPrefix(conststring& prefix) {
        vector<string> words;
        string word = prefix;
        Trie* node = __prefix(prefix);
        __getWords(node, word, words);
        return words;
    }

    //获取Trie中所有单词vector<string> getAllWords() {
        string word = "";
        return getAllWordsOfPrefix(word);
    }

    //删除一个单词void deleteWord(const string& word) {
        if (!search(word)) {
            return;
        }
        Trie* node = this;
        __deleteWord(node, word, 0);
    }
};

看动画理解Trie树

转载于https://www.cxyxiaowu.com/1873.html

Trie这个名字取自“retrieval”，检索，因为Trie可以只用一个前缀便可以在一部字典中找到想要的单词。  
虽然发音与「Tree」一致，但为了将这种 字典树 与 普通二叉树 以示区别，程序员小吴一般读「Trie」尾部会重读一声，可以理解为读「TreeE」。

Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

此外 Trie 树也称前缀树（因为某节点的后代存在共同的前缀，比如pan是panda的前缀）。

它的key都为字符串，能做到高效查询和插入，时间复杂度为O(k)，k为字符串长度，缺点是如果大量字符串没有共同前缀时很耗内存。

它的核心思想就是通过最大限度地减少无谓的字符串比较，使得查询高效率，即「用空间换时间」，再利用共同前缀来提高查询效率。

Trie树的特点

假设有 5 个字符串，它们分别是：code，cook，five，file，fat。现在需要在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 5 个字符串依次进行字符串匹配，那效率就比较低，有没有更高效的方法呢？

如果将这 5 个字符串组织成下图的结构，从肉眼上扫描过去感官上是不是比查找起来会更加迅速。

看动画轻松理解「Trie树」Trie树样子

通过上图，可以发现 Trie树 的三个特点：

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

  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串

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

通过动画理解 Trie 树构造的过程。在构造过程中的每一步，都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后，Trie 树就构造好了。

看动画轻松理解「Trie树」Trie 树构造

Trie树的插入操作

看动画轻松理解「Trie树」

Trie树的插入操作

Trie树的插入操作很简单，其实就是将单词的每个字母逐一插入 Trie树。插入前先看字母对应的节点是否存在，存在则共享该节点，不存在则创建对应的节点。比如要插入新单词cook，就有下面几步：

  • 插入第一个字母 c，发现 root 节点下方存在子节点 c，则共享节点 c

  • 插入第二个字母 o，发现 c 节点下方存在子节点 o，则共享节点 o

  • 插入第三个字母 o，发现 o 节点下方不存在子节点 o，则创建子节点 o

  • 插入第三个字母 k，发现 o 节点下方不存在子节点 k，则创建子节点 k

  • 至此，单词 cook 中所有字母已被插入 Trie树 中，然后设置节点 k 中的标志位，标记路径 root->c->o->o->k 这条路径上所有节点的字符可以组成一个单词cook

Trie树的查询操作

在 Trie 树中查找一个字符串的时候，比如查找字符串 code，可以将要查找的字符串分割成单个的字符 c，o，d，e，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径。

看动画轻松理解「Trie树」

code的匹配路径

如果要查找的是字符串cod(鳕鱼)呢？还是可以用上面同样的方法，从根节点开始，沿着某条路径来匹配，如图所示，绿色的路径，是字符串cod匹配的路径。但是，路径的最后一个节点「d」并不是橙色的，并不是单词标志位，所以cod字符串不存在。也就是说，cod是某个字符串的前缀子串，但并不能完全匹配任何字符串。

看动画轻松理解「Trie树」c

od的匹配路径

程序员不要当一条咸鱼，要向 cook 靠拢：）

Trie树的删除操作

Trie树的删除操作与二叉树的删除操作有类似的地方，需要考虑删除的节点所处的位置，这里分三种情况进行分析：

删除整个单词（比如hi）

看动画轻松理解「Trie树」

删除整个单词

  • 从根节点开始查找第一个字符h

  • 找到h子节点后，继续查找h的下一个子节点i

  • i是单词hi的标志位，将该标志位去掉

  • i节点是hi的叶子节点，将其删除

  • 删除后发现h节点为叶子节点，并且不是单词标志位，也将其删除

  • 这样就完成了hi单词的删除操作

删除前缀单词（比如cod）

看动画轻松理解「Trie树」

删除前缀单词


这种方式删除比较简单。
只需要将cod单词整个字符串查找完后，d节点因为不是叶子节点，只需将其单词标志去掉即可。

删除分支单词（比如cook）

看动画轻松理解「Trie树」

删除分支单词


与 删除整个单词 情况类似，区别点在于删除到 cook 的第一个 o 时，该节点为非叶子节点，停止删除，这样就完成cook字符串的删除操作。

Trie树的应用

事实上 Trie树 在日常生活中的使用随处可见，比如这个：

具体来说就是经常用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

1. 前缀匹配

例如：找出一个字符串集合中所有以 五分钟 开头的字符串。我们只需要用所有字符串构造一个 trie树，然后输出以 五−>分−>钟 开头的路径上的关键字即可。

trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

看动画轻松理解「Trie树」

google搜索

2. 字符串检索

给出 N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，按最早出现的顺序写出所有不在熟词表中的生词。

检索/查询功能是Trie树最原始的功能。给定一组字符串，查找某个字符串是否出现过，思路就是从根节点开始一个一个字符进行比较：

  • 如果沿路比较，发现不同的字符，则表示该字符串在集合中不存在。

  • 如果所有的字符全部比较完并且全部相同，还需判断最后一个节点的标志位（标记该节点是否代表一个关键字）。

Trie树的局限性

如前文所讲，Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

假设字符的种数有m个，有若干个长度为n的字符串构成了一个 Trie树 ，则每个节点的出度为 m（即每个节点的可能子节点数量为m），Trie树 的高度为n。很明显我们浪费了大量的空间来存储字符，此时Trie树的最坏空间复杂度为O(m^n)。也正由于每个节点的出度为m，所以我们能够沿着树的一个个分支高效的向下逐个字符的查询，而不是遍历所有的字符串来查询，此时Trie树的最坏时间复杂度为O(n)。

这正是空间换时间的体现，也是利用公共前缀降低查询时间开销的体现。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xiuzhublog/p/12814155.html