应用场景
类似这种搜索框,当输入关键词时,下拉框会有Query提示词,用于提高用户体验和关键词修改建议,比如说我们搜索错误词,或者首字母拼写,仍然可以找到需要的内容,这在博客检索需要信息和商城类寻找具体商品时作用非常大,
字典树
这是用字典树实现的,也叫Tire树,又称单词查找树,键树,前缀树(?),是哈系树的变种,主要用于统计和排序,优点是可以最大限度减少无关字符串比较,效率很高
核心思想
用空间换时间,用字符串的公共前缀来降低查询所需时间,来提高事务效率,举个概念图的例子。
如图所示,当我们搜索北京和江苏会往两侧查找,而中兴和中国都与共同前缀“中”,这样从中开始查找,就会比从头查找效率更高。
图里面展示的字符串都被节点到节点的路径链接,为该结点对应的字符串,每个节点的所有子节点包含的字符都不同。
构建
我们先上代码,然后画图解释一下,棵树时怎样存储的
这是树结构的代码:
class TrieNode{
//子节点的映射
private final Map<Character,TrieNode> children = new HashMap<>();
//标记元素,检查这个节点是否是某个字符串的结尾
private boolean endWorld;
//判断当前节点是否有需要的子节点
public boolean containsKey(char check){
return children.containsKey(check);
}
// 获取指定字符的子节点
public TrieNode get(char check) {
return children.get(check);
}
// 设置指定字符串的子节点
public void put(char check, TrieNode node) {
children.put(check, node);
}
// 判断当前节点是否为字符串的结尾
public boolean isEnd() {
return endWord;
}
// 标记当前节点为字符串的结尾
public void setEnd() {
endOfWord = true;
}
}
调用树,写插入方法
public class Trie {
// 字典树的根节点
private final TrieNode root;
// 构造函数初始化根节点
public Trie() {
root = new TrieNode();
}
// 插入一个单词到字典树中
public void insert(String word) {
// 从根节点开始遍历
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
// 如果当前字符对应的子节点不存在,则创建一个新的节点并添加
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
// 移动到当前字符对应的子节点
node = node.get(currentChar);
}
// 标记最后一个节点为单词的结尾
node.setEnd();
}
// 检查字典树中是否包含指定单词
public boolean search(String word) {
// 先找到指定单词的最后一个节点
TrieNode node = searchPrefix(word);
// 如果节点不为空且标记为单词的结尾,则说明单词存在
return node != null && node.isEnd();
}
// 查找指定前缀在字典树中对应的最后一个节点
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char currentChar = prefix.charAt(i);
// 如果当前字符对应的子节点不存在,就新建节点
if (!node.containsKey(currentChar)) {
node = node.get(currentChar);
} else {
return null;
}
}
// 返回最后一个节点
return node;
}
}
测试方法
Trie trie = new Trie();
trie.insert("apple");
System.out.println(trie.search("apple")); // 返回 true
System.out.println(trie.search("app")); // 返回 false
图的解释
前面树的定义,差不多是这样的
用键值对存储每一个字符,然后加上一个检查标记,检查标记用于比对元素,比如我存在apple和app,我检索app时检索到了与apple共用的字符头“app”(代码中的searchPrefix方法),但是p的位置没有结束(fasle),那么找到的app并不能算作一个单词或者完整的字符串与app对应,不应该算找到。方法search相较于上面多判断了查找这个节点是否成功,且是否有结束标记,全部满足后,才将成功结果返回。
然后我们说一下插入功能
和查询一样建立查询然后将单词拆开来问节点,节点是否在子节点中存在不存在就新建一个,先创建一个新的TrieNode对象,添加到当前节点的子节点列表中(也就是加了一个分支)。
这里的put方法是将这里new的空对象和对应的字符作为children添加到本节点里面也就是这儿。
结束值还是空的,就这样添加一个节点,简单结束这次循环。
最后用get方法,将节点移步到下一层,即刚才建立好的新路径,一直往复下去,直到单词已经全部写入,判断不支持运行,循环结束了,将最后一个位置用setEnd打上结束标记,完成这次写入。
那,到这里已经解释完了一次简单的构建和添加,可能有点瑕疵,欢迎指正。