写在前面的话：设想一种场景，某个电商平台，随着功能版本的迭代更新，单个界面的请求越来越多，用户体验和性能越来越差，顺着减少接口请求的思路，例如使用纯前端而不通过接口请求的方式维护用户对商品的搜索历史记录列表，你来做的话，如何实现? 下面我提供其中一种解决思路
导读: 字典树（Trie）是针对特定类型的搜索而优化的树数据结构。典型的例子是 AutoComplete（自动填充），也就是说它适合实现“通过部分值得到完整值”的场景。因此字典树也是一种搜索树，我们有时候也叫作前缀树，因为任意一个节点的后代都存在共同的前缀。
字典树的特点如下：
字典树能做到高效查询和插入，时间复杂度为 O(k)，k 为字符串长度；
但是如果大量字符串没有共同前缀，就很耗内存，你可以想象一下最极端的情况，所有单词都没有共同前缀时，这颗字典树会是什么样子；
字典树的核心就是减少不必要的字符比较，提高查询效率，也就是说用空间换时间，再利用共同前缀来提高查询效率。
典型应用场景:
除了我们刚刚提到的 AutoComplete 自动填充的情况，字典树还有很多其他应用场景：
- 搜索
- 分类
- IP 地址检索
- 电话号码检索
如何实现?
首先实现一个字典树上的节点, 每一个字典树同时也是一个节点
一个字典树节点的诞生：
class PrefixNodeTree {
constructor(value) {
this.value = value
this.children = {}
this.isEnd = null
}
}
一个字典树也是一个节点：
class PrefixTree extends PrefixNodeTree {
constructor(){
super(null)
}
}
给树添加树枝：
conditionCheck(node, str){
if(!node) {
throw new Error('还没有创建节点!')
return
}
if(!str) {
throw new Error('字符串不得为空!')
return
}
if(!(Object.prototype.toString.call('str') === '[object String]')) {
throw new Error('不是一个字符串!')
return
}
return true
}
addWord(str) {
// 递归调用addWordHelper方法添加/保存字符串到字典树中
const addWordHelper = (node, str) => {
// 边界条件检查
const checkResult = this.conditionCheck(node, str)
if(!checkResult) return
if (!node.children[str[0]]) { // 字典树已存在该字符例如“s”对应的节点
node.children[str[0]] = new PrefixNodeTree(str[0]);
if (str.length === 1) { // 标记一个完整的字符串例如“some”已经录入成功
node.children[str[0]].isEnd = true;
} else {
// 递归录入
str.length >=2 && addWordHelper(node.children[str[0]], str.slice(1));
}
} else {
// 递归录入
if(str.length >=2) {
addWordHelper(node.children[str[0]], str.slice(1));
}else{
node.children[str[0]].isEnd = true;
}
}
};
addWordHelper(this, str);
}
现在我们已经有一棵字典树了，这棵字典树可以增加枝干，还不能查询，需要增加一个查询的方法
实际需求：查询用户对商品进行搜索的历史记录并最终展示出来
将需求抽象化提取出来：给定一个字符串，返回字典树中所有以该字符串开头的单词
具体实现如下：
思路分析：遍历该字典树，从上层节点开始匹配到完全符合单词的节点（此节点需要放到结果集中），再依次遍历匹配，收集匹配到的结果到结果集中，返回该结果集
步骤拆分：
步骤一： 遍历该字典树，从上层节点开始匹配到完全符合单词的节点
步骤二： 依次遍历匹配，收集匹配到的结果到结果集中，返回该结果集
selectWords(str) {
// 步骤一： 遍历该字典树，从上层节点开始匹配到完全符合单词的节点
// 找到str例如“some”对应的节点“e”
const getMatchedNode = (tree, str) => {
const checkResult = this.conditionCheck(tree, str)
if(!checkResult) return
let node = tree;
while (str.length && node) {
node = node.children[str[0]];
str = str.slice(1);
}
// 没有找到以str例如“some”开头的字符串
if (str.length) return null;
// 返回找到的节点“e”
return node;
};
const matchedNode = getMatchedNode(this, str);
console.log('matchedNode', matchedNode)
// 步骤二： 依次遍历匹配，收集匹配到的结果到结果集中，返回该结果集
const selectWordInner = (matchedNode, str, words = []) => {
const children = matchedNode.children;
Object.keys(children).forEach((key) => {
const newStr = str + children[key].value;
if (children[key].isEnd) {
words.push(newStr);
// 边界情况，查漏补缺
if(Object.keys(children[key].children).length){
selectWordInner(children[key], newStr, words);
}
} else {
// 深度遍历（DFS）递归调用进一步查找可能匹配到的字符串
selectWordInner(children[key], newStr, words);
}
});
return words;
};
if (matchedNode) {
return selectWordInner(matchedNode, str, matchedNode.isEnd ? [str] : []);
}
return [];
}
完整代码如下：
class PrefixNodeTree {
constructor(value) {
this.value = value
this.children = {}
this.isEnd = null
}
}
class PrefixTree extends PrefixNodeTree {
constructor() {
super(null)
}
conditionCheck(node, str) {
if (!node) {
throw new Error("还没有创建节点!")
return
}
if (!str) {
throw new Error("字符串不得为空!")
return
}
if (!(Object.prototype.toString.call("str") === "[object String]")) {
throw new Error("不是一个字符串!")
return
}
return true
}
addWord(str) {
const addWordHelper = (node, str) => {
const checkResult = this.conditionCheck(node, str)
if (!checkResult) return
if (!node.children[str[0]]) {
node.children[str[0]] = new PrefixNodeTree(str[0])
if (str.length === 1) {
node.children[str[0]].isEnd = true
} else {
str.length >= 2 && addWordHelper(node.children[str[0]], str.slice(1))
}
} else {
if (str.length >= 2) {
addWordHelper(node.children[str[0]], str.slice(1))
} else {
node.children[str[0]].isEnd = true
}
}
}
addWordHelper(this, str)
}
selectWords(str) {
const getMatchedNode = (tree, str) => {
const checkResult = this.conditionCheck(tree, str)
if (!checkResult) return
let node = tree
while (str.length && node) {
node = node.children[str[0]]
str = str.slice(1)
}
if (str.length) return null
return node
}
const matchedNode = getMatchedNode(this, str)
console.log("matchedNode", matchedNode)
const selectWordInner = (matchedNode, str, words = []) => {
const children = matchedNode.children
Object.keys(children).forEach((key) => {
const newStr = str + children[key].value
if (children[key].isEnd) {
words.push(newStr)
if (Object.keys(children[key].children).length) {
selectWordInner(children[key], newStr, words)
}
} else {
selectWordInner(children[key], newStr, words)
}
})
return words
}
if (matchedNode) {
return selectWordInner(matchedNode, str, matchedNode.isEnd ? [str] : [])
}
return []
}
}
测试1
let tree = new PrefixTree()
tree.addWord('some')
tree.addWord('someone')
tree.addWord('somebody')
tree.addWord('somespace')
tree.addWord('someway')
tree.addWord('somehow')
tree.addWord('somewhat')
tree.addWord('somelse')
tree.addWord('sometimes')
tree.addWord('something')
tree.addWord('somethingelse')
tree.addWord('somethingelseelse')
tree.addWord('solve')
let test = tree.selectWords('some')
console.log(test)
// ['some', 'someone', 'somebody', 'somespace', 'someway', 'somewhat', 'somehow', 'somelse', 'sometimes', 'something', 'somethingelse', 'somethingelseelse']
测试2
let tree2 = new PrefixTree()
tree2.addWord('some')
let test2 = tree2.selectWords('some')
console.log(test2)
// ['some']
完整实现思路：
用户第一次查询商品的时候，构建一棵上面这样的字典树，并同步存入/添加用户输入查询的字符串，同时把这颗字典树保存到locastorage中，可以以用户的id作为key来存储字典树，之后每一次查询在localstorage中更新字典树（调用addWord方法）。同时要同步渲染查询到的数据以展示用户搜索过的商品列表记录。
用户第N(N>1)次查询商品的时候, 从localstorage中查询到对应的字典树，然后调用addWord更新localstorage中的字典树。同时要同步渲染查询到的数据以展示用户搜索过的商品列表记录。
伪代码实现：
// 用户查询商品函数内部逻辑:
// 其中必要参数为查询的商品字符串
if(localstorage中有对应用户的商品查询字典树){
// 使用addWord方法更新localstorage中的字典树
// 使用selectWords方法查询相关（拥有相同前缀）的用户商品搜索历史记录数据
// 渲染展示对应的历史记录数据列表
}else{
// 新建一棵字典树，并调用addWord方法更新字典树, 将此字典树存储在localstorage中
}
写在最后
希望对你有所帮助或启发，这将是本篇文章最大的价值和意义所在！
