博客

转载自

http://epic.32o.cn/article.asp?id=47

，但是这个地址已经不存在了……


所以从维基百科拿来个图进行解释：http://zh.wikipedia.org/wiki/Trie

今天在vijos有人问我trie树怎么弄。索性就写详细点，让众多新手参考一下。

Trie树就是字符树，其核心思想就是空间换时间。举个简单的例子。

给你100000个长度不超过10的单词。对于每一个单词，我们要判断他有没有重复给出，如果重复出现了，则给出第一次出现的位置。

这题当然可以用hash来，但是我要介绍的是trie树，在某些方面它的用途更大，比如说对于某一个单词，我要查看它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。

现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要在所有单词中查找是否有重复，那么这个算法的复杂度就是O(n^2)，显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的……这样一个树的模型就渐渐清晰了。对于每一个节点，从根遍历到他的过程就是一个单词。那么，对于一个单词，我只要顺着他从跟走到对应的节点，再看这个节点是否存在就可以知道它是否出现过了。新建立节点则相当于插入新单词。这样一来我们询问和插入可以一起完成，所用时间仅仅为单词长度，在这一个样例，便是10。

我们可以看到，trie树每一层的节点数是26^i 级别的。所以为了节省空间，我们用动态链表，或者用数组来模拟动态，空间的花费不会超过单词数×单词长度。

程序非常好实现，区区几行，我就不写了，自己琢磨吧。如果还是不懂请留言。