Trie - 字典树
- 字典树这种数据结构最典型的用例就是存单词；
- 相较于普通的树结构O(logn)的时间复杂度，其时间复杂度为O(w)，w为单词的长度；
基础代码
- Trie中的节点Node是不存储字符的，字符作为“边”，存储在父节点的映射next的key中；
- Trie作为树结构，一种高级的数据结构，和链表，二叉树一样，本身只是个壳，里面是要封装一个头指针的，作为拎起整棵树的拎手；
- 在向Trie中添加单词的时候，并没有用递归的方式，而是遍历；
import java.util.TreeMap;
public class Trie {
private class Node{
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
public Node(){
this(false);
}
}
private Node root;
private int size;
public Trie(){
root = new Node();
size = 0;
}
// 获得Trie中存储的单词数量
public int getSize(){
return size;
}
}
向Trie中添加一个新的单词word
// 向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 ++;
}
}
