引入背景
字典树，也称为前缀树或Trie树，是一种基于字符串的高效数据结构。它常用于存储大量的字符串，并支持快速的查找操作。例如，在搜索引擎中，我们可以通过字典树来实现自动补全功能。通过使用字典树，可以显著提高字符串搜索的效率。
字典树的基本概念
节点结构
字典树中的每个节点通常包括一个指向子节点的指针数组，以及一个布尔值用来标识该节点是否是一个单词的结尾。对于英文字母，这个数组的大小通常是26。每个节点代表一个字符，而从根节点到某个节点的所有路径则代表一个字符串。
插入操作
插入一个新单词到字典树中时，我们需要遍历单词中的每个字符，根据字符在字母表中的位置找到对应的子节点。如果子节点不存在，则需要创建一个新的子节点。最后到达单词的最后一个字符时，将该节点标记为结束节点。
查找操作
查找一个单词时，我们同样需要遍历单词中的每个字符，根据字符找到对应的子节点。如果在某个字符处找不到对应的子节点，则说明该单词不在字典树中。如果遍历完整个单词并且最后一个字符对应的节点被标记为结束节点，则说明该单词存在于字典树中。
实现字典树的步骤
步骤一：定义节点类
首先，我们需要定义一个节点类来表示字典树中的每个节点。这个类应该至少包含一个指向子节点的数组和一个布尔值，用来表示该节点是否是单词的结尾。
class TrieNode {
constructor() {
this.children = new Array(26).fill(null);
this.isEndOfWord = false;
}
}步骤二：定义字典树类
接下来，我们需要定义一个字典树类，用于管理所有的节点。这个类应该提供插入、查找等基本操作。
// www.javascriptcn.com code example
class Trie {
constructor() {
this.root = new TrieNode();
}
// 插入单词到字典树中
insert(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
const charIndex = word.charCodeAt(i) - 'a'.charCodeAt(0);
if (!node.children[charIndex]) {
node.children[charIndex] = new TrieNode();
}
node = node.children[charIndex];
}
node.isEndOfWord = true;
}
// 检查单词是否存在于字典树中
search(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
const charIndex = word.charCodeAt(i) - 'a'.charCodeAt(0);
if (!node.children[charIndex]) {
return false;
}
node = node.children[charIndex];
}
return node.isEndOfWord;
}
}步骤三：测试
为了验证我们的实现是否正确，我们可以创建一些测试用例来检查插入和查找功能。
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // 应输出 true
console.log(trie.search("app")); // 应输出 false
console.log(trie.startsWith("app")); // 应输出 true
trie.insert("app");
console.log(trie.search("app")); // 应输出 true扩展功能
自动补全功能
字典树非常适合实现自动补全功能。当用户输入部分文本时，我们可以遍历字典树，找到所有以该文本为前缀的单词。
// www.javascriptcn.com code example
class Trie {
// ...（之前的代码不变）
// 获取所有以给定前缀开头的单词
getAllWordsWithPrefix(prefix) {
const results = [];
function dfs(node, currentWord) {
if (node.isEndOfWord) {
results.push(currentWord);
}
for (let i = 0; i < 26; i++) {
if (node.children[i]) {
dfs(node.children[i], currentWord + String.fromCharCode('a'.charCodeAt(0) + i));
}
}
}
let currentNode = this.root;
for (let i = 0; i < prefix.length; i++) {
const charIndex = prefix.charCodeAt(i) - 'a'.charCodeAt(0);
if (!currentNode.children[charIndex]) {
return results; // 如果前缀不存在，则返回空结果
}
currentNode = currentNode.children[charIndex];
}
dfs(currentNode, prefix);
return results;
}
}
// 使用示例
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("banana");
console.log(trie.getAllWordsWithPrefix("ap")); // 输出 ["apple", "app"]删除单词
除了插入和查找之外，我们还可以实现删除单词的功能。这要求我们在删除一个单词时，不仅要标记该单词不再存在，还需要处理可能产生的空子树。
// www.javascriptcn.com code example
class Trie {
// ...（之前的代码不变）
// 删除指定单词
delete(word) {
function dfs(node, index) {
if (index === word.length) {
node.isEndOfWord = false;
return node.children.every(child => child === null);
}
const charIndex = word.charCodeAt(index) - 'a'.charCodeAt(0);
if (node.children[charIndex]) {
const shouldDeleteCurrentNode = dfs(node.children[charIndex], index + 1);
if (shouldDeleteCurrentNode) {
node.children[charIndex] = null;
}
return node.children.every(child => child === null);
}
return false;
}
dfs(this.root, 0);
}
}
// 使用示例
const trie = new Trie();
trie.insert("apple");
trie.delete("apple");
console.log(trie.search("apple")); // 输出 false总结
通过上述步骤，我们成功地实现了字典树的基本功能，并且扩展了一些实用的功能如自动补全和删除操作。字典树是一种非常高效的数据结构，尤其适用于处理大量字符串的情况。希望这篇教程能够帮助大家更好地理解和应用字典树。