Tries.md

Tries

Lecture

Notes

Goal is given a text T and pattern P (where the strings exist over ∑), find some or all the occurences of P in T as a substring.

Trie node representation

There are three common ways to represent a trie:

Data Structure	Query Time	Space Complexity
Array	O(P)	O(T∑)
Binary Search Tree	O(P log ∑)	O(T)
Hash Table (No predecessors)	O(P)	O(T)
Trays	O(P + log ∑)	O(T)
Weight-balanced BST	O(P + log k)	O(T)

Implementations

Initial attempt

const Trie = (words) => {
  const t = {};
  let visitor = t;
  
  words.forEach((word) => {
    for (let i = 0, length = word.length; i < length; i++) {
      if (visitor[word[i]]) {
        visitor = visitor[word[i]];
      } else {
        visitor = visitor[word[i]] = {};
      }
      
      if (i === word.length - 1) {
        visitor.word = true;
      }
    }
    
    visitor = t;
  });
  
  return t;
};

const t = Trie([
  'a',
  'an',
  'and',
  'all',
  'boy'
]);

console.log(JSON.stringify(t, null, 2));

Weight-balanced BST

• Weight is the number of descendat leaves in a subtree, in this scenario