什么是 Trie 树？-技术圈

最近复习了 Trie 树的相关知识，有了更加深刻的理解。想去打会游戏放松下，突然接到了面试官的电话。

黑脸面试官

猿同学，看你简历上说熟悉数据结构，说说你对 Trie 树的理解。

猿六

Trie 树是一种数据结构，它又叫字典树。

Trie 树是一种多叉树的结构，每个节点保存一个字符，一条路径上的所有节点保存一个字符串。

下图表示了字符串：him 、 her 、 cat 、 no 、 nova 构成的 Trie 树。

从图中可以看出 Trie 树包含以下性质：

根节点不包含字符，其他节点包含一个字符。
从根节点到某一节点经过的字符连接起来构成一个字符串。如图中的 him 、 her 、 cat 、 no 、 nova。
一个字符串与 Trie 树中的一条路径对应。
在实现过程中，会在叶节点中设置一个标志，用来表示该节点是否是一个字符串的结尾，本例中用青色填充进行标记。
Trie 树中每个节点存储一个字符，从根节点到叶节点的一条路径存储一个字符串。另外，有公共前缀的字符串，他们的公共前缀会共用节点。如 her、 him 共用 h 节点。

黑脸面试官

如何生成 Trie 树？

猿六

Trie 树的生成过程，就是不断将字符串插入树中。

以插入字符串 him 、 her 、 cat 、 no 、 nova 为例，过程如下：

1. 插入 him :

根节点不存在子节点 h，因此创建子节点 h。
在节点 h 的基础上插入第二个字符 i。
节点 h 不存在子节点 i，创建子节点 i。
在节点 i 的基础上插入第三个字符 m。
节点 i 不存在子节点 m，创建子节点 m。并将该节点标记为字符串结束标志，完成 him 字符串插入。

2. 插入 her :

根节点存在子节点 h。不用重新创建子节点 h。
在节点 h 的基础上插入第二个字符 e。
节点 h 不存在子节点 e，创建子节点 e。
在节点 e 的基础上插入第三个字符 r。
节点 e 不存在子节点 r，创建子节点 r。并将该节点标记为字符串结束标志，完成 her 字符串插入。

3. 插入 cat：

根节点不存在子节点 c，因此创建子节点 c。
在节点 c 的基础上插入第二个字符 a。
节点 c 不存在子节点 a，创建子节点 a。
在节点 a 的基础上插入第三个字符 t。
节点 a 不存在子节点 t，创建子节点 t。并将该节点标记为字符串结束标志，完成 cat 字符串插入。

4. 插入 no:

根节点不存在子节点 n，因此创建子节点 n。
在节点 n 的基础上插入第二个字符 o。
节点 n 不存在子节点 o，创建子节点 o。并将该节点标记为字符串结束标志，完成 no 字符串插入。

5. 插入 nova:

根节点存在子节点 n，不用重新创建子节点 n。
在节点 n 的基础上插入第二个字符 o。
节点 n 存在子节点 o，不用重新创建子节点 o。
在节点 o 的基础上插入第三个字符 v。
节点 o 不存在子节点 v，创建子节点 v。
在节点 v 的基础上插入第四个字符 a。
节点 v 不存在子节点 a，创建子节点 a。并将该节点标记为字符串结束标志，完成 nova 字符串插入。

黑脸面试官

如何删除一个字符串？

猿六

删除一个字符串需要考虑的地方较多。

情况一：待删除的字符串末尾为叶节点，且与其它字符串无公共前缀。将节点逐一删除即可，例如删除 cat。

情况二：待删除字符串末尾不是叶节点。将字符串标志位置为 false 即可，例如删除 no 。

情况三：待删除字符串末尾为叶节点，并且中间有其它单词。逐一删除节点，直到待删除节点是另一个字符串的结尾为止，例如删除 nova。

情况四：待删除字符串某一节点还有其它子节点。逐一删除节点，如果待删除节点还有其它子节点，则停止删除，例如删除 him。

黑脸面试官

Trie 树有什么用？

猿六

Trie 树又叫字典树。字典是用来查字的，Trie 树最基本的作用是在树上查找字符串。

例如有 5 个字符串：him 、 her 、 cat 、 no 、 nova 。现在要查找 catch 是否存在。如果使用暴力的方法，需要用 catch 与这 5 个字符串分别进行匹配，效率较低。

如果将这 5 个字符串存储成 Trie 的结构，只需要顺着路径依次比较，比较完 cat 之后，没有节点与 c 匹配，所以字符串集合中不存在 catch。

黑脸面试官

写一下 Trie 树实现插入，检索，删除字符串的代码。

//实现 Trie 树节点结构struct trie_node{    int isKey = 0; //标志，0：不是字符串结尾，1：是字符串结尾    trie_node* child[26] = {nullptr}; //指向子节点指针};
//插入字符串：void insert(string s, trie_node* root){    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        if (!p->child[n])//没有对应子节点，创建        {            trie_node* q =new trie_node;            p->child[n] = q;          }        p = p->child[n];    }    p->isKey = 1;//字符串结尾标志位置为1}
//检索字符串bool search(string s, trie_node* root){    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        if (!p->child[n])            return 0;        p = p->child[n];    }    if (p->isKey)        return 1;    return 0;}//删除字符串：void remove(string s, trie_node* root){    if (!search(s, root))        return;    stack stkt;//存储路径上节点    stack<int> stkc;//存储待删除字符串    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        stkc.push(n);        stkt.push(p->child[n]);        p = p->child[n];    }    p->isKey = 0;//情况二，将标志位置为0    while (!stkt.empty())    {        trie_node* q;        q = stkt.top();        if (q->isKey == 1)//情况三，如果标志位1，停止            return;        for (int i = 0; i < 26; i++)//情况四，如果还有其他字符串公用此前缀，停止        {            if (q->child[i])                return;        }         delete q;//删除节点        stkt.pop();        stkt.top()->child[stkc.top()] = nullptr;//删除边        stkc.pop();    }}

黑脸面试官

Trie 树还有其他用途吗？

猿六

可以用来词频统计

词频统计

在构造树的过程中，已经将所有字符串遍历了一遍。可以在 Trie 树节点的数据结构中，增加一个 count 来计数。对于每个字符串的插入操作，若已存在，计数加 1，若不存在，插入后 count 置为 1。

要统计某个字符串出现的次数，只需要找到字符串结尾对应的节点，输出对应节点的 count 值即可。

//重写 Trie 树节点结构struct trie_node{    int isKey = 0; //标志，0：不是字符串结尾，1：是字符串结尾    int count = 0;//记录出现次数    trie_node* child[26] = {nullptr}; //指向子节点指针};
//重写插入字符串：void insert(string s, trie_node* root){    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        if (!p->child[n])        {            trie_node* q =new trie_node;            q->count += 1;            p->child[n] = q;          }        p = p->child[n];    }    p->isKey = 1;}
//实现词频统计int count(string s, trie_node* root){    if(!search(s,root))        return 0;    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        p = p->child[n];    }    return p->count;}

黑脸面试官

说说 Trie 树的优缺点。

猿六

Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

Trie树和哈希表一样，利用空间换取时间。

优点：插入和查询的效率很高，都为O(m)。其中 m 是待插入/查询的字符串的长度。

缺点：空间消耗比较大。

黑脸面试官

恩，今天先到这，等下一轮面试吧。

猿六

恩恩，谢谢黑脸面试官。

黑脸面试官

你说谁脸黑，你没下一次面试了。