在计算机科学,trie
,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。
简单点来说,这个结构的作用大多是为了方便搜索字符串,该树有以下几个特点
总得来说 Trie 的实现相比别的树结构来说简单的很多,实现就以搜索英文字符为例。
class TrieNode { constructor() { // 代表每个字符经过节点的次数 this.path = 0 // 代表到该节点的字符串有几个 this.end = 0 // 链接 this.next = new Array(26).fill(null) } } class Trie { constructor() { // 根节点,代表空字符 this.root = new TrieNode() } // 插入字符串 insert(str) { if (!str) return let node = this.root for (let i = 0; i < str.length; i++) { // 获得字符先对应的索引 let index = str[i].charCodeAt() - 'a'.charCodeAt() // 如果索引对应没有值,就创建 if (!node.next[index]) { node.next[index] = new TrieNode() } node.path += 1 node = node.next[index] } node.end += 1 } // 搜索字符串出现的次数 search(str) { if (!str) return let node = this.root for (let i = 0; i < str.length; i++) { let index = str[i].charCodeAt() - 'a'.charCodeAt() // 如果索引对应没有值,代表没有需要搜素的字符串 if (!node.next[index]) { return 0 } node = node.next[index] } return node.end } // 删除字符串 delete(str) { if (!this.search(str)) return let node = this.root for (let i = 0; i < str.length; i++) { let index = str[i].charCodeAt() - 'a'.charCodeAt() // 如果索引对应的节点的 Path 为 0,代表经过该节点的字符串 // 已经一个,直接删除即可 if (--node.next[index].path == 0) { node.next[index] = null return } node = node.next[index] } node.end -= 1 } }
本文作者:毛超颖
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!