Information Technology Reference
In-Depth Information
1.7
Trees and Hierarchies
A natural way to express a hypermultiset, built from some initial elements, is by
means of diagrams such as those given in Fig. 1.7. Each level of aggregation cor-
responds to a closed plane curve embracing the elements which are aggregated,
possibly occurring in many identical copies. Moreover, the 2-dimensional nature of
this kind of diagram represents adequately the lack of order among the components
inside each closed curve. The diagram at the bottom of Fig. 1.7 is a diagram of a
rooted tree
, a typical structure representing genealogies. The root is the node at
the top of the diagram (the origin of the genealogy), and each element that is the
parent
of some
child
node is
an internal node
(the root is an internal node), while
other nodes, called
leaves
, do not have child nodes, and the nodes having the same
parent are
sibling
nodes (some authors use the masculine designation ”father, son,
brother”, while others use the feminine designation ”mother, daughter, sister” in-
stead of ”parent, child, sibling”). Terms
ancestor
and
descendant
refer to nodes that
are the beginning and the end, respectively, of a chain of parent-child relationship
(another way of expressing a tree is by means of a
parent function
, assigning to any
node different from the root its parent node).
Life tree represents the hierarchical structure of classification of living organ-
isms. The tree of Fig. 1.8 (http://en.wikipedia.org/wiki/Phylogenetic
−
tree) is a life
evolution tree.
The trees of Fig. 1.9 show the difference between prebiotic and biotic trees. The
biotic tree has leaves connected to the Last Universal Common Ancestor by an un-
interrupted genealogical chain going from it down to the current living organisms.
Fig. 1.7
The membrane diagram of the multiset 3
[
2
a
+
b
]+
2
c
+
3
[
a
+
c
]
on the top, and the
tree diagram of the same multiset on the buttom
