leafy

Different Tree Implementations

Leafy

leafy is a library of different tree implementations. leafy can be used in both the browser and node.

Why would I need a tree in javascript? I have arrays and objects.

Good question!

The driving reason behind the creation of leafy was the library nools which needed a datastructure that was

  • fast
  • maintained order
  • could have items inserted into it without having to re-sort the entire structure.

This was needed in order to maintain a real time list of rule activations without having to search or sort the actions on insertion.

Often a tree is overkill but when you need one its good to know its out there.

npm install leafy

Or download the source (minified)

Note leafy depends on declare.js, extended, is-extended, string-extended, and array-extended

leafy contains the following tree implementations.

options

When creating a tree you can specify a compare function used to sort items as they are inserted or removed.

var tree = new leafy.AVLTree({
   compare : function(a, b){
       var ret = 0;
       if (a.type > b.type) {
           ret = 1;
       } else if (a.type < b.type) {
           ret = -1;
       }
       return ret;
   }
});

By default the tree uses a natural ordering function.

function compare(ab) {
   var ret = 0;
   if (> b) {
       return 1;
   } else if (< b) {
       return -1;
   } else if (!b) {
       return 1;
   }
   return ret;
}

Each tree contains the following functions.

insert

Insert an item into an the tree.

tree.insert("a");
tree.insert("b");
tree.insert("c");
tree.insert("aa");

remove

Remove an item from a tree.

tree.remove("a");
tree.remove("c");

clear

Remove all items from a tree.

 
tree.insert("a");
tree.insert("b");
tree.insert("c");
tree.insert("aa");
 
tree.clear();
 

isEmpty

Returns a boolean indicating if the tree is currently empty.

tree.insert("a");
tree.insert("b");
tree.insert("c");
tree.insert("aa");
 
tree.isEmpty(); //false
 
tree.clear();
 
tree.isEmpty(); //true

contains

Test if a tree contains a particular value.

tree.insert("a");
tree.insert("b");
tree.insert("c");
 
tree.contains("a"); //true 
tree.contains("d"); //false 

**`toArray([order=leafy.IN_ORDER]);

Coverts a tree to an array with the values in the order specified, or in order if not specified

tree.insert("a");
tree.insert("b");
tree.insert("c");
 
tree.toArray(); //["a", "b", "c", "d"] 
tree.toArray(leafy.REVERSE_ORDER); //["d", "c", "b", "a"] 

forEach(iterator(iterator[, scope[, order=leafy.IN_ORDER]])

Loop through the items in tree.

By default the tree will loop through items in order.

tree.insert("a");
tree.insert("b");
tree.insert("c");
tree.insert("aa");
 
tree.forEach(function(itemtree){
    console.log(item); //"a", "b", "c", "d" respectively 
});

You can loop through a tree in any order you wish by specifying any of the following orders.

  • leafy.REVERSE_ORDER
  • leafy.IN_ORDER
  • leafy.POST_ORDER
  • leafy.PRE_ORDER
 
tree.forEach(function(itemtree){
    console.log(item); //"d", "c", "b", "a" respectively 
}, null, leafy.REVERSE_ORDER);
 

map(iterator[, scope[, order=leafy.IN_ORDER]])

Map is very similar to the array counter part except that it returns new tree with the mapped values.

//creates a new tree with the returned values "aa", "bb", "cc", "dd" 
var mapped = tree.map(function(itemtree){
    return item + item;
});
 

filter(iterator[, scope[, order=leafy.IN_ORDER]])

Filter is very similar to the array counter part except that it returns new tree with the mapped values.

//creates a new tree with the returned values "a", "b" 
var mapped = tree.map(function(itemtree){
    return item === "a" || item === "b";
});
 

Trees also contains the following array methods that act just like their array counter part.

Note all of these methods accept an order parameter.

  • reduce
  • reduceRight
  • every
  • some

findLessThan(value[, exclusive=true])

Find all values in a tree less than a particular value. If exclusive is set to false then the original value will be included in the resulting array.

tree.insert("a");
tree.insert("b");
tree.insert("c");
tree.insert("d");
 
tree.findLessThan("d"); //["a", "b", "c"]; 
tree.findLessThan("d", false); //["a", "b", "c", "d"]; 
 

findGreaterThan(value[, exclusive=true])

Find all values in a tree greater than a particular value. If exclusive is set to false then the original value will be included in the resulting array.

tree.insert("a");
tree.insert("b");
tree.insert("c");
tree.insert("d");
 
tree.findGreaterThan("a"); //["d", "c", "b"]; 
tree.findGreaterThan("a", false); //["d", "c", "b", "a"]; 
 

print()

Prints the current structure of a tree to the console.