字典树

字典树又称前缀树，Trie树，顾名思义，它是一种型似字典的树形结构，主要用于快速检索字符串是否存在，查找时间复杂度时O(n)，n是查找的字符串长度。

比如说在集合['abc', 'abb', 'acc', 'aca', 'acb', 'acbd']中查找字符串'acbd'，一般来说我们会遍历集合，比较集合中的每一个字符串，如果集合较小，这种方式还行，如果集合特别大，这样效率就会非常低下，这种情况下就可以使用字典树来解决，下面看看字典树的结构。

如果要查找acbd，先从root出发，查找是否存在子节点a，存在，继续查找节点a是否存在子节点c，存在，继续查找节点c是否存在子节点b，存在，继续查找节点b是否存在子节点d，存在，查找完毕。很明显查找过程只和当前字符串长度有关，和集合中有多少元素并无关系。下面是字典树的简单实现。