本文共 2627 字,大约阅读时间需要 8 分钟。
前缀树是一种树数据结构,用于检索字符串数据集中的键。这一高效的数据结构有多种应用:
图 1. 谷歌的搜索建议
图2. 文字处理软件中的拼写检查
图 3. 使用Trie树的最长前缀匹配算法,Internet 协议(IP)路由中利用转发表选择路径。
图 4. T9(九宫格输入),在 20 世纪 90 年代常用于手机输入
图 5. Trie 树可通过剪枝搜索空间来高效解决 Boggle 单词游戏
还有其他的数据结构,如平衡树和哈希表,使我们能够在字符串数据集中搜索单词。为什么我们还需要 Trie 树呢?尽管哈希表可以在 O(1)O(1) 时间内寻找键值,却无法高效的完成以下操作:
Trie 树优于哈希表的另一个理由是,随着哈希表大小增加,会出现大量的冲突,时间复杂度可能增加到 O(n)O(n),其中 nn 是插入的键的数量。与哈希表相比,Trie 树在存储多个具有相同前缀的键时可以使用较少的空间。此时 Trie 树只需要 O(m)O(m) 的时间复杂度,其中 mm 为键长。而在平衡树中查找键值需要 O(m log n)O(mlogn) 时间复杂度。
Trie 树是一个有根的树,其结点具有以下字段:。
class TrieNode{ //R links to node children private TrieNode[] links; private final int R = 26; private boolean isEnd; public TrieNode(){ links = new TrieNode[R]; } public boolean containsKey(char ch){ retrurn links[ch-'a']!=null; } public TrieNode get(char ch){ return links[ch-'a']; } public void put(char ch,TrieNode node){ links[ch-'a'] = node; } public void setEnd(){ isEnd = true; } public boolean isEnd(){ return isEnd; } }
通过搜索Trie树来插入一个键。我们从根开始搜索它对应于第一个键字符的链接。有两种情况:
重复以上步骤,直到达到键的最后一个字符,然后将当前节点标记为结束结点,算法结束。
class Trie{ private TrieNode root; public Trie(){ root = new TrieNode(); } // insert into a word into the trie public void insert(String word){ TrieNode node = root; for(int i=0;i
每个键在Trie中表示为从根到内部结点或叶的路径。用第一个键字符从根开始,检查当前节点中与键字符对应的链接。有两种情况:
class Trie{ //.... private TrieNode searchPrefix(String word){ TrieNode node = root; for(int i=0;i
该方法与在 Trie 树中搜索键时使用的方法非常相似。我们从根遍历 Trie 树,直到键前缀中没有字符,或者无法用当前的键字符继续 Trie 中的路径。与上面提到的“搜索键”算法唯一的区别是,到达键前缀的末尾时,总是返回 下true。我们不需要考虑当前 Trie 节点是否用 “isend” 标记,因为我们搜索的是键的前缀,而不是整个键。
class Trie{ // ... public boolean startsWith(String prefix){ TrieNode root = searchPrefix(prefix); return node!=null; }}
3358981)]
class Trie{ // ... public boolean startsWith(String prefix){ TrieNode root = searchPrefix(prefix); return node!=null; }}
转载地址:http://bbwdf.baihongyu.com/