Question

图解：数据结构与算法之字典树

Answer 1

字典树（Trie树）这一数据结构是不太常见但是十分好用<typo id="typo-32" data-origin="而" ignoretag="true">而</typo>一种数据结构，博主也就是最近一段时间做了几道字信昌节的题目才了解到字典树这一数据结构。并将自己的学习内容跟大家分享。

首先，何为字典树（Trie树）？顾名思义，就是在查询目标时，像字典一样按照一定排列顺序标准和步骤访问树的节点，举一个简单例子，英文字典查单词"He"，那么第一步你肯定要按照a-z的顺序先找到h这个首字母，然后再按照相同顺序找到e。博主所要介绍的字典树就是类似字典这样的结构。

上述查找单词的过程就是不断查找与所查单词相同前缀的字符串，直至查找到所查单词的最后一个字母。因此，字典树又称为前缀树(prefix Tree)。

以hell、hi、new、nop为例建立一个字典树，构造如下

根据上文所述可以得到字典树的结构性质

根据以上三点来构造字典树。

字典树的构造其实较为简单，和一般树的构造没有太大区别。接下来将对字典树的插入、删除、查询操作进行分析与讲解。

在没有字典树的时候，我们需要先构建出字典树。

以插入hell为例：

再插入单词hit，过程如下，检查＝>存在则访问/不存在则建立新节点再访问＝>直到要插入的单词到达最后一个字符。

字典树的插入操作比较简单，不需要考虑太多排序问题。

正如上文所说，按照一定的标准进行查询目标字符串，每个节点都储存一个字符，根节点到达子节点路径组成的字符串即为该节点所对应的字符串，那么查询目标字符串时按照从根节点一滑烂扒步一步访问相应字符所在的节点，其实也就是匹配字符串前缀的过程。

如下图，在字典树中，查询"hell"，

[图片上传失败...(image-f028c4-1611057619223)]

如果在该字典中查询no

删除操作相对于插入与查询复杂一点，但是也很简单，删除的前提是单词已经存在于字典树。

删除字典树节点的操作需要考虑目标字符串最后一个字符是否是树中的叶子节点。

因为一个单词可能是另一个单词的前缀部分，如果不是叶子节点，我们只需要把该单词的单词标志位清空即可，无需删除整个“树枝”。

比如，想要删除"no"这个单词

比如，想要删除"hell"这个单词，与第一种删除相同，只不过是从最后一个节点，'l'节点是叶子节点，开始往上进行节点删除操作。

比如，想要删除"hi",那么与前两种其实一致，访问到叶子节点'i',删除叶子节点，并向上访问，访问到'h'，由于删除'i'以后，'h'依然不是叶子节点，因此不再继续删除节点。

比如，想要删除"nop",与前几种类似，先访问到叶子节点'p'删除，然后上移发现'o'是叶子节点，然而'o'有单词标记位，所以，这里不再继续删除。

有上面几种删除操作，我们得到了删除的标准：

了解了这么多字典树的各种操历庆作，相信你对字典树的用途有个大概了解了，字典树最大作用是用于==字符串的各种匹配==，前缀匹配（模糊搜索），字符串查找（字典）等等。

博主只打出了“涓涓清泉”四个关键字，其搜索列表返回了诸多以涓涓清泉为首的选项

顾名思义，就是一个单纯的字典而已，不多举例。

字典树的构建，通过利用空间换时间的思想以及字符串的公共前缀减少无效的字符串比较操作从而使得插入和查找字符串变得高效．其插入或者查找的时间复杂度为O(n)，n为字符串长度。

当然，字典树有着它的弊端，当所插入的单词没有很多公共前缀时，字典树的构建变得十分复杂和低效。

字典树的难度不是很大，但却是一种十分有用的数据结构，掌握之后，对于解决一些有关字符串匹配、公共前缀的问题十分有帮助。

当然我们也说了，字典树有着自己的弊端，由于用空间换时间，如果遇到了一堆公共前缀很少的单词进行字典树构造时，空间需求就显得十分大了。