技术分享08 - 前缀树
背景 - 搜索引擎关键字提示
搜索关键字智能提示是一个搜索应用的标配，主要作用是避免用户输入错误的搜索词，将用户引导到相应的关键词上，以提升用户搜索体验。
前缀匹配原则
例如：在搜索框中输入“海底”，搜索框下面会以海底为前缀，展示“海底捞”、“海底捞火锅”、“海底世界”等等搜索词；输入“万达”，会提示“万达影城”、“万达广场”、“万达百货”等搜索词。
Trie树
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。
例如，给出一组单词——重庆鸡公煲、重庆火锅、重庆小天鹅、海底捞、海底世界、海洋公园，我们可以得到下面的Trie：
从上图可知，当用户输入前缀”重庆“的时候，搜索框可能会展示以”重庆“为前缀的“重庆鸡公煲”、“重庆火锅”、”重庆小天鹅”等关键词，再当用户输入前缀”海底“的时候，搜索框里面可能会提示以”海底“为前缀的“海底捞”、”海底世界“等关键词。
基本性质
- 根节点不包含字符，除根节点意外每个节点只包含一个字符。
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符串不相同。
应用
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
优点
可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。
跟哈希表比较：
- 最坏情况时间复杂度比hash表好
- 没有冲突，除非一个key对应多个值（除key外的其他信息）
- 可以自带排序功能，中序遍历trie就可以得到排序
缺点
- Trie其实是一个以空间换时间的算法
- 如果数据存储在外部存储器等较慢位置，Trie会较hash速度慢（hash访问O(1)次外存，Trie访问O(树高)）
实现
class TrieNode {
constructor(value) {
this.value = value; // value 为单个字符
this.children = [];
this.isEnd = false; // 是否为字符串的结尾结点
}
/**
* @description: 根据字符，寻找结点
* @param {Char} val 要查找的字符
* @return {TrieNode | null} 找到的结点 ｜ null
*/
findNode(val) {
for (const child of this.children) {
if (child.value === val) return child;
}
return null;
}
}
class Trie {
constructor() {
this.root = new TrieNode(''); // Trie 树的根结点
}
insert(str) {
let node = this.root;
for (const c of str) {
let findNode = node.findNode(c);
// 当当前字符没有对应子结点时，创建一个节点，并作为当前结点的子结点
if (findNode === null) {
findNode = new TrieNode(c);
node.children.push(findNode);
}
node = findNode;
}
// 遍历字符串结束，标记当前结点为结尾结点
if (!node.isEnd) node.isEnd = true;
}
search(str) {
let node = this.root;
for (const c of str) {
const findNode = node.findNode(c);
if (findNode === null) return []; // 没找到
else node = findNode;
}
let res = []; // 包含前缀为 str 的所有字符串的数组
let track = str; // 回溯的路径
backtrack(track, node);
return res;
/**
* @description: 回溯遍历返回所有前缀为 str 的字符串
* @param {String} track 前缀为 str 的字符串
* @param {TrieNode} node 要遍历的结点
* @return {void}
*/
function backtrack(track, node) {
// 结果只包含“海洋公园”
if (node.children.length === 0) {
res.push(track);
return;
}
// // 结果包含“海洋”和“海洋公园”
// if (node.isEnd) {
// res.push(track);
// if (node.children.length === 0)
// return;
// }
node.children.forEach(child => {
track += child.value;
backtrack(track, child);
track = track.slice(0, -1);
})
}
}
}
const trie = new Trie();
trie.insert('重庆鸡公煲');
trie.insert('重庆火锅');
trie.insert('重庆小天鹅');
trie.insert('海底捞');
trie.insert('海底捞火锅');
trie.insert('海底世界');
trie.insert('海洋');
trie.insert('海洋公园');
console.log('搜索【重庆】的结果：', trie.search('重庆'));
console.log('搜索【海】的结果：', trie.search('海'));
console.log('搜索【火锅】的结果：', trie.search('火锅'));进阶练习
211. 添加与搜索单词 - 数据结构设计 ｜ Leetcode