Alberi BST e AVL

4.1 Alberi binari di ricerca (BST)

Queste sono delle varianti rispetto all’albero, descritto in modo molto sommario sopra (binario perché ogni nodo ha al massimo due figli, mentre l’albero può averne quanti se ne vuole).

4.1.1 Introduzione

La caratteristica principale dell’albero di ricerca è una condizione sulle chiavi (che hanno i figli).

Infatti questo albero binario di ricerca si può vedere come una implementazione della struttura astratta del dizionario. (che ricordiamo, è un struttura in cui a ogni nodo sono presenti due valori, una chiave (tute differenti) e un dato, e sono definite tre operazioni principali, possiamo vederla come interfaccia).

1. Al massimo due figli per nodo. (albero binario)
2. Il dizionario, quindi che ogni nodo abbia chiave.
3. I figli di sinistra hanno chiavi minori del genitore, a destra maggiore.

4.1.2 Prototipo

Possiamo definire alcune operazioni principali per l’albero di ricerca:

1. Le tre standard che sono presenti per il dizionario. (search, insert e delete)
2. Max e Min.
3. Predecessor e successor

Saltiamo le note di implementazione di questi algoritmi :D perché sono già triti e ritriti.

Una nota su predecessor:

Per l’operazione di delete abbiamo solamente considerato il caso di predecessor quando il nodo da considerare possedeva il figlio giusto.

Ma è possibile che non lo abbia, allora è molto simile, ma opposto (invece di scendere continuamente a destra, salgo continuamente a sinistra, con continuamente nel senso finché c’è ancora il nodo).

4.2 Alberi AVL

Questi sono alberi AVL (il cui nome deriva dal nome dei creatori, come RSA), alberi bilanciati secondo l’altezza dei sottonodi. La cosa buona è che avendo i bilanciamenti abbiamo un altezza logaritmica. in particolare possiamo dire che questi siano autobilancianti.

Introduciamo ora alcuni concetti importanti per comprendere il bilanciamento

4.2.1 il concetto di bilanciamento

Il fattore di bilanciamento

Cerchiamo di considerare un fattore di bilanciamento che si ottiene con

con h una funzione che mi ritorna l’altezza. (da notare che è l’altezza, non la funzione).

E l’altezza parte da 0

$$ \beta = fattore\_bilanciamento = h(sinistra) - h(destra) $$

Bilanciato in altezza

Consideriamo un albero bilanciato in altezza se $|\beta| \leq 1$

4.2.2 Altezza di un albero di fibonacci

L’albero di fibonacci è molto interessante da studiare dal punto di vista dell’altezza, infatti possiede il massimo sbilanciamento possibile

• Intuizione dell’albero (dalla costruzione puoi dimostrare la sua altezza in modo intuitiva)

  

• Numero di nodi nell’albero di fibonacci

  

• Conclusione sull’altezza

  

4.2.3 Operazioni elementari (rotazione e altezza)

Altezza

Possiamo definire un algoritmo per definire il fattore di bilanciamento e l’altezza di un sotto-albero (da sapere bene, fare attenzione ai casi null)

• Algoritmo (fattore bilanciamento e update altezza di un nodo)

  

Operazione di rotazione

Una rotazione è una operazione elementare di su un albero che mi riposiziona alcuni figli e genitori di un nodo.

• Esempi di rotazione semplice

  

• Pseudocodice della rotazione

  

4.2.4 Risoluzione degli sbilanciamenti

Possiamo catalogare le possibili tipologie di sbilanciamento in 2 macrogruppi di 2 (sono simmetrici destra e sinistra), questi saranno risolvibili tramite rotazioni, che, come vedremo, hanno la proprietà di diminuire l’altezza del nodo di rotazione di 1.

• Tipi di sbilanciamento

  

• Sbilanciamento di tipo SS (simmetrico DD)

  

• Sbilanciamento di tipo DS

  

• Pseudocodice per risolvere sbilanciamento

  

4.2.5 Note su inserimento e rimozione

Queste due operazioni sono le uniche che possono cambiare il bilanciamento dell’albero.

Si può dimostrare che l’inserimento sbilancia al massimo un nodo, per cui una unica rotazione è sufficiente per il tutto.

Mentre la rimozione può sbilanciare tutto il percorso fino la radice come questa operazione:

• Esempio