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
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 13.Alberi Binari di Ricerca. Cancellazione di un nodo


Alberi binari di ricerca (ABR)

Un albero binario di ricerca (ABR) è 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.


Riepilogo della precedente lezione in aula

Nella lezione precedente abbiamo studiato come:

  • Definire un ABR tramite struct
  • Creare un ABR con un unico nodo o come unione tramite un nuovo nodo radice di due ABR preesistenti;
  • Controllare se un ABR è vuoto;
  • Controllare che un albero è un ABR;
  • Ottenere il valore della radice di un albero;
  • Avere il puntatore al figlio sx/dx di un ABR.
  • Stampare il contenuto di un albero tramite una visita
  • Ricercare un dato elemento o il minimo di un ABR

Sommario

In questa lezione valuteremo come cancellare un nodo da un ABR.

Cancellazione

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

  1. Albero vuoto: non viene realizzata alcuna cancellazione;
  2. L’elemento el < radice albero: la cancellazione va effettuata nel sottoalbero sinistro; elimina(radice->sinistro,el);
  3. L’elemento el > radice albero: la cancellazione va effettuata nel sottoalbero destro; elimina(radice->destro,el);
  4. L’elemento el==radice albero. Si considerano i seguenti casi:
    1. La radice è una foglia.
    2. Il nodo ha un sottoalbero non vuoto e l’altro vuoto.
    3. 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 è scorretta perchè porta troppo in avanti il puntatore da non permette la modifica il campo dx o sx del nodo padre.
  • Una soluzione è quella di utilizzare una funzione che ritorni un puntatore a una struttura ad albero (come proposto per le liste). Il valore ritornato, opportunamente gestito nelle chiamate ricorsive, permetterà di modificare l’ABR nel modo voluto.
  • Un’altra soluzione è quella di utilizzare il metodo del puntatore a puntatore. Questo è da preferirsi quando si ha a che fare con funzioni che devono modificare più oggetti.
  • Di seguito mostriamo la seconda soluzione.

Come usare il puntatore a puntatore

Un ABR con doppio puntatore sarà definito in figura.

L’ABR sarà referenziato con una cella contiene un indirizzo (rad) di una cella contenente un indirizzo (*rad) di una cella in cui è memorizzato la radice dell’albero. Si veda per es. la seconda figura.

Una chiamata ad una funzione “elimina(**rad, el)”, con el intero da eliminare, passa alla funzione il riferimento alla cella con indirizzo 2000. Una modifica alla radice dell’ABR, modificherà anche il contenuto di questa cella.


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