ternary-search-tree

    1.0.7 • Public • Published

    Ternary Search Tree

    A ternary search tree for Node.js.

    Installation

    $ npm install ternary-search-tree --save

    Test

    $ npm test

    Usage

    var TernarySearchTree = require('ternary-search-tree');
    var tst = new TernarySearchTree();
    tst.add('is');
    tst.add('in');
    tst.add('it');
    tst.add('be');
    tst.add('by');
    tst.add('he');
    tst.add('as');
    tst.add('at');
    tst.add('on');
    tst.add('of');
    tst.add('or');
    tst.add('to');
    
    // equivalent: tst.addMany([ 'as', 'at', 'be', 'by', 'he', 'in', 'is', 'it', 'of', 'on', 'or', 'to' ]);
    
    console.log(tst.contains('as')); // = true
    console.log(tst.length); // 12
    console.log(tst.search('as')); // { node }
    console.log(tst.partialMatch('a')); // [{ node(as) },{ node(at) }]
    

    Insertion Order

    You want to avoid inserting strings into the tree in sorted order. This can result in a long skinny tree that will not perform well.

    This Dr. Dobb's article Ternary Search Trees By Jon Bentley and Bob Sedgewick provides the following guidance:

    You can build a completely balanced tree by inserting the median element of the input set, then recursively inserting all lesser elements and greater elements. A simpler approach first sorts the input set. The recursive build function inserts the middle string of its subarray, then recursively builds the left and right subarrays. We use this method in our experiments; it is fast and produces fairly well-balanced trees. The cost of inserting all words in a dictionary with function insert3 is never more than about 10 percent greater than searching for all words. D.D. Sleator and R.E. Tarjan describe theoretical balancing algorithms for ternary search trees in "Self-Adjusting Binary Search Trees" (Journal of the ACM, July 1985).

    The addMany() function takes an Array of Strings and does exactly this.

    Associated Data

    The tree stores just the strings themselves, but no other information. To associate additional information, we add a "data" member to each node. When you add a string to the tree (via the method 'add'), you can provide arbitrary data as the second parameter.

    tst.add('foo', 'bar');
    tst.add('bas', 42);
    tst.add('baz', { .. });
    tst.add('chicken');
    

    Data is retrieved via the "search" method.

    var node = tst.search('foo');
    console.log(node.data); //'bar'
    node = tst.search('chicken');
    console.log(node.data); //null
    

    Docs

    Generate docs

    $ npm docs

    Resources

    Ternary Search Trees

    Install

    npm i ternary-search-tree

    DownloadsWeekly Downloads

    3

    Version

    1.0.7

    License

    ISC

    Unpacked Size

    1.04 MB

    Total Files

    30

    Last publish

    Collaborators

    • mattpage