148 8. Trees
8.4 How to Store Trees.......................
Suppose that you want to store a labeled tree, say the tree in Figure 8.4,
in a computer. How would you do this? Of course, the answer depends on
what you need to store the tree for, what information about it you want
to retrieve and how often, etc. Right now, we are concerned only with the
amount of memory we need. We want to store the tree so that it occupies
the least amount of memory.
Let’s try some simple solutions.
(a) Suppose that we have a treeGwithnnodes. One thing that comes to
mind is to make a big table, withnrows andncolumns, and put (say) the
number 1 in thejth position of theith row if nodesiandjare connected
by an edge, and the number 0, if they are not. It will be convenient to place
the node labeled 0 last, so it corresponds to the 10th row and to the 10th
column:
0000010000
0001010001
0000000001
0100000000
0000010000
1100100000
0000000010
0000000010
0000001100
0110000000(8.1)
This method of storing the tree can, of course, be used for any graph (it
is called theadjacency matrixof the graph, just to mention its name). It is
often very useful, but at least for trees, it is very wasteful. We need one bit
to store each entry of this table, so this takesn^2 bits. We can save a little
by noticing that it is enough to store the part below the diagonal, since the
diagonal is always 0 and the other half of the table is just the reflection of
the half below the diagonal. But this is still (n^2 −n)/2 bits.
(b) We fare better if we specify each tree by listing all its edges. We can
specify each edge by its two endpoints. It will be convenient to arrange this
list in an array whose columns correspond to the edges. For example, the
tree in Figure 8.4 can be encoded by
789630266
992202415Instead of a table withnrows, we get a table just with two rows. We pay a
little for this: Instead of just 0 and 1, the table will contain integers between
0 andn−1. But this is certainly worth it: Even if we count bits, to write