Trie

概念

在计算机科学，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。

简单点来说，这个结构的作用大多是为了方便搜索字符串，该树有以下几个特点

  • 根节点代表空字符串，每个节点都有 N（假如搜索英文字符，就有 26 条） 条链接，每条链接代表一个字符
  • 节点不存储字符，只有路径才存储，这点和其他的树结构不同
  • 从根节点开始到任意一个节点，将沿途经过的字符连接起来就是该节点对应的字符串

Trie - 图1、

实现

总得来说 Trie 的实现相比别的树结构来说简单的很多，实现就以搜索英文字符为例。

  1. class TrieNode {
  2.   constructor() {
  3.     // 代表每个字符经过节点的次数
  4.     this.path = 0
  5.     // 代表到该节点的字符串有几个
  6.     this.end = 0
  7.     // 链接
  8.     this.next = new Array(26).fill(null)
  9.   }
  10. }
  11. class Trie {
  12.   constructor() {
  13.     // 根节点，代表空字符
  14.     this.root = new TrieNode()
  15.   }
  16.   // 插入字符串
  17.   insert(str) {
  18.     if (!str) return
  19.     let node = this.root
  20.     for (let i = 0; i < str.length; i++) {
  21.       // 获得字符先对应的索引
  22.       let index = str[i].charCodeAt() - 'a'.charCodeAt()
  23.       // 如果索引对应没有值，就创建
  24.       if (!node.next[index]) {
  25.         node.next[index] = new TrieNode()
  26.       }
  27.       node.path += 1
  28.       node = node.next[index]
  29.     }
  30.     node.end += 1
  31.   }
  32.   // 搜索字符串出现的次数
  33.   search(str) {
  34.     if (!str) return
  35.     let node = this.root
  36.     for (let i = 0; i < str.length; i++) {
  37.       let index = str[i].charCodeAt() - 'a'.charCodeAt()
  38.       // 如果索引对应没有值，代表没有需要搜素的字符串
  39.       if (!node.next[index]) {
  40.         return 0
  41.       }
  42.       node = node.next[index]
  43.     }
  44.     return node.end
  45.   }
  46.   // 删除字符串
  47.   delete(str) {
  48.     if (!this.search(str)) return
  49.     let node = this.root
  50.     for (let i = 0; i < str.length; i++) {
  51.       let index = str[i].charCodeAt() - 'a'.charCodeAt()
  52.       // 如果索引对应的节点的 Path 为 0，代表经过该节点的字符串
  53.       // 已经一个，直接删除即可
  54.       if (--node.next[index].path == 0) {
  55.         node.next[index] = null
  56.         return
  57.       }
  58.       node = node.next[index]
  59.     }
  60.     node.end -= 1
  61.   }
  62. }