Newsgroup: it.scienza.informatica
Titolo: Alberi binari, nodi interni esterni e mediani

 -- 
http://www.mascanc.net/~masi
... They say jump, you say how high ... 

 Percentuale di nodi mediani (circa): 17%
Personalmente non ho capito, ho bisogno di ulteriori spiegazioni:
1. Su quali alberi binari hai fatto le statistiche?
2. Cosa intendi per nodi interni, esterni, mediani?
-- 
Ciao
Claude

 
Nodi interni: hanno due puntatori, i nodi esterni sono le foglie, 
i nodi mediani hanno solo un puntatore (altro nil).
:-)


 i nodi mediani hanno solo un puntatore (altro nil).
In tal caso le statistiche che hai fatto non hanno molto significato.
I casi sono due: l'albero è bilanciato oppure non lo è. Se l'albero non
è bilanciato la sua forma dipende in tutto e per tutto dall'ordine in
cui inserisci i dati. Non dipende per nulla dalla struttura dell'albero
in se. Le statistiche che hai fatto sull'albero sono in realtà
statistiche sull'ordine dei dati (e a questo punto tanto vale farle
direttamente su questi).
Se invece l'albero è bilanciato la sua struttura è perfettamente
prevedibile ogni 2^k-1 elementi (nelle formule considero l'elevamento a
potenza come prioritario rispetto alla somma per cui 2^k-1 va letto come
(2^k)-1 e non come 2^(k-1)). E' anche conosciuta per numero di elementi
inferiore o superiore di 1 rispetto a questo. Per tutti i casi intermedi
è per buona parte conosciuta e per il resto ... dipende dall'ordine di
inserimento dei dati. E in questo torniamo a statistiche sui dati e non
sull'albero. Usando la tua nomenclatura le formule sono:
Se gli elementi contenuti sono 2^k abbiamo:
i nodi interni sono : 2^(k-1)-1
i nodi esterni sono : 2^(k-1)
i nodi mediani sono : 1
Se gli elementi contenuti sono 2^k-1 abbiamo:
i nodi interni sono : 2^(k-1)-1
i nodi esterni sono : 2^(k-1)
i nodi mediani sono : 0
Se gli elementi contenuti sono 2^k-2 abbiamo:
i nodi interni sono : 2^(k-1)-2
i nodi esterni sono : 2^(k-1)-1
i nodi mediani sono : 1
Se gli elementi contenuti sono in un numero compreso fra 2^k e 2^(k+1)-2
abbiamo:
i nodi interni sono : minimo 2^(k-1)-2 massimo 2^k-2
i nodi esterni sono : minimo 2^(k-1) massimo 2^k-1
i nodi mediani sono : minimo 1 massimo 2^(k-1)
in altre parole partendo da un livello di riempimento di 2^k-1 la cui
forma è certa (vedi sopra), man mano che si inseriscono i successivi 2^k
elementi succederà che i 2^(k-1) nodi esterni diventeranno dapprima dei
nodi mediani e quindi dei nodi interni mentre i nuovi 2^k nodi che
inserisci diverranno nodi esterni. In che ordine avvengono questi
mutamenti dipende dall'ordine di inserimento dei dati. Ma puoi avere
alcune certezze. Fra cui lo stato al primo e all'ultimo passaggio (vedi
infatti sopra). E anche una relazione fra il numero di nodi mediani e il
numero di nodi esterni e interni. In particolare sai che in un albero
bilanciato questa regola vale sempre:
Se gli elementi contenuti sono 2^k-1+n con n compreso fra 0 e 2^k e se
il numero di nodi mediani è m, che sarà ovviamente compreso fra 0 e
2^(k-1) avrai:
i nodi interni sono : minimo 2^(k-1)-1 massimo 2^(k-1)-1(n-m)/2
i nodi esterni sono : minimo 2^(k-1) massimo 2^(k-1)+(n-m)/2
i nodi mediani sono : m (ovviamente)
Nota che m sarà sempre tale che n-m è un numero pari.
Nota anche che questa regola è soddisfatta sempre (anche nei tre casi
particolari detti sopra).
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

 
Ho trovato un articolo interessante sul computer journal del 1992 Issue 4
del Professor Renzo Sprugnoli.
Non ricordo bene il link, ma con una semplice ricerca su google dovrebbe
essere reperibile.
Appena ho capito posto un piccolo riassunto.
