Representation - Practices

We can think of the memory of a computer as just a huge one dimensional array (a really huge one, indeed!). Now, look at the trees we have just drawn above. How would they fit into the memory of a computer? That looks like a tricky question, but the answer is not that hard. In fact we can come up not just with one, but actually two, different representations.

Representation 1… Using an Array

The first way to represent a tree is quite simple. Since computer memory can be thought of as a one dimensional array, let's represent the tree using a one dimensional array. Each node of the tree will be represented as an element of the array. The root of the tree will be at the very first location of the array. The rest of the nodes follow like reading the tree from top to bottom, and from left to right (just like you are reading this page).

So, for example, this tree..

 
Fig 3a. This tree…

Will end up looking like this…

Fig 3b. will be represented using this array

Pretty simple, huh? Problems occur, though, when there are gaps in the tree… For example, let's look at this tree…

 
Fig 4a. And this tree…

To represent it, we will have to waste some locations in the array, in order to represent the tree correctly. This is how the array will look. (Unused locations have been marked as 'X.' In real life, you can insert any invalid value to indicate an empty node)

Fig 4b. will be represented using this array

The first X (after the D) is for the missing right child of B. Other invalid elements are for the missing children of D, E and the children of the missing child of B. This gives us seven wasted nodes to represent a tree with eight nodes, which is not very good at all.

So, what is good about this representation? First, it is easy to navigate the tree. Given any node, it is easy to find its parent, and its two children. How? Let's assume the root of the tree is put at location 1 of the array. Now, if we have a node at location x, it is easy to show that its parent is at location x/2 (if x is odd, just ignore the fractional part), and its children are at locations x*2, and x*2+1.

Don't believe this? Take a good look at the previous tree. Let's look at node "C." This is a node in location three of the array. The parent of this node should be at location 3/2 which gives us 1 (we ignore the fractional part, as just mentioned). The node at location 1 is "A." "A" is indeed the parent of node "C." Now, again "C" was at location three, so its children should be at locations six and seven. The nodes at locations six and seven are "E" and "F," which are indeed the children of node "C." Now, take a moment to try the same thing on node "F." Did everything work out correct? Great. Let's move on.

Now, what is bad about this representation? Basically, if the tree is not dense enough, considerable memory gets wasted. Let's look at an extreme example. The eight node tree shown below requires an array of size 127. This is a serious memory. You can imagine that it gets even worse for bigger trees!

 
Fig 5. This is bad… really bad! Lots of memory gets wasted

The bottom line is, this representation is really good for very dense trees, but it gets really bad when the trees are not very dense. An example of when this representation is perfect, is when we have a heap. Heaps are special kinds of binary trees that are very dense (In fact, no memory gets wasted at all!). But, let's leave them for another time.

So what do we do when the tree is not dense enough? This calls for a different representation, namely, the linked representation.

Representation 2… Linked representation

Basically this representation shows the tree nearly as we see it on paper. We define a new class "Node" to hold the data of a single node, and we put two references to the two children of this node. When a node has no left child, or right child, we can set its reference to null.
So, if we define a class like this…

class Node
{
 int data; //or whatever
 Node left;
 Node right;
}

The tree is now a collection of nodes linked together. For example, this tree…

 
Fig 6a. Now, this tree…

Will be represented as 7 instances of Node, like this…

 
Fig 6b. could be represented using linked representation like this

Each node is represented by an instance of Node. Node has 3 members. Left (the small rectangle to the left), Data (the rectangle in the middle), and Right (the small rectangle to the right).

So, what is good about this representation? It doesn't waste much memory even when the tree is not dense enough. But there are drawbacks. There is some extra storage wasted, of course, because of all the extra references. Another problem is that, given a node, it is not easy to find its parent. (Some tweaks can be done to the representation to allow this, but that's another story).

Now, we know what a tree is, and we know how to represent it. It's time to see trees in action. Let's head directly to our first example, the dictionary.