Page 1 of 3
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.
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.
Each node is associated with a value that takes n bytes to store then a suitable SMF is:
location = base + n*i + n*(2^j-1)
which gives the location of the value stored at ith node at the jth level and ^ is the raise to a power operator.
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 2^j.
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:
location 0 1 2 3 4 5 6
node 0 | 0 1 | 0 1 2 3
level 0 | 1 | 2
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*(b^j-1)
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
gives the result 2^k.
Using this the storage mapping function:
location = node + 2^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 ab about what goes where.
this.Nodes =new Array();
Next we need a basic set and get functions for a 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:
and to retrieve a value you would use something like: