字典树的概念和用途

字典树的概念和用途

字典树（Trie 树），又称单词查找树或者键树，是一种树形结构，是一种哈希树的变种。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie 的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

图中的数字代表单词出现的频次。

字典树的基本性质

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。

• 从根节点到某一个节点，路径上经过的字符连接起来，就是该节点对应的字符串。

• 每个节点的所有子节点包含的字符都不相同。

实现 Trie (前缀树)

题目地址 (opens new window)

var TrieNode = function() {
  this.children = {};
  this.isEnd = false;
};

var Trie = function() {
  this.root = new TrieNode();
};

// 插入
Trie.prototype.insert = function(word) {
  if (!word) return;
  let node = this.root;
  for (const c of word) {
    if (!node.children[c]) {
      node.children[c] = new TrieNode();
    }
    node = node.children[c];
  }
  node.isEnd = true;
};

// 查询
Trie.prototype.search = function(word) {
  if (!word) return false;
  let node = this.root;
  for (const c of word) {
    if (!node.children[c]) {
      return false;
    }
    node = node.children[c];
  }
  return node.isEnd;
};

// 前缀
Trie.prototype.startsWith = function(prefix) {
  if (!prefix) return true;
  let node = this.root;
  for (const c of prefix) {
    if (!node.children[c]) {
      return false;
    }
    node = node.children[c];
  }
  return true;
};