Nobody Pays (for) Magazines

    container-avltree

    0.1.5 • Public • Published

    container-avltree

    AvlTree implementation in Javascript

    To manage a pool of sorted elements. Complexity in O(log2(n)) for addition and removal.

    List of methods and their time complexity

    Method Time Complexity
    add O(log2(n))
    removeByReference O(log2(n))
    getCount O(1)
    popSmallest O(log2(n))
    popGreatest O(log2(n))
    getSmallestAbove O(log2(n))
    getGreatestBelow O(log2(n))
    forEach O(n * p)
    forEachReverse O(n * p)
    toArray O(n)
    clear O(n)

    Where:

    • n is the number of elements in the tree
    • p is the complexity of the processing function.

    API usage

    To instantiate a new tree:

    // In this example, myTree will hold elements sorted by zIndex
    function myComparisonFunction(a, b) {
        return a.zIndex - b.zIndex;
    }
     
    var myTree = new AvlTree(myComparisonFunction);

    To add an element:

    var myObjectReference = myTree.add(myObject); // O(log2(n))

    To remove an element:

    myTree.removeByReference(myObjectReference); // O(log2(n))

    To apply a treatment on all the elements in sorted ordered:

    myTree.forEach(function (object) {
        console.log(object);
    });

    To apply a treatment on all the elements in opposite sorted ordered:

    myTree.forEachReverse(function (object) {
        console.log(object);
    });

    To get the smallest element greater or equal to a given object:

    var myObjectAbove = myTree.getSmallestAbove({ zIndex: 4 }); // O(log2(n))

    To get the greatest element smaller or equal to a given object:

    var myObjectBelow = myTree.getGreatestBelow({ zIndex: 4 }); // O(log2(n))

    To convert into an array:

    var myArray = myTree.toArray(); // O(n)

    To get the number of elements in the tree:

    var nbElements = myTree.length;

    Keywords

    none

    Install

    npm i container-avltree

    DownloadsWeekly Downloads

    138

    Version

    0.1.5

    License

    MIT

    Last publish

    Collaborators

    • bchevalier
    • cstoquer
    • tatsujinichi