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 » 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