|
Page 1 of 3 Binary trees in JavaScript? Easy with the right storage mapping function. Find out how to code a binary tree right up to a depth-first traversal.
JavaScript Data Structures
Contents
- The Associative Array
- The String Object
- The Array object
- Speed dating - the art of the JavaScript Date object
- Doing JavaScript Date Calculations
- A Time Interval Object
- Collection Object
- Stacks, Queue & Deque
- The Linked List
- A Lisp-like list
- The Binary Tree
- Bit manipulation
- Typed Arrays I
- Typed Arrays II
- Master JavaScript Regular Expressions
* First Draft
The binary tree is one of the more useful of the "advanced" data structures and it is fairly easy to implement in JavaScript.
However the usual method is to use object references, links or pointers and this makes searching the tree an expensive task. To find a given node in the tree you generally have to traverse the tree and examine all the nodes on the way to the target node.
For trees with fixed branching factors e.g. a binary tree with two child nodes attached to every parent node or a ternary tree with three child nodes and so on... there is a very simple but often overlooked way of doing the job.
Instead of using references to link the tree together you can use a storage mapping function to store the data at fixed location. You can think of it as an example of a perfect hash function if you want to but it is simpler to think in terms of storage mapping functions.
In a nutshell a Storage Mapping Function SMF is a function that when given a set of indices that specify which element of a structure you want it returns the address or location of the element.
For example for an array you would give the SMF the index of the array element you want and it gives you the address where it is stored.
Notice that this method only works for trees with a fixed branching factor and no "missing" nodes i.e. every tree is complete and balanced.
The Binary Tree SMF
A binary tree is a tree structure such that each node, apart from the final or terminal nodes, has exactly two children - hence the binary in binary tree.
You can specify the element of the tree that you want by giving two indices - the level i.e. how far down the tree and the node number at that level i.e. how far to the right the node is.
Each node is associated with a value that takes n bytes to store then a suitable SMF is:
location = base + n*i + n*(2j-1)
which gives the location of the value stored at ith node at the jth level.
To see why this works consider the following small binary tree:
j node i
level 0 0
/ \
/ \
/ \
level 1 0 1
/ \ / \
/ \ / \
level 2 0 1 2 3
and so on.
Notice that going from one level to the next doubles the number of nodes and you should be able to work out that the number of nodes at level j is simply 2j.
With this insight you should now also be able to see how the SMF works. The tree is stored as lines of nodes one level at a time.
That is:
Storage location 0 1 2 3 4 5 6
level 0 | 1 | 2
node 0 | 0 1 | 0 1 2 3
Storage mapping functions are used in low level code to create the data structures that high level language offer. But there is no reason they can't be used in a high level language to create new structures.
To make use of this SMF in a high-level language all you have to do is declare an array of elements that will hold the node values and use the SMF with n=1 to determine which element node i at level j is stored in.
You should be able to see that you can create a storage mapping function for any tree with a constant branching factor b. All you have to do is change the 2 to b to give:
location = base + n*i + n*(bj-1)
A JavaScript binary tree
The JavaScript Array object can be used to store any object at an indexed location so using this as the basic storage component for out binary tree is an obvious choice.
The first thing we need is the storage mapping function and here we hit our first minor problem. JavaScript doesn't have a "raise to a power" operator.
Instead it has the pow method of the Math object. For example,
Math.pow(2,k):
raises 2 to the kth power.
This is what we would have to use for a general tree with a b way branch at each node but for a binary tree we can take a slightly different and theoretically more efficient route.
The shift operators >> and << are equivalent to divide by 2 and multiply by 2 respectively. So
1<<k;
gives the result 2^k.
Using this the storage mapping function:
location = node + 2level - 1
is easy enough to translate into JavaScript.
Taking an object oriented approach let's package everything into a BinaryTree object and its associated constructor function:
function BinaryTree(){
this.btSMF=function(level,node){
return node+(1<<level)-1;
}
}
From this point on everything will be defined within the BinaryTree constructor function - a complete listing can be found at the end if you get confused about what goes where.
The btSMF function takes a node and level number and returns the location within a standard Array that the node should be stored.
We need to declare the array but JavaScript arrays are so good natured we don't have to specify its size - it will grow as needed.
this.Nodes =new Array();
Get And Set
Next we need a basic set and get functions for a node.
this.setNode=function(value,level,node){
this.Nodes[this.btSMF(level,node)]=value;
}
this.getNode=function(level,node){
return this.Nodes[this.btSMF(level,node)];
}
These two functions simply store and retrieve the data at the location indicated by the storage mapping function.
To try them out let's store a simple three level tree as shown in the diagram above:
tree=new BinaryTree();
tree.setNode(1,0,0);
tree.setNode(2,1,0);
tree.setNode(3,1,1);
tree.setNode(4,2,0);
tree.setNode(5,2,1);
tree.setNode(6,2,2);
tree.setNode(7,2,3);
and to retrieve a value you would use something like:
alert(tree.getNode(2,1));
<ASIN:1871962625>
<ASIN:1871962560>
<ASIN:1871962579>
<ASIN:1871962420>
<ASIN:1871962501>
<ASIN:1871962528>
|