Information Technology Reference
In-Depth Information
Fig. 7.26
Increasing UB leaves. Top: a minimal UB; Middle: an UB where the left leaf edge
of the top UB is replaced by a minimal UB; Bottom: an UB where the internal edge of the
middle UB is replaced by a minimal UB
Proof.
From the previous propositions it follows that any BT with
n
leaves has
(
edges. Moreover, from each UB a BT, with the same
number of leaves can be obtained by de-collapsing one of its edges.
2
n
−
2
)
nodes and
(
2
n
−
3
)
Proposition 7.19.
The number of rooted binary trees of n leaves is
BT
(
n
)=(
2
n
−
3
)
!!
Proof.
The minimal UB has one internal node connected with 3 edges to 3 leaves,
therefore
UB
1. We pass from a UB to another UB having a number of leaves
increased by one, by replacing one edge with a minimal UB (see, Fig. 7.26). For
example,
UB
(
3
)=
, because an UB with 3 leaves has
3 edges, and an UB with 4 leaves has 5 edges. From Propositions 7.16 and 7.17, we
know that a UB of
n
(
4
)=
3
UB
(
3
)
,and
UB
(
5
)=
5
UB
(
4
)
−
1 leaves has 2
(
n
−
1
)
−
3 edges.