为什么数据结构与算法对前端开发很重要

从一个需求谈起

```var data = [{
"value": "浙江",
"children": [{
"value": "杭州",
"children": [{
"value": "西湖"
}]
}]
}, {
"value": "四川",
"children": [{
"value": "成都",
"children": [{
"value": "锦里"
}, {
"value": "方所"
}]
}, {
"value": "阿坝",
"children": [{
"value": "九寨沟"
}]
}]
}]```

```var data = [{
"province": "浙江",
"city": "杭州",
"name": "西湖"
}, {
"province": "四川",
"city": "成都",
"name": "锦里"
}, {
"province": "四川",
"city": "成都",
"name": "方所"
}, {
"province": "四川",
"city": "阿坝",
"name": "九寨沟"
}]```

```'use strict'

/**
* 将一个没有层级的扁平对象,转换为树形结构({value, children})结构的对象
* @param {array} tableData - 一个由对象构成的数组,里面的对象都是扁平的
* @param {array} route - 一个由字符串构成的数组,字符串为前一数组中对象的key,最终
* 输出的对象层级顺序为keys中字符串key的顺序
* @return {array} 保存具有树形结构的对象
*/

var transObject = function(tableData, keys) {
let hashTable = {}, res = []
for( let i = 0; i < tableData.length; i++ ) {
if(!hashTable[tableData[i][keys[0]]]) {
let len = res.push({
value: tableData[i][keys[0]],
children: []
})
// 在这里要保存key对应的数组序号,不然还要涉及到查找
hashTable[tableData[i][keys[0]]] = { \$\$pos: len - 1 }
}
if(!hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]]) {
let len = res[hashTable[tableData[i][keys[0]]].\$\$pos].children.push({
value: tableData[i][keys[1]],
children: []
})
hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]] = { \$\$pos: len - 1 }
}
res[hashTable[tableData[i][keys[0]]].\$\$pos].children[hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]].\$\$pos].children.push({
value: tableData[i][keys[2]]
})
}
return res
}

var data = [{
"province": "浙江",
"city": "杭州",
"name": "西湖"
}, {
"province": "四川",
"city": "成都",
"name": "锦里"
}, {
"province": "四川",
"city": "成都",
"name": "方所"
}, {
"province": "四川",
"city": "阿坝",
"name": "九寨沟"
}]

var keys = ['province', 'city', 'name']

console.log(transObject(data, keys))```

```var transObject = function(tableData, keys) {
let hashTable = {}, res = []
for (let i = 0; i < tableData.length; i++) {
let arr = res, cur = hashTable
for (let j = 0; j < keys.length; j++) {
let key = keys[j], filed = tableData[i][key]
if (!cur[filed]) {
let pusher = {
value: filed
}, tmp
if (j !== (keys.length - 1)) {
tmp = []
pusher.children = tmp
}
cur[filed] = { \$\$pos: arr.push(pusher) - 1 }
cur = cur[filed]
arr = tmp
} else {
cur = cur[filed]
arr = arr[cur.\$\$pos].children
}
}
}
return res
}```

Trie树

Trie 这个名字取自“retrieval”，检索，因为 Trie 可以只用一个前缀便可以在一部字典中找到想要的单词。 虽然发音与「Tree」一致，但为了将这种 字典树 与 普通二叉树 以示区别，程序员小吴一般读「Trie」尾部会重读一声，可以理解为读「TreeE」。

Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

Trie树的特点

Trie树样子

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同

Trie 树构造

Trie树的插入操作

Trie树的插入操作

Trie树的插入操作很简单，其实就是将单词的每个字母逐一插入 Trie树。插入前先看字母对应的节点是否存在，存在则共享该节点，不存在则创建对应的节点。比如要插入新单词`cook`，就有下面几步：

• 插入第一个字母 `c`，发现 `root` 节点下方存在子节点 `c`，则共享节点 `c`
• 插入第二个字母 `o`，发现 `c` 节点下方存在子节点 `o`，则共享节点 `o`
• 插入第三个字母 `o`，发现 `o` 节点下方不存在子节点 `o`，则创建子节点 `o`
• 插入第三个字母 `k`，发现 `o` 节点下方不存在子节点 `k`，则创建子节点 `k`
• 至此，单词 `cook` 中所有字母已被插入 Trie树 中，然后设置节点 `k` 中的标志位，标记路径 `root->c->o->o->k`这条路径上所有节点的字符可以组成一个单词`cook`

code的匹配路径

cod的匹配路径

Trie树的删除操作

Trie树的删除操作与二叉树的删除操作有类似的地方，需要考虑删除的节点所处的位置，这里分三种情况进行分析：

删除整个单词（比如 hi ）

• 从根节点开始查找第一个字符`h`
• 找到`h`子节点后，继续查找`h`的下一个子节点`i`
• `i`是单词`hi`的标志位，将该标志位去掉
• `i`节点是`hi`的叶子节点，将其删除
• 删除后发现`h`节点为叶子节点，并且不是单词标志位，也将其删除
• 这样就完成了`hi`单词的删除操作

Trie树的应用

1. 前缀匹配

trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能

2. 字符串检索

• 如果沿路比较，发现不同的字符，则表示该字符串在集合中不存在。
• 如果所有的字符全部比较完并且全部相同，还需判断最后一个节点的标志位（标记该节点是否代表一个关键字）。

Trie树的局限性

LeetCode 第 208 号问题就是 实现 Trie (前缀树)，感兴趣的小伙伴可以去实操一下。

References

`[1]` 从一个需求谈起: https://github.com/LeuisKen/leuisken.github.io/issues/2

301 篇文章61 人订阅

0 条评论