Alberi Binari

Visite: 1639

Gradito:

[ Picolo appunti ]

Leggi anche appunti: Il concetto di infinito Il concetto di infinito Il concetto di infinito è sicuramente uno dei concetti Il teorema degli incrementi finiti(o di Cauchy) Il teorema degli incrementi finiti(o di Cauchy) Se F(x) e φ(x) Un nuovo postulato delle parallele UN NUOVO POSTULATO delle parallele Una trentina d'anni dopo la pubblicazione

Alberi Binari

Un albero binario può essere l'insieme vuoto o composto dalla tripletta T =(X, L, R), dove X è un nodo e L ed R sono 2 alberi binari disgiunti, nessuno de quali contiene X.

NB: è un albero ordinato, di ordine 2 (ogni nodo interno ha grado = 2).

NNB: un sottoalbero sinistro vuoto è diverso da un sottoalbero destro vuoto.

Alberi binari pieni: tutte le sue foglie sono allo stesso livello e ogni nodo interno ha 2 figli

foglie

m = 2^h - 1                   nodi interni

n = 2^{h + 1} - 1                nodi

h = log₂ (n + 1) - 1      altezza

NB: in generale si ha:             h + 1 < n < 2^{h + 1} - 1 log₂n < h < n - 1

Identità: occupano lo stesso spazio in memoria;

Uguaglianza: 2 oggetti hanno lo steso valore;

Isomorfismo: esiste una funzione f che fa corrispondere ogni elemento x della prima struttura X, ad un unico elemento y = f(x) della seconda struttura Y, cosicché ad ogni y I Y corrisponda un unico elemento x I X. 2 elementi x₁ e x₂ si dicono adiacenti in X se e solo se i corrispondenti f(x₁) e f(x₂) sono adiacenti in Y.

Alberi binari completi:può essere un albero binario pieno o una albero binario pieno ad eccezione di una porzione di foglie sul lato destro a livello più basso.

h + 1 < n < 2^{h + 1} - 1 h = log₂n

Corrispondenza tra un albero binario completo e un array:

1. il genitore del nodo memorizzato all'indirizzo i si trova all'indirizzo i/2;
2. il figlio di sinistra del nodo memorizzato in i si trova in 2i;
3. il figlio di destra del nodo memorizzato in i si trova in 2i + 1;

PS: Ciò che definisce un albero binario completo è la condizione per cui la corrispondenza con un array memorizza al suo interno tutti i nodi senza celle vuote.

Attraversamento

Per livelli:

inizializzare una coda;

mettere in coda la radice;

ripetere i passi da 4 a 7 fino a che la coda non è vuota;

togliere il nodo X dalla coda;

visitare X;

mettere in coda il figlio sinistro se esiste;

mettere in coda il figlio destro se esiste;

Pre ordine

visita la radice;

se il sottoalbero sinistro non è vuoto, attraversarlo in pre ordine;

se il sottoalbero destro non è vuoto, attraversarlo in pre ordine;

Post ordine

se il sottoalbero sinistro non è vuoto, attraversarlo in post ordine;

se il sottoalbero destro non è vuoto, attraversarlo in post ordine;

visita la radice;

Intra ordine

se il sottoalbero sinistro non è vuoto, attraversarlo in intra ordine;

visita la radice;

se il sottoalbero destro non è vuoto, attraversarlo in intra ordine;