La funzione Elimina viene utilizzata per eliminare il nodo specificato da un albero di ricerca binario. Tuttavia, dobbiamo eliminare un nodo da un albero di ricerca binario in modo tale che la proprietà dell'albero di ricerca binario non venga violata. Esistono tre situazioni in cui è possibile eliminare un nodo dall'albero di ricerca binario.
Il nodo da eliminare è un nodo foglia
È il caso più semplice, in questo caso sostituire il nodo foglia con NULL e liberare semplicemente lo spazio allocato.
Nell'immagine seguente stiamo eliminando il nodo 85, poiché il nodo è un nodo foglia, quindi il nodo verrà sostituito con NULL e lo spazio allocato verrà liberato.
Il nodo da eliminare ha un solo figlio.
In questo caso, sostituire il nodo con il suo figlio ed eliminare il nodo figlio, che ora contiene il valore da eliminare. Basta sostituirlo con NULL e liberare lo spazio allocato.
Nell'immagine seguente il nodo 12 è da eliminare. Ha un solo figlio. Il nodo verrà sostituito con il suo nodo figlio e il nodo 12 sostituito (che ora è il nodo foglia) verrà semplicemente eliminato.
Il nodo da eliminare ha due figli.
È un caso un po’ complesso rispetto ad altri due casi. Tuttavia, il nodo che deve essere eliminato viene sostituito ricorsivamente con il suo successore o predecessore in ordine finché il valore del nodo (da eliminare) non viene posizionato sulla foglia dell'albero. Al termine della procedura, sostituire il nodo con NULL e liberare lo spazio allocato.
Nell'immagine seguente è da eliminare il nodo 50 che è il nodo radice dell'albero. L'attraversamento in ordine dell'albero indicato di seguito.
6, 25, 30, 50, 52, 60, 70, 75.
sostituisci 50 con il suo successore in ordine 52. Ora, 50 verrà spostato sulla foglia dell'albero, che verrà semplicemente cancellata.
Algoritmo
Elimina (ALBERO, ARTICOLO)
Scrivi 'articolo non trovato nell'albero' ELSE IF ITEM DATA
Elimina(ALBERO->SINISTRA, OGGETTO)
ALTRIMENTI SE ELEMENTO > ALBERO -> DATI
Elimina(ALBERO -> DESTRA, ARTICOLO)
ALTRIMENTI SE ALBERO -> SINISTRA E ALBERO -> DESTRA
IMPOSTA TEMP = findLargestNode(ALBERO -> SINISTRA)
IMPOSTA ALBERO -> DATI = TEMP -> DATI
Elimina(ALBERO -> SINISTRA, TEMP -> DATI)
ALTRO
IMPOSTA TEMP = ALBERO
SE ALBERO -> SINISTRA = NULL E ALBERO -> DESTRA = NULL
IMPOSTA ALBERO = NULL
ALTRIMENTI SE ALBERO -> SINISTRA != NULL
IMPOSTA ALBERO = ALBERO -> SINISTRA
ALTRO
IMPOSTA ALBERO = ALBERO -> DESTRA
[FINE SE]
TEMP. LIBERA
[FINE SE]
Funzione:
void deletion(Node*& root, int item) { Node* parent = NULL; Node* cur = root; search(cur, item, parent); if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur- >right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? Cur- >left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } Node* findMinimum(Node* cur) { while(cur->left != NULL) { cur = cur->left; } return cur; }