Trie
什么是 Trie
咱们晓得一个线性表的程序查找的工夫复杂度为 O(n);二分搜寻树的查找为 O(log n),它们都和数据结构中的元素个数相干。对于线性表和二分搜寻树的工夫复杂度剖析有须要的能够查看 Set 汇合和 BinarySearchTree 的工夫复杂度剖析
本文介绍的 Trie 字典树 (次要用于存储字符串) 查找速度次要和它的元素 (字符串) 的长度相干[O(w)]。
Trie 字典树次要用于存储字符串,Trie 的每个 Node 保留一个字符。用链表来形容的话,就是一个字符串就是一个链表。每个 Node 都保留了它的所有子节点。
咱们日常中应用的通讯录就是一个例子。
如果有 N 个条目,应用树结构查问的工夫复杂度是 O(logn)
而如果用 Trie 查问每个条目标工夫复杂度与字段中一共有多少条目无关!工夫复杂度为 O(W)
W 为查问单词的长度!
每个节点有 26 个指向下个节点的指针
Class Node{
char c;
Node next[26];
}
在 Trie 中叶子节点并不一定是单词的结尾,像平底锅的英文是 pan 而熊猫是 panda 咱们不能只依据叶子节点来辨别单词的开端,所以咱们须要一个变量来存储以后节点是否是某个单词的结尾。
class Node{
boolean isWord;
Map<char,Node> next;
}
特点
- 根节点不蕴含字符,除根节点外每一个节点都只蕴含一个字符
- 从根节点到某一节点,门路上通过的字符连接起来,为该节点对应的字符串
- 每个节点的所有子节点蕴含的字符都不雷同
Trie 字典树的新增
public class Trie {
private class Node{
public boolean isWord;
public TreeMap<Character,Node> next;
public Node() {this(false);
}
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();}
}
private Node root;
private int size;
public Trie(){root = new Node();
size = 0;
}
// 取得 Trie 中存储单词的数量
public int getSize(){return size;}
// 向 Trie 中增加一个新的单词 word
public void add(String word){
Node cur = root;
for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);
if(cur.next.get(c) == null){cur.next.put(c,new Node());
}
cur = cur.next.get(c);
}
if(!cur.isWord){
cur.isWord = true;
size ++;
}
}
}
Trie 字典树的查问
// 查问单词 word 是否在 Trie 中
public boolean contains(String word){
Node cur = root;
for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);
if (cur.next.get(c) == null){return false;}
cur = cur.next.get(c);
}
return cur.isWord;
}
// 查问是否在 Trie 中有单词以 prefix 为前缀
public boolean isPrefix(String prefix){
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {char c = prefix.charAt(i);
if (cur.next.get(c) == null){return false;}
cur = cur.next.get(c);
}
return true;
}