trie数据结构简介

trie，也称为前缀树，是一种高效的树状数据结构，用于存储和检索字符串。它对于涉及字符串搜索、前缀匹配和自动完成功能的任务特别有用。

发音：

• 这是一个单音节词
• 末尾的“ie”发音为长“e”音，类似于“see”或“tree”
• 它与“pie”或“die”不押韵 这种发音有助于将其与其他外观相似的单词区分开来，并强调其与数据检索操作的联系。

何时使用 trie

在您需要以下情况的情况下尝试是理想的选择：

1. 快速执行基于前缀的搜索
2. 实现自动完成功能
3. 存储单词词典以进行拼写检查
4. 高效存储和检索具有公共前缀的字符串 ## 可视化 trie

让我们想象一个包含单词“cat”、“car”和“dog”的特里树：

       root
     /   |   
    c    d    ...
   /     |
  a      o
 /      |
t   r    g

每个节点代表一个字符，从根节点到叶节点的路径组成完整的单词。

在 javascript 中实现 trie

让我们用 javascript 实现一个基本的 trie 结构：

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // Insert a word into the trie
  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  // Search for a word in the trie
  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  // Check if any word starts with the given prefix
  startsWith(prefix) {
    let node = this.root;
    for (let char of prefix) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

// Example usage
const trie = new Trie();

// Insert words
trie.insert("apple");
trie.insert("app");
trie.insert("banana");

console.log(trie.search("apple"));    // Output: true
console.log(trie.search("app"));      // Output: true
console.log(trie.search("appl"));     // Output: false
console.log(trie.startsWith("app"));  // Output: true
console.log(trie.startsWith("ban"));  // Output: true
console.log(trie.startsWith("cat"));  // Output: false

守则解释

1. class trienode：表示 trie 中的一个节点。每个节点都有：： 一个用于存储子节点的对象： 一个布尔标志，用于标记单词的结尾
2. class trie：主要的 trie 结构及其方法：
   • 插入：向特里树添加一个单词
   • 搜索：检查单词是否存在于 trie
   • startswith：检查 trie 中是否有任何单词以给定前缀开头
3. 该方法遍历 trie，为不存在的字符创建新节点，并将最后一个节点标记为单词的结尾。
4. 该方法沿着给定单词的路径遍历 trie，如果找到整个单词并将其标记为完整单词，则返回。
5. 该方法类似，但只检查给定的前缀是否存在于 trie 中，而不管它是否是一个完整的单词。

时间和空间复杂度

• 时间复杂度：
  • 插入：o(m)，其中 m 是单词的长度
  • 搜索：o(m)，其中 m 是单词的长度
  • startswith：o(m)，其中 m 是前缀的长度
• 空间复杂度：o(n * m)，其中n是单词数，m是单词的平均长度

tries 为字符串相关操作提供了出色的性能，特别是在处理大量具有公共前缀的单词时。它们提供快速查找和前缀匹配，这使得它们在自动完成系统、ip 路由表和字典实现等各种应用中具有无价的价值。

如果您喜欢本教程，请在此处关注我，并在 x/twitter 上关注我：@turckalicious。本文是在 wonderfall (https://wonderfall.xyz) 的帮助下完成的，这是一款人工智能驱动的交互式文档编辑器，可帮助您更快地研究、写作和迭代。