Albero binario - dimostrazione per induzione

kayvaan
Ciao a tutti
potreste mostrarmi una dimostrazione per induzione per provare che un albero binario completo abbia
$n = 2l-1$ vertici? Dove $l$ sono le foglie. il caso base è banale. Ma come verifico l'ipotesi induttiva?
Spero di aver postato nella sezione giusta.

[xdom="Seneca"]Sposto la discussione in Algebra.[/xdom]

Risposte
bestiedda2
"kayvaan":
Ciao a tutti
potreste mostrarmi una dimostrazione per induzione per provare che un albero binario completo abbia
$n = 2l-1$ vertici? Dove $l$ sono le foglie. il caso base è banale. Ma come verifico l'ipotesi induttiva?
Spero di aver postato nella sezione giusta.

[xdom="Seneca"]Sposto la discussione in Algebra.[/xdom]


non hai un tuo tentativo? Con un disegno è più facile trovare la soluzione...

gpicchiarelli
La soluzione consiste nel dimostrare che $l = 2^(h+1)$
e poi di seguito sostituendo di dimostra per induzione che $n = 2^(h+1) - 1 $ dove $h$ è l'altezza dell'albero.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.