2.3 Trie 树

• 2.3.1 前缀树的实现

在计算机科学，Trie，又称 前缀树 或 字典树，是 N叉树的一种特殊形式。

特点：

1. 根节点就是一个空字符串
2. 节点不存储字符，只有路径上才存储
3. 从根节点开始到任意一个节点，将沿途经过的字符连接起来就是该节点对应的字符串

字符：apple，app，cat，cap

2.3.1 前缀树的实现 (opens new window)

class TrieNode {
  constructor() {
    // 代表当前节点的处于第几层
    this.path = 0;
    // 代表当前节点结束位置
    this.end = 0;
    // 存储字母的容器
    this.next = new Array(26).fill(null);
  }
}

const Trie = function() {
    this.root = new TrieNode();
};

Trie.prototype.insert = function(word) {
    if (!word) return;
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      // 获得字符先对应的索引
      let index = word[i].charCodeAt() - 'a'.charCodeAt();
      // 如果索引对应没有值，就创建
      if (!node.next[index]) {
        node.next[index] = new TrieNode();
      }
      node.path += 1;
      node = node.next[index];
    }
    node.end += 1;
};

Trie.prototype.search = function(word) {
    if (!word) return;
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      let index = word[i].charCodeAt() - 'a'.charCodeAt();
      // 如果索引对应没有值，代表没有需要搜素的字符串
      if (!node.next[index]) {
        return 0;
      }
      node = node.next[index];
    }
    return node.end;
};

Trie.prototype.startsWith = function(prefix) {
    if (!prefix) return;
    let node = this.root;
    for (let i = 0; i < prefix.length; i++) {
        let index = prefix[i].charCodeAt() - 'a'.charCodeAt();
        if (!node.next[index]) {
            return 0;
        }
        node = node.next[index];
    }
    return 1;
};

前缀树的应用场景： 自动补全

前缀树的局限性：Trie 树的核心思想是空间换时间