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:

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:
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.