怎么做博客网站,建设厅特种作业,萨龙 wordpress,wordpress 顶部大图文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
1 Trie树的使用场景
搜索引擎中的搜索词建议。当你在搜索引擎中输入词#xff0c;搜索引擎提示给你一个词的列表#xff0c;帮助你快速输入想搜索的词。 这个功能…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
1 Trie树的使用场景
搜索引擎中的搜索词建议。当你在搜索引擎中输入词搜索引擎提示给你一个词的列表帮助你快速输入想搜索的词。 这个功能要想想做得精准肯定需要很多优化工作。但这个功能的底层数据结构就是Trie树。
2 什么是Trie树
Trie树也叫字典树是一种树形结构专门用于处理在一个字符串集合中查找某个字符串。
2.1 Trie树的结构
例如需要在howhiherhellososee这六个字符串中查找某个字符串。我们也可以用字符串和这6个字符串逐个比较只是效率不高。使用Trie树只需要一次比较就可以。我们先用这六个字符串构建一个Trie树。 之后每次查找从Trie树的根节点开始查找。Trie树是利用字符串之间的公共前缀将重复的前缀合并在一起。根节点不包含任何信息每个节点是字符串中的一个字符。从根节点到红色节点的一条路径表示一个字符串。重点红色节点并不都是叶子节点例子中没有表示出来。
2.2 Trie树的构造过程 2.3 Trie树的查找过程
当我们查找一个字符串的时候从根节点开始。例如查找字符串her我们把字符串切分成字符h e r从根节点开始走出路径/-h-e-r并且r节点有字符串结束标志树中包含字符串her。 例如我们查找字符串he我们把字符串切分成字符h e。从根节点开始走出路径/-h-e。但是e没有字符串结束标志所以树中不包含he。
3 Trie树代码实现
Trie树的操作包括初始化和查找。 Trie树是一棵多叉树。在二叉树的时候节点每个节点是用左右指针指向子节点。
class BinaryTreeNode {char data;BinaryTreeNode left;BinaryTreeNode right;
}
Trie树是一个多叉树怎么存储节点的子节点呢一种方法是假设字符串只包含小写字母可以在字母和数组下标之间做映射使用数组存储子节点。如果子节点的字母是a存储在children[0]如果子节点的字母是b存储在children[1]…
class TrieNode {char data;TrieNode children[26];
}整体代码
public class Trie {private TrieNode root new TrieNode(/);public void insert(String text){char[] chars text.toCharArray();TrieNode node root;for(int i0;ichars.length;i){int idx chars[i] - a;if(node.childern[idx]null){node.childern[idx] new TrieNode(chars[i]);}node node.childern[idx];}node.endWord true;}public boolean find(String text){TrieNode node root;char[] chars text.toCharArray();for(int i0;ichars.length;i){int idx chars[i] - a;if(node.childern[idx]null){return false;}node node.childern[idx];}return node.endWord;}class TrieNode{private char data;private TrieNode[] childern;private boolean endWord;public TrieNode(char ch){this.data ch;}}
}Trie树的时间复杂度。Trie树构建的时候需要遍历所有的字符时间复杂度O(n)。n为 所有字符串长度之和。查找的时候每个字符遍历一次时间复杂度O(m)m是查找字符串长度。
4 Trie树适合解决的问题
4.1 Trie树的缺点耗内存
上面的代码中每个节点都需要长度为26的数组存储子节点。但是并不是每个字母后面都会跟着26个字母很多数组 中的值是空的。 这还是只考虑了小写字母的情况当要存储的包含数字、中文的时候按照这种方式存储会需要 更多的内容。这个时候可以考虑使用哈希表存储子节点。也可以使用有序数组、跳表、红黑树等牺牲一定的性能。例如使用有序数组那插入的时候要维护数组有序多消耗时间查询每一层子节点的时候不是O(1)而是需要二分。
4.2 Trie树的优点前缀匹配
对于支持动态数组高效操作的数据结构有散列表、红黑树、跳表等。这些数据结构也可以实现字符串查找。而Trie树除了字符串匹配之外更常用于字符串前缀匹配。就是前面提到的搜索词提示。词库是用户的热门搜索词这些词构建一棵Trie树。我们把用户输入的词作为前缀子串去Trie树中匹配将匹配到的字符串返回。 实际工程中会遇到 一些问题需要解决 1 词库中匹配到的词可能很多怎么排序 2 在用户拼写错误的情况下依然能够返回正确的提示词怎么做到
