Simple Search Tries in ES6

searchtrie.js

/*

TRIES

A trie (or radix tree) is a simple data structure that represents a set of values stored against a
tokenizable key (usually strings). Each edge in a Trie represents a token in a key. A key is present in the trie if 
(1) There exists a path (e1..en) from the root such that the key = <token(e1), token(e2)...token(en)> and 
(2) there is some value at the path's terminal vertex vn.

Let k = length(key). Then time complexity for lookup, insertion and deletion for a Trie is O(k).
Let A be the alphabet from which keys are produced. Then the worst case space complexity of a trie is O(|A|^l).

Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). 
This does not seem like an advantage, since normally k ≥ log n, but in a balanced tree every comparison is a 
string comparison requiring O(k) worst-case time, many of which are slow in practice due if there are long common prefixes 
that are compared in order, left to right. In a trie, all comparisons require constant time, but it takes m comparisons 
to look up a string of length m. Radix trees can perform these operations with fewer comparisons, and require many 
fewer nodes.

Tries really shine when there are repeated prefixes within the keys of a data set (for example a dictonary of words). 
Tries suck when the length of keys is unbounded. Great use cases for a trie include: (1) Predictive text (2) Spell Check
You can compress a sparse tree to reduce the space it takes in memory.

Why do they call it 'trie' (pronounced `try`) - Some French guy called it a 'trie' which was meant to be short for 'retrival'.
Tries are still very much tree structures desipte the misleading name.

https://en.wikipedia.org/wiki/Trie#Dictionary_representation

*/

let isNull = (i) => { return (i === null || i === undefined); };
;
;
export default class SearchTrie {
    constructor(items) {
        if (items)
            this.initializeWithItems(items);
    }
    addItemIndexForKeywords(itemIndex, keywords) {
        for (var i in keywords) {
            this.addItemIndexForKeyword(itemIndex, keywords[i]);
        }
    }
    addItemIndexForKeyword(itemIndex, keyword) {
        let letters = keyword.toLowerCase().split('');
        var lastNode = this.root;
        for (var i in letters) {
            let l = letters[i];
            if (isNull(lastNode.children[l])) {
                lastNode.children[l] = { children: {}, items: {} };
            }
            lastNode.children[l].items[itemIndex] = true;
            lastNode = lastNode.children[l];
        }
    }
    initializeWithItems(items) {
        this.root = {
            children: {},
            items: {}
        };
        this.items = items;
        for (var i in items) {
            this.addItemIndexForKeywords(i, items[i].keywords);
        }
        return this;
    }
    match(query) {
        let step = 0;
        let letters = query.toLowerCase().split('');
        let lastNode = this.root;
        while (step < letters.length) {
            let l = letters[step];
            if (isNull(lastNode.children[l])) {
                return [];
            }
            else {
                lastNode = lastNode.children[l];
            }
            step = step + 1;
        }
        return Object.keys(lastNode.items).map((i) => { return this.items[i]; });
    }
}