1.字典树基础
1.1.字典树
- 字典树又称前缀树，对于一个字符串在加入字典树结构时，会合并相同的字符，字典树是一种多叉树
- 对于一个字符串的结尾字符，专门做一个标识，来表示存在一个字符串以此单词为结尾，从而避免子串被覆盖
- 根结点并不存储任何字符，仅代表着一个根，实际上字典树的效率取决于字符串的长度，也就是树的深度，而与字符串的数量没有关系。实际上对字符串来说，串长度不会太长，这也决定了这种数据结构的效率比较高
- 字典树在大量数据的情况下任然可以保持很高的效，这一性能是大量空间消耗换取的，但对于现在计算机而言，字典树带来的益处远比损耗要大，因此很有实际意义。
- 笔者实现的仅为最基础的字典树，实际上字典树对于减小空间消耗也有很多解决办法，这些变种在减少空间消耗的情况下，也会增加维护成本，代码复杂度提高和效率上会稍稍降低。
1.2.逻辑结构
-
直接举例说明，我们对字符串"adb"，"adbef"，"db"，"def"，"der"，"cc"构造字典树。
构造字典树.png
1.3.物理结构
- 在构造字典树时，比较常规的实现是使用Map结构
- 若字典树存储的是以英文字母为基础的单词字符串，则也可以固定长度，采用数组形式，每层节点数目为26个空间；但是实际上我们并不一定每层都会用到如此多的空间，会造成很大的浪费。
-
若对于存储为汉字或拥有其他特殊字符的字符出啊，采用Map结构就可以使用到便开辟空间，使空间使用率提高
上述字典树的物理结构：
字典树物理结构.png
2.字典树实现
2.1.构造函数
public class Trie {
private class Node {
//描述当前结点是否为一个单词
public boolean isWord;
public TreeMap<Character, Node> map;
public Node(boolean isWord) {
this.isWord = isWord;
this.map = new TreeMap<>();
}
public Node() { this(false); }
}
private Node root;
private int size;
public Trie() {
root = new Node();
size = 0;
}
/**
* 获取trie中存储的单词数量
* @return :
*/
public int getSize() { return size; }
2.2.新添一个字符串
/**
* 向trie中添加一个新的单词
* @param word ：
*/
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
Character c = word.charAt(i);
//若该字符不存在于当前结点保存的映射中，则新填一个映射保存该字符
if (cur.map.get(c) == null) {
cur.map.put(c, new Node());
}
//当前结点移动到该字符的结点处
cur = cur.map.get(c);
}
//当移动到单词最后一个字符，若字符为false,说明没有该字符
if (!cur.isWord) {
cur.isWord = true;
size++;
}
}
1.遍历以此保存每一个字符，若存在不进行操作，不存在添加该单词
2.标识最后一个字符为单词结尾
2.2.判断该单词是否存在
/**
* 查询trie中是否有word这个单词
* @return ：
*/
public boolean contains(String word){
Node cur = root;
for (int i = 0; i < word.length(); i++) {
Character c = word.charAt(i);
//若有一个字符不匹配，则单词不匹配
if (cur.map.get(c) == null) {
return false;
}
cur = cur.map.get(c);
}
//当遍历到最后一个单词后，判断是否存在该单词
return cur.isWord;
}
1.遍历确定是否每一个字符都存在
2.判断最后一个字符是否是一个字符串的结尾
2.3.判断是否存在以prefix为前缀的单词
/**
* 查询trie中是否有以prefix为前缀的单词
* @param prefix ：单词前缀
* @return ：
*/
public boolean isPrefix(String prefix){
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
Character c = prefix.charAt(i);
if(cur.map.get(c) == null){
return false;
}
cur = cur.map.get(c);
}
//当遍历完，前缀字符都拥有，所以有以此为前缀的单词
return true;
}
