Information Technology Reference
In-Depth Information
Firstly, we recall the following proposition, which can be easily shown by induc-
tion on the number of nodes.
−
Proposition 7.15.
In a complete binary tree with n leaves there are n
1
internal
−
nodes (that is,
2
n
1
nodes).
The following proposition is an easy consequence of the the previous one, because
any tree has a number edges equal to the number of its nodes minus one.
Proposition 7.16.
In a complete binary tree with n leaves there are
2
n
−
2
edges.
A
Unrooted Branches
(UB) is a unrooted trees where any internal node has degree
3. Given a BT, if we remove its root, by collapsing the two edges exiting from it in
one edge, we get a UB (see 7.25). Therefore, the following proposition holds.
Proposition 7.17.
Any BT can be transformed into a UB with the same number of
leaves and a number of edges decreased by one.
(
)
In order to obtain the enumeration of the set
BT
n
of BT with
n
leaves, we consider
(
)
(
)
the set
UB
n
of UB with
n
leaves. For simplicity we continue to denote by
BT
n
and
UB
(
n
)
the cardinalities of these sets, respectively.
Fig. 7.25
Transforming a binary tree (top) in an unrooted branch (bottom) with the same
leaves
Proposition 7.18.
The number BT
(
n
)
of rooted complete binary trees with n leaves
is given by
(
2
n
−
3
)
UB
(
n
)
where UB
(
n
)
is the number of unrooted branchings with
n leaves.
