前言
继二叉树、堆之后，接下来介绍另外一种树型的数据结构 -Trie树，也能够叫它前缀树、字典树。例如咱们再搜索引擎里输出几个关键字之后，后续的内容会主动续上。此时咱们输出的关键词也就是前缀，而前面的就是与之匹配的内容，而这么一个性能底层的数据结构就是 Trie 树。那到底什么是 Trie 树？还是三个步骤来相熟它，首先理解、而后实现、最初利用。
什么是 Trie 树？
这是一种多叉树，它次要解决的问题是能在一组字符串里疾速的进行某个字符串的匹配。而它的这种高效正是建设在算法的以空间换工夫的思维上，因为字符串的每一个字符都会成为一个树的节点，例如咱们把这样一组单词 ['bag', 'and', 'banana', 'ban', 'am', 'board', 'ball'] 进行 Trie 化后就会成为以下这样：
根节点为空，因为子节点都的存储的单词结尾的缘故。Trie树的实质就是将 单词之间的公共前缀合并起来 ，这也就会造成单词ban 和banana专用同一条门路，所以须要在单词的结尾处给一个标识符，示意该字符为一个单词的完结。所以当输出关键词 ba 后，只须要遍历前面的节点就能够将 bag、banana、ball 单词出现给用户。是不是很酷~
从零实现一颗 Trie 树
之前咱们介绍的都是二叉树，所以应用左右孩子示意这个很不便，但 Trie 树是一种多叉树，如果仅仅只是存储小写字母，那么每个父节点的子节点最多就有 26 个子孩子。所以子节点咱们都应用单个字符作为其 key 来存储，这样无论多少个子节点都没问题。Trie次要是操作就是两个，一个是往树里增加单词、另一个是查问树里是否有某个单词。
class Node { // 节点类
constructor(isWord = false) {
this.isWord = isWord // 该节点是否是单词的结尾
this.next = new Map() // 子孩子应用 map 存储}
}
class Trie { // 实例类
constructor() {this.root = new Node()
}
...
}往 Trie 里减少单词(add)
将单词拆解为单个的字符，而每个字符就是一个 Node 类的实例，最初当单词达到开端时，将最初字符 Node 节点的 isWord 属性设置为 true 即可。
class Trie {
...
add(word) { // 之后的利用里有遍历的写法
const _helper = (node, word) => {if (word === '') { // 递归到底，单词曾经不能被拆解了
node.isWord = true // 将上一个字符标记为单词结尾
return
}
const c = word[0] // 从单词的首字母开始
if (!node.next.has(c)) { // 如果孩子节点里不蕴含该字符
node.next.set(c, new Node()) // 设置为新的孩子节点
}
_helper(node.next.get(c), word.slice(1)) // 持续拆解单词的其余字符
}
_helper(this.root, word) // 退出到根节点之下
}
}通过 add 办法，就能够构建一颗 Trie 树了，但构建它最大的意义是能疾速的进行查问，所以咱们还须要一个 search 办法，能疾速的查问该单词是否在 Trie 树里。
查问 Trie 里的单词(search)
因为曾经有一颗 Trie 树了，所以要查问也很简略，只须要将要查问的单词合成为字符逐层向下的和 Trie 树节点进行匹配即可，只有有一个节点 Trie 树里没有，就能够判断 Trie 树不存在这个单词，单词合成结束之后，返回最初停留那个节点的 isWord 属性即可。
class Trie {search(word) {const _helper = (node, word) => {if (word === '') { // 曾经不能拆解了
return node.isWord // 返回停留节点的 isWord 属性
}
const c = word[0]
if (!node.next.get(c)) { // 只有有节点不匹配
return false // 示意没有
}
return _helper(node.next.get(c), word.slice(1)) // 逐层向下
}
return _helper(this.root, word) // 从根节点开始
}
}输入 Trie 树里的每个单词(log)
这个办法仅仅是集体在相熟 Trie 树时增加一个办法，每次调用打印出树里所有的单词，不便调试时应用。
class Trie {
...
log() { // 根之前的打印匹配的前缀相似，只须要调整
const ret = []
const _helper = (node, path) => {if (node.isWord) {ret.push(path.join('')) // 将单词放入后果里
}
for (const [key, value] of node.next) { // 遍历每一个孩子节点
path.push(key) // 退出单词门路
_helper(value, path)
path.pop() // 回溯}
}
_helper(this.root, [])
console.log(ret)
}
}返回前缀匹配的单词
这个办法纯正也是集体所加，很多介绍介绍 Trie 树的材料不会写这个办法，集体感觉这是很能联合 Trie 树个性的一个办法，因为仅仅作为准确查问来说，还真没比哈希表、红黑树劣势多少。但如果只是返回匹配前缀的单词，这个劣势就很大了。像输入法的主动联想、IDE的主动补全性能都能够用这个办法实现。
class Trie {
...
match(prefix) {if (prefix === '') {return []
}
let cur = this.root
for (let i = 0; i < prefix.length; i++) { // 首先找到前缀停留的节点
const c = prefix[i]
if (!cur.next.get(c)) { // 前缀都不匹配，那必定没这单词了
return []}
cur = cur.next.get(c) // cur 就是停留的节点
}
const ret = []
const _helper = (node, path) => {if (node.isWord) { // 如果是一个单词
ret.push(prefix + path) // 将其增加到返回后果里
}
for (const [key, value] of node.next) {
path += key // 记录匹配的门路
_helper(value, path) // 递归向下查找
path = path.slice(0, -1) // 回溯
}
}
_helper(cur, '') // 从 cur 开始向下匹配
return ret // 返回后果
}
}Trie 树的利用
首先利用尝试一下上述咱们实现的这个 Trie 类：
const trie = new Trie();
const words = ['bag', 'and', 'banana', 'an', 'am', 'board', 'ball'];
words.forEach(word => {trie.add(word); // 构建 Trie 树
});
trie.log() // 打印所有单词
console.log(trie.match('ba')) // ['bag', 'banana', 'ball']学习 Trie 树最重要就是学习它解决问题的思维，接下来咱们拿力扣几道字典树相干的问题，来看看如果奇妙的应用 Trie 树思维解答它们。
720 – 词典中最长的单词 ↓
给出一个字符串数组 words 组成的一本英语词典。从中找出最长的一个单词，该单词是由 words 词典中其余单词逐渐增加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。示例
输出：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输入："apple"
解释："apply" 和 "apple" 都能由词典中的单词组成。然而 "apple" 的字典序小于 "apply"。简略来说就是找到最长的单词，但这个单词必须是其余的单词一步步累加起来的，所以不能呈现跨级跳跃的状况。思路就是咱们把这个字典转化为一个 Trie 树，在树里给每个单词做好完结的标记，只能是单词的能力往下进行匹配，所以进行深度优先遍历，但其中只有有一个字符不是单词，就完结这条路接下来的遍历，最初返回匹配到最长的单词长度即可。这个字典转化为 Trie 树后如下图：
很显著 banana 间接淘汰，因为这个字符串的第一个字符就不是一个单词，而最初角逐的就是 apply 和apple，因为这两个单词一路都是踏着其余单词而来。实现代码如下：
class Node {constructor(isWord) {
this.isWord = isWord
this.next = new Map()}
}
class Trie {constructor() {this.root = new Node()
}
add(word) { // 构建树
const _helper = (node, word) => {if (word === '') {
node.isWord = true
return
}
const c = word[0]
if (!node.next.get(c)) {node.next.set(c, new Node())
}
_helper(node.next.get(c), word.slice(1))
}
_helper(this.root, word)
}
}
var longestWord = function (words) {const trie = new Trie()
words.forEach(word => { // 将字符汇合构建为 trie 树
trie.add(word)
})
let res = '' // 保留最长单词
const _helper = (node, path) => {if (path.length > res.length || (path.length === res.length && res > path)) {
res = path
// 只有匹配到单词长度大于已存单词长度 或者 相等时取小的那位
// 更新最长单词
}
for (const [key, value] of node.next) { // 遍历多叉树
if (!value.isWord) { // 只有这个节点不是单词结尾，就略过
continue
}
path += key // 将这个单词退出到门路里
_helper(value, path) // 持续向下匹配
path = path.slice(0, -1) // 遍历完一个分支后，减去这个分支字符
}
}
_helper(trie.root, '')
return res // 返回最长单词
};677 – 键值映射 ↓
实现一个 MapSum 类里的两个办法，insert 和 sum。对于办法 insert，你将失去一对（字符串，整数）的键值对。字符串示意键，整数示意值。如果键曾经存在，那么原来的键值对将被代替成新的键值对。对于办法 sum，你将失去一个示意前缀的字符串，你须要返回所有以该前缀结尾的键的值的总和。示例：输出: insert("apple", 3), 输入: Null
输出: sum("ap"), 输入: 3
输出: insert("app", 2), 输入: Null
输出: sum("ap"), 输入: 5简略来说就是首先输出一些单词以及对应的权重，而后再输出前缀之后，把每个匹配的单词的权重值累加即可。这次的解题思路就和之前 match 办法很像，咱们把 insert 的单词放入一颗 Trie 树里，单词结尾也就是该单词对应的权重值。所以首先定位前缀最初停留的节点，而后遍历的把之后的节点都遍历一遍，累加其权重值即可。代码如下：
class Node { // 节点类
constructor(val = 0) {
this.val = val // 权重值，默认为 0
this.next = new Map()}
}
var MapSum = function () { // 题目须要的类
this.root = new Node()};
MapSum.prototype.insert = function (key, val) {
let cur = this.root
for (let i = 0; i < key.length; i++) {const c = key[i]
if (!cur.next.get(c)) {cur.next.set(c, new Node())
}
cur = cur.next.get(c)
}
cur.val = val
};
MapSum.prototype.sum = function (prefix) {
let cur = this.root
for (let i = 0; i < prefix.length; i++) {const c = prefix[i]
if (!cur.next.get(c)) { // 前缀都不匹配，间接返回 0
return 0
}
cur = cur.next.get(c) // 前缀匹配完了之后，cur 就是停留的节点
}
let res = 0 // 总权重值
const _helper = node => {
res += node.val
// 遍历 cur 之后的每一个节点即可，因为不是单词的权重值为 0
for (const item of node.next) {_helper(item[1])
}
}
_helper(cur)
return res
};648 – 单词替换 ↓
在英语中，咱们有一个叫做 词根 (root) 的概念，它能够跟着其余一些词组成另一个较长的单词——
咱们称这个词为 继承词(successor)。例如，词根 an，跟随着单词 other(其余)，能够造成新的单词 another(另一个)。当初，给定一个由许多词根组成的词典和一个句子。你须要将句子中的所有继承词用词根替换掉。如果继承词有许多能够造成它的词根，则用最短的词根替换它。你须要输入替换之后的句子。示例 1：输出：dictionary = ["cat","bat","rat"],
sentence = "the cattle was rattled by the battery"
输入："the cat was rat by the bat"
示例 2：输出：dictionary = ["a","b","c"],
sentence = "aadsfasf absbs bbab cadsfafs"
输入："a a b c"思路咱们还是应用 Trie 树，将所有的前缀 (词根) 构建为一颗 Trie 树，而后遍历的把每个单词与这颗前缀树进行匹配，当前缀树达到结尾时，就把原来字符串换为该词根即可。如图所示：
代码如下：
class Node {constructor(idWord = false) {
this.isWord = idWord
this.next = new Map()}
}
class Trie {constructor() {this.root = new Node()
}
add(word) {const _helper = (node, word) => {if (word === '') {
node.isWord = true
return
}
const c = word[0]
if (!node.next.get(c)) {node.next.set(c, new Node())
}
_helper(node.next.get(c), word.slice(1))
}
_helper(this.root, word)
}
change(words) {for (let i = 0; i < words.length; i++) {const word = words[i]
let cur = this.root
let dict = ''
for (let j = 0; j < word.length; j++) {const c = word[j] // 遍历每个单词的每个字符
if (cur.next.get(c)) { // 如果单词有匹配的词根
dict += c // 记录遍历的词根
cur = cur.next.get(c) // 向下遍历
if (cur.isWord) { // 当词根到底时
words[i] = dict // 将记录的词根替换掉单词
break // 不必再遍历单词之后的字符了
}
} else {break // 如果没有匹配的词根，间接换下一个单词}
}
}
return words.join(' ') // 返回新的字符串
}
}
var replaceWords = function (dictionary, sentence) {const trie = new Trie()
dictionary.forEach(dict => {trie.add(dict) // 构建树
})
return trie.change(sentence.split(' ')) // 将单词拆分
};这题转换的 Trie 树就是三条独立的分支，如果 Trie 树长这样，其实就齐全没必要应用 Trie 树，所以这也是应用 Trie 树的场景局限性。
最初
通过上述实现与利用，置信大家曾经对 Trie 有了足够的理解，这是一种十分优良的解决问题的思维，场景应用得过后，能施展出微小的劣势。如果场景不合乎，那就尽量不应用这种数据结构吧。因为 … 咱们来总结下这种数据结构的优缺点：
长处
- 性能高效，从任意多的字符串中匹配某一个单词的工夫复杂度，最多仅为该单词的长度而已。
- 前缀匹配，像搜寻及
IDE主动补全的场景，应用Trie树就非常适合。
毛病
- 对数据要求严苛，如果字符汇合公共的前缀并不多时
(第三题就是这个状况)，体现并不好。因为每个节点不仅仅能够存储小写字母，还包含大写字母、数字等，这样的话，一颗Trie树就会异样宏大，会十分耗费内存。 JavaScript没有现成的类应用，要本人手写且要保障没bug，麻烦。
本章 github 源码