 |
|
| Appunti scientifiche |
|
|
|
| Appunti scientifiche |
|
| Visite: 1725 | Gradito: |   [ Picolo appunti ] |
Leggi anche appunti:I Quadrati magiciI Quadrati magici Introduzione Nella matematica da Spazi vettorialiSPAZI VETTORIALI Siano K un campo e V un insieme. Diremo che V e` uno spazio Formule matematicaFormule matematica Geometria Analitica La retta: » equazione |
 |
 |
Alberi
Organizzazione gerarchica, con elementi successori (figli), predecessori (padri) e con un unico elemento di partenza detto radice.
Definizione ricorsiva: un albero può essere vuoto o composto dalla coppia T = (X, S), dove X è un nodo e S un insieme di alberi disgiunti nessuno dei quali contiene X (sottoalberi).
Albero s Ø | <X, S> Se T s <X, >, cioè ho un albero che non ha sottoalberi (nodo senza figli), allora si ha un nodo foglia, altrimenti il nodo si dice interno.
Proprietà:
cammino: sequenza di nodi adiacenti a 2 a 2 lunghezza = n° di coppie adiacenti.
alberi aciclici: nessun cammino può contenere più volte lo stesso nodo.
cammino radice: cammino da nodo a radice ogni nodo in un albero ha un solo cammino radice i, se un nodo appartiene ad un cammino radice di un altro si dice avo.
profondità di un nodo: lunghezza del suo cammino radice.
livello: insieme di tutti i nodi ad una data profondità.
altezza: profondità maggiore tra tutti i suoi nodi (n° di relazioni da percorrere per arrivare dal nodo alla radice)
NB: altezza di u albero unario = 0;
altezza di u albero vuoto = -1
lunghezza del cammino di un albero: somma delle lunghezze di tutti i cammini ottenute partendo dalla radice.
grado di un nodo: n° dei suoi figli (n° di sottoalberi che partono da esso).
ordine di un albero: massimo grado tra quello dei suoi nodi.
Un albero è pieno quando tutti i suoi nodi interni hanno lo steso grado e tutte le foglie sono allo sesso livello.
Due nodi sono collegati tra loro quando 1 è la radice e l'altro è la radice di un suo sottoalberi (relazione uno a molti, padre - figli).
Se T è una foglia #T = 1
Se T != radice ai #(Ti) la sommatoria di i va da 1 a n, il più 1 c'è perché bisogna considerare anche la radice, e la sommatoria indica tutti i sottoalberi
se T s <X, >
ai #(Ti) negli altri casi
#(T) =
Formula analitica di #(T) per un albero T di ordine d e altezza h:
dh + 1 - 1
d - 1
h + 1 < #(T) <
altezza di un albero di ordine d con n nodi: h = logd (nd - n + 1) - 1
X = radice X I Ti con i = 1, 2, ., m
Appartenenza di un nodo al l'albero: X I T T
Effettuiamo, ricorsivamente la ricerca in tutti sottoalberi, arrivando fino alle foglie (sottoalberi senza ulteriori sottoalberi), sulle quali si esegue il confronto x = radice. Se non l'abbiamo trovato nelle foglie, non c'è in tutto il sottoalbero superiore.
Funzione n(T)
Dato un albero restituisce l'insieme dei nodi in esso contenuti T s <X, S> S =
n(T) = U ai n(Ti) la sommatoria di i va da 1 a n
Definizione ricorsiva: se Ti = <X, >, allora n(Ti) = , altrimenti continua ad esplorare il sottoalbero.
Alberi ordinati: può essere vuoto o composto dalla coppia T s (X, S), dove X è un nodo e S una sequenza di alberi disgiunti, nessuno dei quali coerente X definizione analoga a quella di albero, con la sola differenza che i sottoalberi sono contenuti in una sequenza, non in un insieme.
Algoritmi di attraversamento di alberi ordinati
Per livelli
Inizializzare una coda;
Mettere in coda la radice;
Ripeti i passi dal 4 al 6 finché la coda non è vuota;
Togli il nodo X dalla coda;
Visita X;
Metti in coda tutti i figli di X , in ordine;
Per ordine
Visita la radice;
Esegui ricorsivamente un attraversamento
In pre ordine di ogni sottoalbero (prima
sinistra poi destra);
Post ordine
Esegui ricorsivamente un attraversamento in
in post orine di ogni sottoalbero (prima sinistra
poi destra)
Visita la radice;
|
| Appunti su: |
|
| Appunti Contabilita |  |
| Tesine Geografia |  |
| Lezioni Fisica |  |