0
$\begingroup$

Might be an odd question but how is it that when you specify a tree using an adjacency list emphasizing leafs first you state only need state 0 or 1 parent for each node but when you define a tree in another matter, emphasizing the root first (moving inward), you must specify any number of child nodes for each node? Seems like the second method requires more data to specify the same tree than the first. Or perhaps that’s not the case for all trees?

$\endgroup$
  • 2
    $\begingroup$ What is the reason for having different representations of any kind of data? $\endgroup$ – Dave Clarke May 13 '14 at 11:41
1
$\begingroup$

Not all is space/computing complexity. Trees are useful for modelling problems (and their solutions). Say you have several alternative courses of action, and after deciding on one of them, you get offered another selection, and do on. This is naturally modelled by a tree with a root (your starting point) and branch points where the number of decendents aren't necessarily the same. The decendents aren't even in any particular order (you can set up a list of the alternatives, but that is an artificial, externally imposed, order). This is your conceptual model, which you probably would represent concretely as a rooted, ordered tree (children are in a particular, arbitrary, order), and you might decide to store that as a linked data structure of nodes with first child, next sibbling pointers.

$\endgroup$
1
$\begingroup$

You're right. You need less space to save a tree with an adjacency list. But (like Dave Clarke's comment already says) there are more interesting fields, not only the space-complexity. Sometimes it is useful to spend more space to reduce for example the time-complexity of a problem. An easy example makes that point clear: If you represent your tree by saving the children of each node, you can compute the children of a given point in constant time (just looking which children are saved for the particular node). If you otherwise save the parent of each node, then you have to check every node in your tree (except the given point) to compute the children of a given node. In the first case you need more space and less time. In the second case you need less space, but more time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy