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字典树相关的话题
