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.
Search WWH ::




Custom Search