JavaScript中的数据结构与算法：图解Trie树

在计算机科学中，Trie树（也称为前缀树或字典树）是一种用于高效存储和检索字符串的数据结构。它能够在O(m)的时间复杂度内完成字符串的插入、查询和删除操作，其中m是待操作字符串的长度。Trie树在很多应用中都有广泛的应用，例如自动补全、拼写检查和IP路由表等。

本文将详细介绍Trie树的概念、构造方法以及常见操作，同时提供JavaScript代码实现。

Trie树的概念

Trie树是一种多叉树，每个节点代表一个字符，从根节点到叶子节点的路径构成一个字符串。根节点为空字符，每个节点可以有多个子节点，子节点代表从父节点出发的不同字符。另外，每个节点还可以存储一个标志位，用于表示该节点是否为一个完整的单词。

下图是一个简单的Trie树示例：

        root
       / | 
      a  b  c
     /   |   
    p    a    t
   /     |     
  p      t      s

在上面的示例中，Trie树存储了三个单词：app、apt和cats。根节点为空字符，从根节点到叶子节点的路径分别代表了这三个单词。

Trie树的构造

构造Trie树的基本步骤如下：

1. 创建根节点，并将其初始化为空字符。
2. 遍历待插入的字符串，对于每个字符执行以下操作：
   • 如果该字符在当前节点的子节点中存在，则将当前节点更新为该子节点。
   • 否则，创建一个新的节点，将该字符作为新节点的值，并将新节点添加到当前节点的子节点中。然后将当前节点更新为新节点。
3. 在最后一个字符所在的节点上设置标志位，表示该节点为一个完整的单词。

下面是JavaScript中构造Trie树的代码实现：

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

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

  insert(word) {
    let current = this.root;
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }
    current.isEndOfWord = true;
  }
}

Trie树的操作

Trie树支持以下几种常见操作：

• 插入：将一个字符串插入到Trie树中。
• 查询：判断一个字符串是否在Trie树中。
• 删除：从Trie树中删除一个字符串。

下面是JavaScript中Trie树的查询和删除操作的代码实现：

class Trie {
  // ... 省略构造函数和插入操作的代码 ...

  search(word) {
    let current = this.root;
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!current.children.has(char)) {
        return false;
      }
      current = current.children.get(char);
    }
    return current.isEndOfWord;
  }

  delete(word) {
    this._delete(this.root, word, 0);
  }

  _delete(node, word, index) {
    if (index === word.length) {
      if (!node.isEndOfWord) {
        return false;
      }
      node.isEndOfWord = false;
      return node.children.size === 0;
    }

    const char = word[index];
    if (!node.children.has(char)) {
      return false;
    }

    const childNode = node.children.get(char);
    const shouldDeleteChild = this._delete(childNode, word, index + 1);
    if (shouldDeleteChild) {
      node.children.delete(char);
      return node.children.size === 0;
    }

    return false;
  }
}

总结

Trie树是一种高效的数据结构，适用于存储和检索字符串。本文介绍了Trie树的概念、构造方法以及常见操作，并提供了JavaScript代码实现。希望通过本文的介绍，读者能够更好地理解和应用Trie树。

参考资料

• Trie树 - 维基百科