Information Technology Reference
In-Depth Information
Decoding sequences into trees
Given a sequence
,
,...
α
over a set
X
of
n
nodes numbered by 1
2
n
,thefol-
lowing procedure provides another sequence
of nodes over
X
.Let
j
be the
smallest index of the nodes of
X
which does not occur in
β
α
, then put
β
=(
x
j
)
and update
α
, by removing its first element.
For
i
1
do
:
let
j
be the smallest index of the nodes which do not occur in
=
2
,...,
n
−
α
and do not
already occur in
β
, then update
β
by adding to it
x
j
as last element, and update
α
by removing its first element.
done
.
The set of pairs of elements having the same positions in
α
and
β
, respec-
tively, provide the edges of the tree encoded by the sequence
α
.
Figure 7.23 shows a tree and the sequence
(
1
,
4
,
4
,
3
,
5
,
5
,
3
,
1
)
encoding the tree.
The sequence
(
2
,
6
,
7
,
4
,
8
,
9
,
5
,
3
)
is generated by the above procedure applied to
(
1
,
4
,
4
,
3
,
5
,
5
,
3
,
1
)
. In fact, the pairs of elements having the same positions in
(
1
,
4
,
4
,
3
,
5
,
5
,
3
,
1
)
and
(
2
,
6
,
7
,
4
,
8
,
9
,
5
,
3
)
provide the edges of the tree encoded
by
(
1
,
4
,
4
,
3
,
5
,
5
,
3
,
1
)
.
Fig.
7.23
The
tree
over
nodes
{
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
}
is
encoded
by
the
sequence
(
,
,
,
,
,
,
,
)
(
,
,
,
,
,
,
,
)
1
4
4
3
5
5
3
1
. This sequence with the sequence
2
6
7
4
8
9
5
3
returns the tree
Cayley's formula easily follows from the previous encoding. In fact, given
n
nodes, there are
n
n
−
1
1. It could be considered
counterintuitive that a two-dimensional structure as a tree could be encoded by a se-
quence. However, at a more careful analysis, we realize that the encoding sequence
of a tree is based on a previous ordering of its nodes, therefore, in more precise
distinct sequences of length
n
−
