第八十三期：数据结构（字典树 trie tree）

terrence386

发布于 2022-07-15 11:03:45

2440

发布于 2022-07-15 11:03:45

文章被收录于专栏：JavaScript高级程序设计JavaScript高级程序设计

树tree

树，对于前端来讲，算是比较复杂的数据结构了。它是我们了解图的前提。图可以用来表示对象之间的关系，并且这个对象可以是任意类型，只要对象之间有固定的关系，就可以用树的形式来表示。

虽然从数据结构上讲，树有很多种形式：

有序树
无序树
二叉树
满二叉树
完全二叉树
哈夫曼树
等等

我们仅仅用一个例子来简单的了解一下树这个数据结构。

字典树 trie tree

这个例子，我们将创建一个单词查找树trie tree，并用所有国家的列表对其进行预填充。然后，用户可以输入他们国家的名称，我们的组件将作为一个预先输入，并向用户显示可用的选项。

是的，你没有看错，这个功能类似于我们在常用的前端框架中的tree组件。我猜测原理是一样的，甚至这个例子比有的框架实现的更加优秀。

我们可以思考一下为什么我们需要字典树？如果我们百度一下字典树，我们会有如下结论：

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

换句话说，字典树就是一个优化的查找树，它的键是字符串。

举个例子，假设我们有个数组：

var friends = ['ross','rachel','adam','amy','joey'];

然后我们把它转化成一个字典树，就变成了下面这个样子：

从这个图上可以看到，从根节点开始，我们根据输入的字符串一步一步的构建了这棵树。单词被分解为单个字符，然后重复的节点不会被重新插入，而是被重用以构建树的其余部分。

添加

我们可以简单实现一个添加方法

export class Trie {
    tree = {}
    constructor() {}

    add(input) {
        //  设置根节点
        var currentNode = this.tree
        // 初始化下一个节点
        var nextNode = null
        // 拆分输入的字符串  adma --> a & dma
        var curChar = input.slice(0,1)
        input  = input.slice(1)

        //找到第一个字符的节点，然后接着拆分
        while(currentNode[curChar] && curChar){
            currentNode = currentNode[curChar]
            curChar=input.slice(0,1)
            input=input.slice(1)
        }
        // 当下个字符可用 则添加新的分支
        while(curChar){
            // 下一个节点
            nextNode ={}
            // 当前节点的当前字符
            currentNode[curChar]=nextNode
            // 迭代下一个
            currentNode=nextNode
            // 准备下一次迭代
            curChar=input.slice(0,1)
            input=input.slice(1)
        }
    }
}

上面的代码其实做了两件事：

确定树已构建到哪个级别。
将剩余部分添加为一个新子树。

我们添加一个admin字符串打印一下：

let t = new Trie()
t.add('admin')
t.add('addon')
console.log(t.tree)

/*
{
  a:{
    d:{
      m:{
        i:{
          n:{}
        }
      },
      d:{
        o:{
          n:{}
        }
      }
    }
  }
}
*/

我们会发现前面相同的两个字符是公共部分，后面的是m和d是两个不同的分支。

查找

有了添加方法，我们再来实现一个查找方法：

// 查找
    search(input) {
        let currentNode = this.tree
        let curChar = input.slice(0,1)
        input = input.slice(1)
        // 根据当前的字符 提取子节点
        while(currentNode[curChar] && curChar){
            currentNode = currentNode[curChar]
            curChar = input.slice(0,1)
            input = input.slice(1)
        }

        // 如果到达结尾处也没有找到子节点
        if(curChar && !currentNode(curChar)){
            return {}
        }
        return currentNode
    }

我们用之前的数据做个测试，然后就可以看到下面的结果。

加点提示信息呗

有时候我们需要在界面上展示一些提示信息，比如这种效果：

当然，这里只是举个例子。

这个也简单，我们只需要在新增节点的时候讲节点信息保存到一个对象中即可。

 //  新增
    add(input) {
        //  设置根节点
        var currentNode = this.tree
        // 初始化下一个节点
        var nextNode = null
        // 拆分输入的字符串  adma --> a & dma
        var curChar = input.slice(0, 1)
        console.log(curChar)
        input = input.slice(1)

        //找到第一个字符的节点，然后接着拆分
        while (currentNode[curChar] && curChar) {
            currentNode = currentNode[curChar]

            // 保存提示信息
            currentNode.remainder.push(input)

            curChar = input.slice(0, 1)
            input = input.slice(1)
        }
        // 当下个字符可用 则添加新的分支
        while (curChar) {
            // 下一个节点
            nextNode = {
                // 增加提示信息
                remainder:[input]
            }
            // 当前节点的当前字符
            currentNode[curChar] = nextNode
            // 迭代下一个
            currentNode = nextNode
            // 准备下一次迭代
            curChar = input.slice(0, 1)
            input = input.slice(1)
        }
    }