树和二叉搜索树

树 Tree
tree.png

二叉搜索树

二叉搜索树任何一个结点，它的左子树的所有结点都要小于这个根结点，它的右子树的所有结点都要大于根结点。

二叉树搜索树中序遍历是一个升序的序列。

二叉搜索树查找的效率更高。

binary_search_tree.png

Trie 树

基本结构

字典树，即 Trie 树，又称单词查找树或键树，是一种树形结构。
典型应用是用于统计和排序大量的字符串（不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

Trie 树不是一颗二叉树，是多叉树。

优点：最大限度地减少无谓的字符串比较，查找效率比哈希表高。

trie.webp

基本性质

  • 结点本身不存完整单词；
  • 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串；
  • 每个结点的所有子结点路径代表的字符都不相同。

核心思想

Trie 树的核心思想就是空间换时间。

利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

字典树结构

trie_struct.png

相关题目

二叉树的层次遍历

实现 Trie (前缀树)（亚马逊、微软、谷歌在半年内面试中考过）

单词搜索 II （亚马逊、微软、苹果在半年内面试中考过）

  1. // 二叉树的层次遍历
  3. /**
  4.  * 广度优先搜索
  5.  * @param {TreeNode} root
  6.  * @return {number[][]}
  7.  */
  8. var levelOrder = function(root) {
  9.   if (!root) return [];
  11.   const ans = [];
  13.   const queue = [root];
  15.   while (queue.length) {
  16.     let len = queue.length;
  18.     ans.push([]);
  20.     while (len--) {
  21.       const n =  queue.shift();
  23.       ans[ans.length - 1].push(n.val);
  25.       n.left && queue.push(n.left);
  26.       n.right && queue.push(n.right);
  27.     }
  28.   }
  30.   return ans;
  31. };
  1. // 实现 Trie (前缀树)
  3. var Trie = function() {
  4.   this.children = {};
  5. };
  7. /** 
  8.  * @param {string} word
  9.  * @return {void}
  10.  */
  11. Trie.prototype.insert = function(word) {
  12.   let nodes = this.children;
  14.   for (const ch of word) {
  15.     if (!nodes[ch]) {
  16.       nodes[ch] = {};
  17.     }
  18.     nodes = nodes[ch];
  19.   }
  21.   nodes.isEnd = true;
  22. };
  24. Trie.prototype.searchPrefix = function(word) {
  25.   let nodes = this.children;
  27.   for (const ch of word) {
  28.     if (!nodes[ch]) {
  29.       return false;
  30.     }
  31.     nodes = nodes[ch];
  32.   }
  34.   return nodes;
  35. };
  37. /** 
  38.  * @param {string} word
  39.  * @return {boolean}
  40.  */
  41. Trie.prototype.search = function(word) {
  42.   const nodes = this.searchPrefix(word);
  44.   return nodes != undefined && nodes.isEnd !== undefined;
  45. };
  47. /** 
  48.  * @param {string} prefix
  49.  * @return {boolean}
  50.  */
  51. Trie.prototype.startsWith = function(prefix) {
  52.   return this.searchPrefix(prefix);
  53. };
  55. /**
  56.  * Your Trie object will be instantiated and called as such:
  57.  * var obj = new Trie()
  58.  * obj.insert(word)
  59.  * var param_2 = obj.search(word)
  60.  * var param_3 = obj.startsWith(prefix)
  61.  */