trie树是字符串算法里很常见的一种数据结构。用于存储多个串。它本质上是一个自动机。又叫字典树。如果用trie树存储一个词典,要查找某个词是否在字典里,理论上是可以获得O(n)的复杂度的,而空间开销上,理论上也不会超过各个串长度之和,甚至要小于它们的长度之和。