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;