Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 11.Alberi Binari di Ricerca


Alberi

L’albero è un tipo astratto di dato utilizzato per rappresentare relazioni gerarchiche tra oggetti.


Alberi binari

Un albero binario può essere facilmente rappresentato in modo ricorsivo. Infatti, un albero

  • è un oggetto vuoto (cioè è un insieme vuoto di nodi); oppure
  • è formato da un nodo A (chiamato radice) e da due sottoalberi, a loro volta alberi binari, chiamati rispettivamente sottoalbero sinistro e sottoalbero destro.

Rappresentazione di un albero binario

Per rappresentare un albero binario si puo usare la seguente struttura ricorsiva:


Primitive sugli alberi binari

Per controllare se un nodo è vuoto possiamo usare la seguente funzione (vedi figura):

Per sapere il valore di un nodo possiamo usare la seguente funzione che ritorna 0 se l’albero è vuoto, altrimenti memorizza nella variabile val il valore del nodo


Altre Primitive

Per avere il puntatore al figlio sinistro (destro) di un nodo (vedi figura):

Per costruire un nodo (vedi figura):


Visita di un albero binario

Oltre alle operazioni primitive, si definiscono delle operazioni di visita ovvero di analisi dei nodi di un albero in deteminato ordine.

Di seguito analizziamo le seguenti visite di un albero:

  • Visita in Preordine
  • Visita in Ordine
  • Visita in Postordine

Visita in Preordine

Nella visita in Preordine, se l’albero non è vuoto:

  • Si analizza la radice dell’albero;
  • Si visita in preordine il sottoalbero sinistro;
  • Si visita in preordine il sottoalbero destro.

Nella visita in preordine del precedente albero i nodi verrebbero visitati nel seguente ordine: 1, 2, 3, 4, 5, 6, 7


Visita in Ordine

Nella visita in ordine, se l’albero non è vuoto:

  • Si visita in ordine il sottoalbero sinistro;
  • Si analizza la radice dell’albero;
  • Si visita in ordine il sottoalbero destro.

Nella visita in ordine del precedente albero i nodi verrebbero visitati nel seguente ordine: 3, 2, 4, 1, 6, 5, 7


Visita Postordine

Nella visita in postordine, se l’albero non è vuoto:

  • Si visita in postordine il sottoalbero sinistro;
  • Si visita in postordine il sottoalbero destro;
  • Si analizza la radice dell’albero.

Nella visita in ordine del precedente albero i nodi verrebbero visitati nel seguente ordine: 3, 4, 2, 6, 7, 5, 1


Codice per la visita di un albero


Alberi binari di ricerca

Un albero binario di ricerca è un albero binario in cui per ogni nodo dell’albero N tutti i nodi del sottoalbero sinistro di N hanno un valore minore o uguale di quello di N e tutti i nodi del sottoalbero destro hanno un valore maggiore di quello del nodo N.

Il vantaggio principale di tale organizzazione è nella ricerca.

Ogni volta che bisogna ricercare un elemento, il confronto del valore di un nodo dell’albero permette di eliminare dalla fase di ricerca o il sottoalbero corrente di destra o quello di sinistra.


Ricerca in un albero binario di ricerca

Per trovare un numero R si procede nel seguente modo:

  • Se l’albero è vuoto l’elemento non è presente;
  • Se la radice dell’albero == R l’elemento è stato trovato;
  • Se la radice dell’albero > R la ricerca viene condotta nel sottoalbero sinistro;
  • Altrimenti la ricerca viene condotta nel sottoalbero destro;

La ricerca può essere realizzata mediante una funzione ricorsiva che nei casi 3 e 4 invoca se stessa.


Ricerca in un albero binario di ricerca

Versione iterativa della ricerca


Ricerca in un albero binario di ricerca

Versione ricorsiva della ricerca


Inserimento di un nuovo nodo in un ABR

  • Se l’albero è vuoto, viene creato un nuovo nodo.
  • Se l’elemento è minore o uguale alla radice dell’albero, l’inserimento va fatto nel sottoalbero sinistro.
  • Se l’elemento è maggiore o uguale alla radice dell’albero, l’inserimento va fatto nel sottoalbero destro.

Inserimento di un nuovo nodo in un ABR


Inserimento di un nuovo nodo tramite l’uso di puntatori a puntatori


Ricerca minimo in un ABR

Se il sottoalbero sinistro è vuoto, il minimo è la radice.

Altrimenti il minimo è da cercare nel sottoalbero sinistro.


Cancellazione

Nella cancellazione di un elemento el da un albero bisogna distinguere i seguenti casi:

Albero vuoto: non viene realizzata alcuna cancellazione;

  • L’elemento el < radice albero: la cancellazione va effettuata nel sottoalbero sinistro;

elimina(radice->sinistro,el);

  • L’elemento el > radice albero: la cancellazione va effettuata nel sottoalbero destro;

elimina(radice->destro,el);

  • L’elemento el==radice albero. Si considerano i seguenti casi:

La radice è una foglia:

  • Il nodo ha un sottoalbero non vuoto e l’altro vuoto.
  • Il nodo ha entrambi i sottoalberi non vuoti.

Primo caso

La radice è una foglia: viene eliminata liberando la memoria del nodo radice


Secondo Caso

Se il sottoalbero destro è vuoto:

  • il nodo figlio del nodo padre (10) di el (7) diventa il nodo figlio di el (4)

Viene eliminato il nodo el (7).


Terzo Caso

Il sottoalbero destro e sinistro del nodo el sono non vuoti:

  • viene ricavato il minimo (12) del sottoalbero destro;
  • il minimo (12) viene copiato nel nodo el (10);
  • viene eliminato il minimo (12) del sottoalbero destro.

Codice per la cancellazione (NO)


Osservazioni

Il codice precedente, non cancella efficacemente un nodo perchè all’atto della cancellazione “free(radice); radice=NULL;” deallochiamo effettivamente la memoria per il nodo da cancellare, ma il nodo padre di quest’ultimo continuerà a puntare ad una locazione di memoria reale, che non è NULL.

La funzione non è corretta perchè porta troppo avanti il puntatore, per cui non abbiamo più la possibilità di modificare il campo destro o sinistro del nodo padre.

Una soluzione è forzare la modifica del nodo padre utilizzando una variabile di comodo.

Un’altra soluzione è quella di utilizzare il metodo del puntatore a puntatore.

Di seguito mostriamo entrambe le soluzioni.

Codice per la cancellazione con variabile di comodo “foglia”


Codice per la cancellazione con variabile di comodo “foglia”


Uso di puntatori a puntatori


Uso di puntatori a puntatori


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion