Nodi interni in un albero binario semi-completo
per gli studenti di informatica o per chi sa cos'e' un BST.
Sia $A$ un albero semicompleto (ovvero l'ultimo livello $i$ ha $2^(i-1)$ nodi). Dimostrare che il numero di nodi interni di $A$ e' $(n-1)/2$
Sia $A$ un albero semicompleto (ovvero l'ultimo livello $i$ ha $2^(i-1)$ nodi). Dimostrare che il numero di nodi interni di $A$ e' $(n-1)/2$
Risposte
vabbe' non ha riscosso molto successo... ad ogni modo questa era la mia soluzione... :
sia $h$ l'altezza dell'albero, per induzione su $h$ si puo' dimostrare che il numero di nodi interni di $A$ e' $n_{i} = \sum_{k=0}^{h-2} 2^{k} + 2^{h-1}/2 = 2^{h-1} - 1 + 2^{h-1}/2 = (3*2^{h-1})/2-1$ (1) . Adesso se $A$ ha $n$ nodi abbiamo che $n =\sum_{k=0}^{h-1}2^{k} + 2^{h}/2 = 2^{h}-1 + 2^{h}/2 = (3*2^{h})/2 -1$ dunque $2^{h} = 2/3*(n+1)$ da cui $h = log_{2}2/3*(n+1)$ (2)
Sostituendo (2) in (1) abbiamo $n_{i} = (n+1)/2 -1 = (n-1)/2$
sia $h$ l'altezza dell'albero, per induzione su $h$ si puo' dimostrare che il numero di nodi interni di $A$ e' $n_{i} = \sum_{k=0}^{h-2} 2^{k} + 2^{h-1}/2 = 2^{h-1} - 1 + 2^{h-1}/2 = (3*2^{h-1})/2-1$ (1) . Adesso se $A$ ha $n$ nodi abbiamo che $n =\sum_{k=0}^{h-1}2^{k} + 2^{h}/2 = 2^{h}-1 + 2^{h}/2 = (3*2^{h})/2 -1$ dunque $2^{h} = 2/3*(n+1)$ da cui $h = log_{2}2/3*(n+1)$ (2)
Sostituendo (2) in (1) abbiamo $n_{i} = (n+1)/2 -1 = (n-1)/2$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo