动画Trie树
Trie树也称之为前缀树，适合处理前缀匹配问题。也因为每一个节点都存储26个字母，也称之为字典树，发明Trie树的人喜欢把这个单词读成/ˈtriː/tree，其他人喜欢读成/ˈtraɪ/ "try"。
本篇是一个入门介绍，后面有动画。
前缀树每个节点有2个属性：一个是26个子孩子的数组，一个是是否是结尾字符。为了便于理解，一起来看下leetcode 208题，算是Trie树的裸题。
题目：
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
题解
构造函数中初始化根节点，Trie*孩子节点数组初始化为0，结束标识设置为0。
插入函数从根节点开始查找，如果字符不存在，就创建一个新的Trie节点，继续遍历单词字符，创建过程很像插入了一个单词链表。
搜索函数和插入类似，遍历节点，如果不存在子孩子则返回失败，如果遍历完成，还需要保证最后一个字符的结束标识为1。
前缀函数和搜索类似，不过不需要关心结束标识。
Trie动画
源代码
class Trie {
public:
Trie* c [26];
char v :1; //结束标识
/** Initialize your data structure here. */
Trie() {
memset(c, 0, sizeof(c));
v = 0;
}
Trie* searchPrefix(string & prefix) {
Trie* p = this;
for(char &ch : prefix){
char index = ch-'a';
if(!p->c[index]){
return 0;
}
p = p->c[index];
}
return p;
}
/** Inserts a word into the trie. */
void insert(string word) {
Trie* p = this;
for(char &c:word){
char index = c-'a';
if(p->c[index] == 0){
p->c[index] = new Trie();
}
p = p->c[index];
}
p->v = 1;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Trie* v = searchPrefix(word);
return v && v->v;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return searchPrefix(prefix);
}
};
总结
Trie树的关键点在于像创建链表一样创建每一个单词，每个单词的最后一个字符节点设置结束标识。每个节点有26个孩子节点，所以Trie树会比较耗费内存。
DAT树
为了解决Trie树占用内存过大问题，三个日本人设计了一种特殊的数据结构，用双数组存储Trie树信息，这个设计极大的减少了内存占用问题，DAT树是Trie树内存的1%左右，在实际大规模应用中，基本上都需要使用DAT进行优化。极简笔记的中文分词就是使用的DAT，内存占用非常小。