前缀树

trie

Posted on 2019-03-05

定义

Trie树,又叫字典树前缀树(Prefix Tree),是一种多叉树结构。如下图所示

与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串

针对上图的结构,我们可以知道由字符串['ap', 'app', 'apc', 'trie', 'du', 'dump']构成

特点:

  • 除根节点不包含字符,其他节点都包含字符
  • 每个节点的子节点包含的字符串不相同
  • 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串
  • 每个节点的子节点通常有一个标志位,用来标识单词的结束

构建Trie树

为了构建一颗Trie树,首先需要明确树的节点的结构。对于每一个节点都有两个属性:

  • 是否是单词结尾的属性is_word
  • 子节点childrenchildren是一个以单词字符为key的对象

所以我们可以很轻易的构建出节点对象:

var Trie = function() {
  this.is_word = false
  this.children = {}
};

当插入一个单词到树中时,就需要从根节点开始,查看当前的字符是否存在于子节点中,若不存在,则直接创建一个子节点,存在的话则继续遍历单词,并将当前节点置为上个字符对应的节点,当到达单词末尾时需要将最后一个节点的is_word置为true

Trie.prototype.insert = function(word) {
  let cur = this
  for (let i = 0; i < word.length; i++) {
    const char = word[i]
    if (!cur.children[char]) {
      cur.children[char] = new Trie()
    }
    cur = cur.children[char]
  }
  cur.is_word = true
};

查询单词

对于查询来说,首先有路径满足单词,其次就是确定单词的最后一个字符在树中的节点被标记为单词结尾了,即is_wordtrue

Trie.prototype.search = function(word) {
  let cur = this
  for (let i = 0; i < word.length; i++) {
    const char = word[i]
    cur = cur.children[char]
    if (!cur) break
  }
  return cur && cur.is_word || false
};

完整实现

var Trie = function() {
  this.is_word = false
  this.children = {}
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  let cur = this
  for (let i = 0; i < word.length; i++) {
    const char = word[i]
    if (!cur.children[char]) {
      cur.children[char] = new Trie()
    }
    cur = cur.children[char]
  }
  cur.is_word = true
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
  let cur = this
  for (let i = 0; i < word.length; i++) {
    const char = word[i]
    cur = cur.children[char]
    if (!cur) break
  }
  return cur && cur.is_word || false
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
  let cur = this
  for (let i = 0; i < prefix.length; i++) {
    const char = prefix[i]
    cur = cur.children[char]
    if (!cur) break
  }
  return cur ? true : false
};

/** 
 * Your Trie object will be instantiated and called as such:
 * var obj = Object.create(Trie).createNew()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */