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
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…
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.
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!
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
The tree is now a collection of nodes linked together. For example, this tree…
Will be represented as 7 instances of Node, 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).
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.
blog comments powered by Disqus