降维打击！为什么我认为数据结构与算法对前端开发很重要

川长思鸟来 2022-04-25 09:24 160阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

*事情要从 GitHub 上的一个 issue 谈起：**http**s://**github.com/LeuisK**en/leuisken.github.io/issues/2，需求里面的我指代为 issue 里面**的我**。*

### 从一个需求谈起 ###

在我之前的项目中，曾经遇到过这样一个需求，编写一个级联选择器，大概是这样：

![640?wx\_fmt=png][640_wx_fmt_png]

图中的示例使用的是 Ant-Design 的 Cascader 组件。

要实现这一功能，我需要类似这样的数据结构：

var data = [{  "value": "浙江",  "children": [{    "value": "杭州",    "children": [{      "value": "西湖"    }]  }]}, {  "value": "四川",  "children": [{    "value": "成都",    "children": [{      "value": "锦里"    }, {      "value": "方所"    }]  }, {    "value": "阿坝",    "children": [{      "value": "九寨沟"    }]  }]}]
      "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": "九寨沟"}]
      "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))
    
    /**
     * 将一个没有层级的扁平对象,转换为树形结构({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))

还好 keys 的长度只有 3 ，这种东西长了根本没办法写，很明显可以看出来这里面有重复的部分，可以通过循环搞定，但是想了很久都没有思路，就搁置了。

后来，有一天晚饭后不是很忙，就跟旁边做数据的同事聊了一下这个需求，请教一下该怎么用循环来处理。他看了一下，就问我：“你知道 trie 树吗？”。我头一次听到这个概念，他简单的给我讲了一下，然后说感觉处理的问题有些类似，让我可以研究一下 trie 树的原理并试着优化一下。

讲道理， trie 树这个数据结构网上确实有很多资料，但很少有使用 JavaScript 实现的，不过原理倒是不难。尝试之后，我就将 `transObject` 的代码优化成了这样。（关于 trie 树，还请读者自己阅读相关材料）

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}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
    }

这样，解决方案就和 keys 的长短无关了。

这种解决方案正如《三体》里面使用「二向箔」对宇宙文明进行降维打击一般干净利落！

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

如果你对「Trie」树的相关概念不了解的话，可以继续往下查看进行阅读学习。

> 这是之前的写的一篇旧文，小吴这里进行了一定的修改和排版。

### Trie树 ###

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

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

此外 Trie 树也称前缀树（因为某节点的后代存在共同的前缀，比如 pan 是 panda 的前缀）。

它的key都为字符串，能做到高效查询和插入，时间复杂度为 O(k)，k 为字符串长度，缺点是如果大量字符串没有共同前缀时很耗内存。

**它的核心思想就是通过最大限度地减少无谓的字符串比较，使得查询高效率，即「用空间换时间」，再利用共同前缀来提高查询效率。**

### Trie树的特点 ###

假设有 5 个字符串，它们分别是：code，cook，five，file，fat。现在需要在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 5 个字符串依次进行字符串匹配，那效率就比较低，有没有更高效的方法呢？

如果将这 5 个字符串组织成下图的结构，从肉眼上扫描过去感官上是不是比查找起来会更加迅速。

![640?wx\_fmt=png][640_wx_fmt_png 1] Trie树样子

通过上图，可以发现 Trie树 的三个特点：

通过动画理解 Trie 树构造的过程。在构造过程中的每一步，都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后，Trie 树就构造好了。

![640?wx\_fmt=gif][640_wx_fmt_gif] Trie 树构造

### Trie树的插入操作 ###

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

Trie树的插入操作

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

### Trie树的查询操作 ###

在 Trie 树中查找一个字符串的时候，比如查找字符串 `code`，可以将要查找的字符串分割成单个的字符 c，o，d，e，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径。

![640?wx\_fmt=png][640_wx_fmt_png 2] code的匹配路径

如果要查找的是字符串`cod`(鳕鱼)呢？还是可以用上面同样的方法，从根节点开始，沿着某条路径来匹配，如图所示，绿色的路径，是字符串`cod`匹配的路径。但是，路径的最后一个节点「d」并不是橙色的，并不是单词标志位，所以`cod`字符串不存在。也就是说，`cod`是某个字符串的前缀子串，但并不能完全匹配任何字符串。

![640?wx\_fmt=png][640_wx_fmt_png 3] cod的匹配路径

### Trie树的删除操作 ###

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

#### 删除整个单词（比如 hi ） ####

![640?wx\_fmt=gif][640_wx_fmt_gif 2] 删除整个单词

#### 删除前缀单词（比如 cod ） ####

![640?wx\_fmt=gif][640_wx_fmt_gif 3] 删除前缀单词  
这种方式删除比较简单。  
只需要将 `cod`单词整个字符串查找完后， `d`节点因为不是叶子节点，只需将其单词标志去掉即可。

#### 删除分支单词（比如 cook ） ####

![640?wx\_fmt=gif][640_wx_fmt_gif 4] 删除分支单词  
与 **删除整个单词** 情况类似，区别点在于删除到 `cook` 的第一个 `o` 时，该节点为非叶子节点，停止删除，这样就完成 `cook`字符串的删除操作。

### Trie树的应用 ###

事实上 Trie树 在日常生活中的使用随处可见，比如这个：

具体来说就是经常用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

#### 1. 前缀匹配 ####

例如：找出一个字符串集合中所有以 `五分钟` 开头的字符串。我们只需要用所有字符串构造一个 trie树，然后输出以 五−>分−>钟 开头的路径上的关键字即可。

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

![640?wx\_fmt=png][640_wx_fmt_png 4] google搜索

#### 2. 字符串检索 ####

给出 N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，按最早出现的顺序写出所有不在熟词表中的生词。

检索/查询功能是Trie树最原始的功能。给定一组字符串，查找某个字符串是否出现过，思路就是从根节点开始一个一个字符进行比较：

### Trie树的局限性 ###

如前文所讲，Trie 的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

假设字符的种数有`m`个，有若干个长度为n的字符串构成了一个 Trie树 ，则每个节点的出度为 `m`（即每个节点的可能子节点数量为`m`），Trie树 的高度为`n`。很明显我们浪费了大量的空间来存储字符，此时Trie树的最坏空间复杂度为`O(m^n)`。也正由于每个节点的出度为`m`，所以我们能够沿着树的一个个分支高效的向下逐个字符的查询，而不是遍历所有的字符串来查询，此时Trie树的最坏时间复杂度为`O(n)`。

这正是空间换时间的体现，也是利用公共前缀降低查询时间开销的体现。

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

希望今天的这篇文章能帮大家认识到掌握好了数据结构可以在工作中带来多大的帮助，大家加油：）

### References ###

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

![640?wx\_fmt=png][640_wx_fmt_png 5]

[640_wx_fmt_jpeg]: /images/20220125/f4fb4d4379704e5fbc50074081aa3b7f.png
[640_wx_fmt_png]: /images/20220125/314cf676e414462488917939f384dd6f.png
[640_wx_fmt_jpeg 1]: /images/20220125/964347c080c04173a306c8d9be94533f.png
[640_wx_fmt_png 1]: /images/20220125/63680ffa3ca84218b140b27320b9b245.png
[640_wx_fmt_gif]: /images/20220125/34a3f96207454d35babb5c70ffe3e6fc.png
[640_wx_fmt_gif 1]: /images/20220125/f49aeae00c2546b499a4210322c880c3.png
[640_wx_fmt_png 2]: /images/20220125/3922b2aa3e4a4670ac2267a289fd33e5.png
[640_wx_fmt_png 3]: /images/20220125/a142fb465a5b4fa08a29a5782bdb2b3f.png
[640_wx_fmt_gif 2]: /images/20220125/b32f56060f9643eeb8d644bfe4c32e03.png
[640_wx_fmt_gif 3]: /images/20220125/03084c0110fe4b59bdbb39bf4cf74e2e.png
[640_wx_fmt_gif 4]: /images/20220125/b84451c6b9c14aafb6767d8eaff5d823.png
[640_wx_fmt_png 4]: /images/20220125/8608f3d9c26642c994987c0879d975fe.png
[640_wx_fmt_png 5]: /images/20220125/a02bd734f5ef4e48bb8e69d022947e7c.png