前缀树(Trie)-构造解释

• 概念

  • 每个节点允许有n多个子节点，通过children对象存储为子节点群，其中
    • key代表途经的单个字母c
    • value代表新的后方节点群，其中
      • 递归存储着n多个子节点，以及一个isEnd属性代表途经到这里有单词以c结尾
  • 从根节点开始往下走，依次途经节点群得出一个个字母，可以串出一个字符串
  • 可以用来存储大量的字符串序列，加快前缀查找或整体匹配的速度

• 树的节点类型-Node类

  • 含有两个属性
    • children 子节点群
    • isEnd 标志着走到此处形成的“字符串序列”是曾经存进去的单词，初始为false

• 插入

  • 往一个节点插入单词序列，采用循环迭代方式
    • 循环取出的每个字符ch
      • 先看有没有旧的同前缀单词曾途经此字符
        • 有的话，直接取children中对应key为ch的已有结构
        • 没有就新建一个并存入children
      • 取到后，迭代为新的当前节点，进入下一次循环
    • 最后要把结尾处的isEnd设为true，表示到单词这里结尾

  addNode(currentNode, word) {
      for (const ch of word) {
          currentNode.children[ch] = currentNode.children[ch] || new Node();
          currentNode = currentNode.children[ch];
      }
      currentNode.isEnd = true;
  };
  

• 查找

  • 在一个节点中查找单词序列，采用递归方式
    • 递归结束条件——当前索引i到达单词末尾
      • 然后以当前节点的isEnd作为判断依据
    • 否则，取出当前索引i对应的字符ch，查看是否在children中有对应key为ch的已有结构
      • 有的话，取出来作为新的节点，i+1进入递归，并把递归结果原样返回
      • 没有的话，代表找不到，返回false

  searchNode(currentNode, word, i) {
      if (i === word.length) return currentNode.isEnd;
      const ch = word[i];
      if (ch in currentNode.children) {
          return searchNode(currentNode.children[ch], word, i + 1);
      } else {
          return false;
      }
  }