I’m not going to dive deep into what Binary Search Tree is because this tutorial and Wikipedia does an excellent job at that. Instead I’ll mostly dicuss about a neat JS implementation that I came across recently, usable on the server side with Node.js and client-side as well.
What's the one thing every developer wants? More screens! Enhance your coding experience with an external monitor to increase screen real estate.
Introduction
Precisely, a binary search tree is a non-linear data structure organized into a hierarchy of nodes (look at the main image above) each of which points to a left and right node, the left node being lesser while right being greater in value. Each subtree or node at any level must be a binary tree with no duplicate nodes whatsoever. It can be used for anything that’s comparable. By nature the tree is sorted and fast for searching as possibilities get eliminated with each steps/nodes.
So that’s the gist of it, the tutorial linked above explains it in details with a pure JavaScript implementation (yay!) while the wikipedia article also demonstrates Java and C++ implementations.
Its useful to know that there’s a commonly used variation of Binary tree called Red Black Search Tree that imposes some extra requirements to self-balance itself. A self balancing tree keeps its height small (number of levels below the root) on multiple insertions and deletions. Think of it as an implementation where the depth of the farthest leaf ain’t more than double of that of the nearest leaf. Ofcourse the balancing task can come at a considerable cost with large structures.
Using js_bintrees
js_bintrees provides Binary and Red-Black Search Trees implementations in JavaScript. You can install it via npm (or just load the script in your webpage for browser usage) –
$ npm install bintrees
Now let’s see how to go about using it. We’ll use RB Tree for the upcoming examples.
var RBTree = require('bintrees').RBTree;
// or for client side usage
// <script src="/path/to/rbtree.js"></script>
var compareFunction = function (a, b) { return a - b; };
var tree = new RBTree(compareFunction);
tree.insert(6);
tree.insert(5);
tree.insert(-20);
tree.insert(-8);
So we create an instance of the RBTree constructor that requires a comparator function as an argument, which in this case is compareFunction. The function’s behaviour, i.e., the return value must be 0 if a === b, lesser than 0 if a < b or greater than 0 if a > b. Unsurprisingly, this is similar to the compare function you pass to Array.prototype.sort.
Let's take a look at the different methods this module provides like find(), insert(), clear(), remove(), each(), reach(), iterator(), min(), max() -
$ node
> RBTree = require('bintrees').RBTree
[Function: RBTree]
> compareFunction = function (a,b) { return a-b; }
[Function]
> tree = new RBTree(compareFunction)
{ _root: null,
_comparator: [Function],
size: 0 }
> tree.insert(6)
true
> tree.insert(5)
true
> tree.insert(-20)
true
> tree.insert(-8)
true
> tree
{ _root:
{ data: 5,
left:
{ data: -20,
left: null,
right: [Object],
red: false },
right:
{ data: 6,
left: null,
right: null,
red: false },
red: false },
_comparator: [Function],
size: 4 }
> tree.find(-8)
-8
> tree.find(5)
5
> tree.min()
-20
> tree.max()
6
> tree.find(-5)
null
> tree.remove(-5)
false
> tree.remove(-8)
true
> tree.find(-8)
null
> tree.each(function (data) { console.log(data); });
-20
5
6
undefined # return value
# reach is each in reverse order
> tree.reach(function (data) { console.log(data); });
6
5
-20
undefined # return value
each and reach uses the iterator methods behind the scenes. tree.iterator() will return a null-iterator on which next() returns the first element in the tree while prev() returns the last element. Otherwise, next() returns the next element in the tree while prev() returns the previous one. Usage -
> it = tree.iterator()
{ _tree:
{ _root:
{ data: 5,
left: [Object],
right: [Object],
red: false },
_comparator: [Function],
size: 3 },
_ancestors: [],
_cursor: null } # null-iterator
> it.next()
-20
> it.next()
5
> it.next()
6
> it.next()
null # null-iterator
> it
{ _tree:
{ _root:
{ data: 5,
left: [Object],
right: [Object],
red: false },
_comparator: [Function],
size: 3 },
_ancestors: [],
_cursor: null } # null-iterator
> it.prev()
6
> it.prev()
5
> it.prev()
-20
> it.prev()
null # null-iterator
> it.prev()
6
> it.next()
null
As you can see, when the iteration hits the end, it becomes a null-iterator again. For proper iteration in your code, you can do something like this -
var it = tree.iterator()
, node;
while ((node = it.next()) !== null) {
// do something with `node`
}
Use it.prev() to iterate backwards, which is what reach() does to traverse in reverse order. Ofcourse you can use next() or prev() anytime when traversing through the tree.
There are 3 more interesting methods that returns an iterator - findIter(item) that returns one with the cursor (or current item) at the matching node if found else null, lowerBound(item) that returns one at or immediately after the matching node and upperBound(item) that returns one after the match. Lets try these out -
> tree.insert(-20) true > tree.insert(5) true > tree.insert(6) true > tree.size 3 > it = tree.findIter(2) null # No match returned/found # will return iterator with cursor at 5 > it = tree.findIter(5) > it.next() 6 > it.next() null > it.next() -20 > it.next() 5 > it.next() 6 # find 2 or the item after 2 (if 2 not found) # and place the cursor on the match > it = tree.lowerBound(2) > it.next() 6 > it.prev() 5 # find 6 or the item after 6 (if 6 not found) # and place the cursor on the match > it = tree.lowerBound(6) > it.next() null > it.prev() 6 # Place cursor on the item after 5 > it = tree.upperBound(5) > it.next() null > it.prev() 6
If for whatever reason you want to clear the entire tree -
> tree.clear()
undefined
> tree.find(5)
null
> tree.find(-20)
null
> tree
{ _root: null,
_comparator: [Function],
size: 0 }
Last but not the least getting the number of nodes in a tree is as easy as accessing the size property on the tree object.
> tree.size 4
Some Real World Context
I am working on an application where a lot of realtime data comes (as JSON) from a Node/Redis backend. You can imagine the data to be a list of objects - { field1: val1, field2: val2 ... fieldN: valN } - that have to be shown in a tabular fashion (as a report) on the webpage. The objects need to be sorted by their price field and displayed in ascending/descending order. As new data comes in, either update the row data against incoming price or if the row doesn't exists, create new ones.
Initially I just displayed all the rows and then sorted them on the price column using simple sorting technique with Array.prototype.sort -
Grid.prototype.sortGrid = function () {
// Sort table by price
var self = this
, levels = $('#grid .level')
// Convert the array-like object into a real proper array
, levels = Array.prototype.splice.call(levels, 0);
var compare = function (a, b) {
a = parseFloat(a.querySelector('.price').innerHTML);
b = parseFloat(b.querySelector('.price').innerHTML);
return b-a;
};
levels.sort(compare);
self.$el.html('');
levels.forEach(function (level) {
self.$el.append(level);
});
};
But then I discovered this module and simply pumped in all objects into a tree, iterated over it (pretty much as explained before) and formed the grid/table. This is how my comparator function looks like -
var tree = new RBTree(function (a,b) {
return a.price - b.price;
});
Notice how I use ob.property for comparison, which means you can use this approach not just for plain numbers but for any kind of data/object that can be compared.
When new objects come in, all I do is check their existance in the tree using find({ price: ob.price }) and if they do exist, update all fields with matching prices in the table else just insert() them and redraw the table. I could probably ditch the find() call and just insert() as it returns true on success while false on failure which will most probably be the result of duplicate insertion.
Since I am using this module, instead of redrawing after an insert() during an "update" operation, I can just find the node before/after the newly inserted one using findIter().next() or findIter().prev() -> find the row in the table DOM with that price -> insert a new row before/after that row in the DOM. Hopefully this'd help reduce load on CPU and memory consumption when the table is too large.
Conclusion
If you ever have a requirement where you need to have unique items in your data structure, want them sorted, need fast search and quick lookups, etc. for purposes like storage, generating reports, grids, tabular data or some other ones, then feel free to consider this option.
Good write up! Thanks.
I thought binary trees are only good for hurting my feelings in job interviews 🙂
Verdade!