Nutritious Pumpkin Mash

    node-avl-tree

    0.1.1 • Public • Published

    NPM Version Build Status Built with Grunt

    Installation

    Install via npm: npm install node-avl-tree

    The dist/ directory contains both a normal (avl.js) as well as a minified version of the library (avl.min.js). Import either into Node.js using require("avl") or directly include in the browser using <script src="avl.min.js"></script>

    Usage

    Create

    var t = new AVLTree();
    t.is_empty();  // true
    t.root;  // null

    Insert

    var t = new AVLTree();
    var k = 1;  // Key is used to determine order
    var v = 'hello';  // User data to be associated with key
    var n = t.insert(k, v);  // returns newly created AVLNode
    n.key;  // k
    n.value;  // v
    t.root;  // n

    Search

    var t = new AVLTree();
    var a = t.insert(1, 'hello');
    var b = t.insert(2, 'world');
    t.search(1);  // returns a
    t.search(3);  // returns b, the last leaf visited while searching for 3

    Remove

    var t = new AVLTree();
    var a = t.insert(1, 'hello');
    var b = t.insert(2, 'world');
     
    a.is_valid();  // true
    t.remove(1);  // Removal by key, returns 'hello'
    a.is_valid();  // false, node has been removed
     
    b.is_valid();  // true
    b.remove();  // Removal by node, returns 'world'
    b.is_valid();  // false, node has been removed

    Custom Comparator

    The default tree will assume its keys are numbers and imposes the natural ordering on its nodes based on them. You may supply your own compare function during instantiation to customize this behavior.

    var default = function(a, b) { return a - b; }  // This is the default comparator
    var reversed = function(a, b) { return b - a; }
     
    var t1 = new AVLTree();  // == new AVLTree(default)
    t1.insert(1); t1.insert(2); t1.insert(3);
     
    /*
     * Tree structure:
     *    2
     *   / \
     *  1   3
     */
     
    var t2 = new AVLTree(reversed);
    t2.insert(1); t2.insert(2); t2.insert(3);
     
    /*
     * Tree structure:
     *    2
     *   / \
     *  3   1
     */

    Example: Sorting

    var t = new AVLTree();
    t.insert(2, 'world');
    t.insert(6, 'day');
    t.insert(5, 'beautiful');
    t.insert(3, 'what');
    t.insert(1, 'hello');
    t.insert(4, 'a');
     
    result = []
    while (!t.is_empty()) {
        result.push(t.search(0).remove());
    }
     
    result.join()  // 'hello world what a beautiful day'

    License

    This software is licensed under the MIT License. See the LICENSE file for more information.

    Install

    npm i node-avl-tree

    DownloadsWeekly Downloads

    1

    Version

    0.1.1

    License

    none

    Last publish

    Collaborators

    • rharel