什么是“Trie树”
Trie 树，也叫“字典树”。它是一个树形结构，专门用于处理字符串匹配，解决在一组字符串集合中快速查找某个字符串的问题。你可以看一下下面的 Trie 树，它存储了：how 、hi、her、hello、so、see 六个单词。
Trie树-什么是Trie树.jpg
其中，根节点不包含信息，从根节点到红色节点的一条路径表示一个字符串，其中，红色节点不一定是叶子节点。
通过观察上面的 Trie树 ，你可以看出 Trie树 本质就是利用字符串之间的公共前缀，将重复的前缀合并在一起。根据这个它的这个特点，我们可以通过查询字符的前缀，快速地查询到具有相同前缀的单词。
Trie树 的构建
Trie树 的构建很简单，依然以之前的六个单词为例，它们的 Trie树 构建过程如下：
Trie树-构建.jpg
Trie树-构建2.jpg
Trie树 的查找过程
当我们要在 Trie树 中查找字符串 “her” 的时候，会产生如下的查找路径（用绿色标注出来的路就）：
Trie树-查找.jpg
如果路径终点是一个红色节点，查询成功；如果非红色节点，则查询失败，例如下面查找 “he” 失败：
Trie树-查找失败.jpg
如何实现 Trie树
Trie树 要实现两个操作：将字符串集合构造成 Trie树 和 在 Trie树 中查询一个字符串。为了实现这两个操作，我们需要关注 如何存储一个 Trie树。
存储 Trie树
以前我们学习了二叉树的存储结构，它的存储结构非常简单。但是对于 Trie树 来说，它是一个多叉树，所以对于其孩子节点的存储就会比较麻烦。
Trie树-指针构建.jpg
由于我们采用这样的存储方式，这导致我们的每个节点都要保存整个字符集的指针，这导致了内存的浪费。
代码实现
前面我们已经讲了 Trie树 的构建、查询、存储。下面就给出它的实现代码，帮助你理解：
public class Trie {
private TrieNode root = new TrieNode('/'); // 存储无意义字符
// 往Trie树中插入一个字符串
public void insert(char[] text) {
TrieNode p = root;
for (int i = 0; i < text.length; ++i) {
int index = text[i] - 'a';
if (p.children[index] == null) {
TrieNode newNode = new TrieNode(text[i]);
p.children[index] = newNode;
}
p = p.children[index];
}
p.isEndingChar = true;
}
// 在Trie树中查找一个字符串
public boolean find(char[] pattern) {
TrieNode p = root;
for (int i = 0; i < pattern.length; ++i) {
int index = pattern[i] - 'a';
if (p.children[index] == null) {
return false; // 不存在pattern
}
p = p.children[index];
}
if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
else return true; // 找到pattern
}
public class TrieNode {
public char data;
public TrieNode[] children = new TrieNode[26];
public boolean isEndingChar = false;
public TrieNode(char data) {
this.data = data;
}
}
}
性能分析
时间复杂度
构建 Trie树 的时间复杂度：构建过程需要扫描所有的字符串，时间复杂度是 O(n)，n表示所有字符串的长度之和。
查询的时间复杂度：查询过程非常快，假设查询的字符串的长度是 k ，我们只需要比对大约 k 个节点，也就是说，查询的时间复杂度为 O(k)。
内存分析
由于要保存字符集中的指针， Trie树 需要耗费大量内存：假设我们的字符集为 a~z 的 26 个小写字母，那么在每个节点中，都要有一个存储 26 个字母的指针，一个指针的大小是 8 字节，这就代表，**如果你要存储 1 字节的信息，我们需要在该节点中额外耗费 26*8 = 208 个字节。
我们可以牺牲一点查询效率，将存储指针的数据结构换成有序数组、跳表、红黑树等。
Trie树-节省内存-缩点优化.jpg
然而，无论如何， Trie树 的内存消耗还是比较大的，它对要处理的字符串有极其严苛的要求：
- 字符串中包含的字符集不能太大。如果字符集太大，存储空间就会浪费严重，即使进行优化，也要牺牲查询、插入效率。
- 字符串的前缀重合要比较多，不然空间消耗较大。
- Trie树 使用了指针进行存储，对缓存不友好。
- 在工程中，可能要我们自行实现一个 Trie树 ，这会让工程变得复杂。
所以，对于在一组字符串中查找字符串的问题，在工程中我们更倾向于使用散列表或者红黑树。
Trie树 的应用场景： Trie树 比较适合这样的应用场景：当我们需要使用前缀快速查找相关的字符串的时候。
例如：搜索引擎的自动补全功能，依然使用之前的例子，如果我们要在 how 、hi、her、hello、so、see 中寻找以 h 和 he 开头的字符串，在 Trie 树 中的执行过程如下：
Trie树-实现前缀查找.jpg
这样的应用场景比较常见，比如 输入法的自动补全功能，IDE代码编辑器自动补全功能、浏览器网址输入的自动补全功能等。
总结
Trie 树 可以实现在一组字符串中快速查找目标字符串的功能。如果这组字符串的重复前缀不是很多，那么这种数据结构就比较耗费内存。
尽管耗费内存比较大，但是它的查询效率非常高。
Trie 树 的优势不在于做动态集合的数据查尔，使用散列表或者红黑树可能更加适合。Trie 树最大的优势是查找前缀匹配的字符串，比如搜索引擎中的关键词提示的场景。
以上就是关于 Trie树 的全部内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论