Trie Tree

The trie tree is a useful data-structure when looking for a particular key in a large data set of keys. Each traversed node in the Trie Tree will complete the key by one more char. This results in a very useful addition if one is interested in all other keys that share the same prefix as the target key. For example a search for the key "sun" will also return keys such as "sunbath, sunflower, sunday or sunglasses".

TrieTree = function()
{
    var _root = null;

    var _numEntries = 0;

    function findLastNodeForString( str )
    {
        if( str == null || str.length == 0 )
        {
            return null;
        }

        var node = _root;

        const n = str.length;

        //go through every char of string
        for( var i = 0; i < n; ++i )
        {
            //move node down each time
            if( node.down != null )
            {
                node = node.down;
            }
            //if node can't go down, and str hasn't been found yet, its not in the tree
            else
            {
                return null;
            }

            //search the children lists for the correct path to follow
            while( str.charAt( i ) != node.glyph )
            {
                //if the correct path hasn't been found str is not in tree
                if( node.next == null )
                {
                    return null;
                }

                node = node.next;
            }
        }

        return node;
    }

    function recursiveList( node, str, result )
    {
        while( node != null && node.glyph != "" )
        {
            recursiveList( node.down, str + node.glyph, result );

            if( node.wordEnd )
            {
                result.push( str + node.glyph );
            }

            node = node.next;
        }
    }

    this.build = function( words )
    {
        var n = words.length;

        for( var i = 0; i < n; ++i )
        {
            this.insert( words[ i ] );
        }
    };

    this.insert = function( str )
    {
        //remove punctuation and special characters
        str = str.toLowerCase().replace( /[^a-zA-Z äöüÄÖÜß 0-9]+/gi, "" ).replace( /^\s+|\s+$/g, "" );

        if( str.length == 0 )
        {
            return;
        }

        var level = 0;

        if( _root == null )
        {
            _root = new TrieTreeNode( "", level );
        }

        var node = _root;
        var nextNode = _root;
        var parentNode = _root;

        var index = 0;

        // loop until every char in str is inserted
        while( index < str.length )
        {
            level++;

            var glyph = str.charAt( index );

            // there are no chars on this tree level yet. create a new node with given char
            if( node.down == null )
            {
                node.down = new TrieTreeNode( glyph, level );

                //this will make a lot of null check obsolete
                node.down.next = new TrieTreeNode( "", level );
                node.down.next.down = node;

                node = node.down;
            }
            // No chars on this tree level yet, insert it at right position or ignore if this char already exists
            else
            {
                parentNode = node;
                node = node.down;

                // char has smallest value, so prepend before existing ones
                if( glyph < node.glyph )
                {
                    node = new TrieTreeNode( glyph, level, node );
                    parentNode.down = node;
                }
                // find correct place where to append char
                else if( glyph > node.glyph )
                {
                    // find the correct position to insert char based on alphabetical order
                    while( node.glyph != "" && glyph > node.glyph )
                    {
                        nextNode = node;
                        node = node.next;
                    }

                    // this char does not exist yet, so append it
                    if( glyph != node.glyph )
                    {
                        node = new TrieTreeNode( glyph, level, node );
                        nextNode.next = node;
                    }
                }
            }

            index++;
        }

        if( node.wordEnd != true )
        {
            //at this point it will always be at the start of a word
            node.wordEnd = true;

            _numEntries++;
        }
        else
        {
            //console.log( "ignoring insert as " + str + " already exists" );
        }
    };

    this.has = function( str )
    {
        return ( findLastNodeForString( str ) != null );
    };

    this.list = function()
    {
        var result = [];

        if( _root == null )
        {
            return result;
        }

        recursiveList( _root.down, "", result );

        return result;
    };

    this.find = function( str )
    {
        str = str.toLowerCase();

        var result = [];

        var node = findLastNodeForString( str );

        // nothing found
        if( node == null )
        {
            return result;
        }

        if( node.wordEnd )
        {
            result.push( str );
        }

        //populate result list with all words of which str is prefix
        recursiveList( node.down, str, result );

        return result;
    };

    this.empty = function()
    {
        _root = null;

        _numEntries = 0;
    };
};

function TrieTreeNode( glyph, level, next )
{
    this.glyph = glyph || "";
    this.level = level;
    this.next = next || null;
    this.wordEnd = false;
    this.down = null;
}