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.

• AVLTree
• RedBlackTree
• BinaryTree
• AnderssonTree

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(a, b) {
   var ret = 0;
   if (a > b) {
       return 1;
   } else if (a < 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(item, tree){
    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(item, tree){
    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(item, tree){
    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(item, tree){
    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.