Trie 的删除操作
我们并没有实现 Trie 的删除操作，在大多数情况下比如竞赛面试使用 Trie 的时候基本上都不会涉及删除操作的。
但是如果在实际应用中使用 Trie 的话，很多时候是要涉及删除操作的。
比如我们做一个通讯录，使用 Trie 创建通讯录的话，我们将通讯录中的每一个人名当做单词插入到 Trie 中，在单词最后一个字母的位置存储相应的通讯录的信息，电话号码也好，地址也好，邮编也好或者是这些信息的和，如果我们使用 Trie 做这个通讯录的话，相应的就要做删除操作，为 Trie 实现删除操作也是比较容易的。
比如当前的 Trie 是这样，如果想删除 deer 这个词的话，当搜索到 deer 这个词的最后一个字母之后，自底向上再进行删除就好了。
在这个删除过程中，对于每一个节点，如果 next 为空了相应的都可以删除，所以删除之后相应的就变成了下面这个样子。
d 这个节点不能删除，因为 d 这个节点除了之前的 next 指向 e 之外在这里还指向 o。
还有种情况，比如我要删除 pan 这个单词，pan 单词的末尾根本就不是个叶子节点，这种情况下也很简单，直接把这个节点的 isWord 删除就好了。
Trie 的局限性
对于一种数据结构，如果它有那么大的优势能够以那么高的性能进行字符串的访问，那么它一定就要相应的劣势，世界还是很公平的。对于 Trie 来说，最大的局限性就是“空间”。
对于 Trie 来说，每一个 node 只承载了一个字符的信息，而对于从这个字符到下一个字符需要使用 TreeMap 这样一个映射去映射到下一个字符，即使我们讨论的是 26 个字母表这样一个字符空间的话，那么这个 TreeMap 最多也要存储 26 条记录，换句话说我们的存储空间整体基本可以认为是原来的字符串所占的空间的 27 倍那么大，这个空间的消耗是非常多的。
在解决这个问题相应的也有一些变种。最为典型的一种变种就是“压缩字典树”。
压缩字典树（Compressed Trie）
在我们使用 Trie 的过程中，很多时候对于一个节点只有一个后续的字符，那么在这种情况下，这两个后续的字符完全可以合并起来，单链上有多个字符也可以完全合并在一起，因为通过这个字符节点无法访问到其他字符，只能访问到下一个这个字符，所以可以将原来的 Trie 改造成右边的样子。
从根节点触发，访问以 c 为起始的单词，在我们当前的 Trie 中只有一个 cat，那么我们把这个 cat 放在一个节点中就好了，其他地方同理。
对于 panda 要注意，由于 pan 也是这个 Trie 中的一个词，所以我们要把 pan 和 da 这两部分分离开，就变成了现在这样子。
对于压缩字典树，空间进行了一定程度的节省，但是维护成本也更高了。
如果再添加一个单词，比如添加 park，走 pan 这条路，pa 又是一个前缀了，要对 pan 进行拆分，所以又变得复杂一些。
三分搜索树（Ternary Search Trie）
Ternary 和 binary 对应，是一个三分的意思，对于任意一个节点 d，分了三个岔，这三个岔分别代表小于 d，等于 d，大于 d。
稍微拓展一下，变成下面这个样子，这个三分搜索树中存储了 dog 这个词，我们用搜索的过程演示一下
首先搜索字母 d，根节点就是这个 d
之后就可以看根节点的中间这个子树相应的下一个节点，下一个节点是 k，可是我们要搜索的字母是 o，o 比 k 要大，所以我们到 k 的右子树去找，k 的右子树的节点是 o
接下来继续到 o 的中间子树去找，下一个要找的字符是 g，g 比 l 要小，所以去 l 的左子树找，至此就找到 dog 单词。
我们用三分搜索树搜索一个单词所需要的时间比单词中的字母总数要多的，这是因为有可能走到并不是我们要找的单词的节点。
三分搜索树的优点就是对于每一个节点只有左中右三个孩子，而不像 Trie 那样用一个 map 来表示它的孩子，所以它大大节省了空间，相应的就牺牲了一定的时间。
源码下载
下载地址导航目录
查看导航本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接：数据结构笔记总结（9.7）更多和 Trie 字典树相关的话题
