Cancellazione di un nodo di un albero
La cancellazione di un nodo di un albero presuppone che una volta avvenuta venga mantenuta l’integrità dell’albero e che nel caso si tratti di un BST sia salvaguardata anche la relazione tra i vari nodi.
Cancellazione in un albero non ordinato
Nel caso degli alberi non ordinati è necessario preoccuparsi solo di mantenere l’integrità dell’albero non essendoci relazioni d’ordine tra i vari nodi.
E’ pertanto sufficiente scorrere l’albero per trovare il nodo da cancellare, conoscendo ad esempio la chiave. Se viene trovato, è sufficiente ricercare una foglia dell’albero, non importa quale, sostituire la chiave della foglia a quella da cancellare e quindi eliminare la foglia.
Nel lucido seguente è mostrato un esempio.
Cancellazione in un albero non ordinato (segue)
Esempio
Nel caso dell’albero di figura si vuole canecllare il nodo con chiave 30. Poichè la chiave esiste è allora sufficiente cercare una foglia, ad esempio quella con chiave 28, sostituire questa chiave a quella da cancellare e eliminare la foglia.
Cancellazione in un albero ordinato BST
Nel caso degli alberi ordinati è necessario preoccuparsi non solo di mantenere l’integrità dell’albero ma anche la relazione d’ordine esistente tra i vari nodi.
Vanno distinti tra casi:
- Il nodo da cancellare è una foglia.
- Il nodo da cancellare ha un solo figlio.
- Il nodo da cancellare ha sia un sotto albero destro che un sotto albero sinistro.
Cancellazione in un albero ordinato BST (segue)
Nella figura seguente si mostrano i primi due casi che sono di semplice soluzione.
Infatti se il nodo è una foglia è sufficiente eliminarla ponendo a NULL il puntatore del parent (padre) che la riguarda. Si vedano gli esempi (a) e (b).
Nel caso in cui il nodo da cancellare ha un solo sottoalbero, è allora sufficiente legare la radice del sotto albero a cui punta il nodo da cancellare, con il parent che punta al nodo. In questa maniera, ovviamente si preserva l’ordine. Si vedano gli esempi (c) e (d).
Cancellazione in un albero ordinato BST (segue)
Eliminazione di un nodo su un BST
Cancellazione in un albero ordinato BST (segue)
Nel caso in cui il nodo da cancellare abbia sia il sotto albero di sinistra che quello di destra allora si procede come segue:
si sostituisce alla chiave del nodo da cancellare o la chiave del nodo di valore maggiore del suo sottoalbero di sinistra o quella di valore minore del suo sotto albero di destra.
Se questo nodo ha a sua volta un sottoalbero di destra o uno di sinistra ci si comporta nei suoi confronti come se fosse un nodo da cancellare e quindi si esegue la stessa procedura sopra descritta.
Cancellazione in un albero ordinato BST (segue)
Nell’esempio di figura si sostituisce alla chiave 30 del nodo individuato, la chiave del nodo 35 che è la più piccola del suo sottoalbero destro.
Cancellazione in un albero ordinato BST (segue)
Analizziamo il problema della riorganizzazione dell’albero una volta eliminato un nodo.
Caso a- il nodo (QQQ) da eliminare ha il sotto albero sinistro vuoto. Nell’esempio si usa la stessa nomenclatura che verrà utilizzata in seguito nel codice.
Il puntatore che da Parent prima puntava a Candidate ora acquista il valore del puntatore a RRR ottenuto in questo caso da Candidate->right
Cancellazione in un albero ordinato BST (segue)
Ad esempio per eliminare il nodo con chiave Riccardo con il procedimento precedente si passa dall’albero (A) all’albero (B).
Caso b- il nodo da eliminare ha il sotto albero destro vuoto.
La procedura è analoga alla precedente.
Cancellazione in un albero ordinato BST (segue)
// Pseudo Codice – casi (a) (b)
if (Candidate->left==NULL)
LegaPadre(Candidate, Candidate ->right, Padre, Tree)
else
if (Candidate->right==NULL))
LegaPadre(Candidate, Candidate ->left, Padre, Tree)
else
continua a riorganizzare l’albero
Cancellazione in un albero ordinato BST (segue)
La procedura LegaPadre ha un prototipo del seguente tipo:
void LegaPadre(Tnodo OldChild, Tnodo NewChild, Tnodo Padre, Tnodo &Tree)
{riorganizza l’albero BST dopo l’eliminazione di un nodo}
Dove:
OldChild = è il puntatore al nodo da cancellare
NewChild = è il puntatore al nodo al nodo a cui il Padre deve collegarsi
Padre = è il padre del nodo da cancellare
Tree = è la radice dell’albero nel quale si deve operare la cancellazione
per il caso di nodo da cancellare, avente con un solo sottoalbero, può codificarsi
come segue.
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Per eliminare il nodo la cui chiave è stata spostata si ricorre alla seguente procedura:
void DelTNode(int KeyValue, Tnodo &Tree, bool &Done)
{elimina il nodo con chiave KeyValue ricostruendo la struttura BST.
Se il Nodo non esiste Done risulta False}
di cui mostriamo lo pseudo codice nella successiva diapositiva.
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Allo pseudo codice precedente segue il codice nella prossima diapositiva.
I commenti al codice chiariscono il suo funzionamento.
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Analogamente al caso precedente illustriamo nel lucido seguente la procedura che serve ad individuare il puntatore del nodo la cui chiave andrà a sostituire quella da cancellare e che sarà poi eliminata.
I commenti al codice chiariscono il suo funzionamento.
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Nella procedura precedente viene richiamata la procedura Cerca (Tree, KeyValue, TNode, Padre) che nell’albero Tree ricerca la chiave KeyValue e restituisce il puntatore al nodo con questa chiave, se c’è, oppure NULL se non c’è. Fornisce inoltre anche il puntatore del padre del nodo cercato.
Di seguito si mostra lo pseudo codice e quindi il codice.
I commenti al codice chiariscono il suo funzionamento.
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Di seguito si mostra, con una animazione il valore assunto dalle diverse variabili man mano che l’algoritmo di cancella procede per il caso mostrato.
Cancellazione in un albero ordinato BST (segue)
Cancellazione in un albero ordinato BST (segue)
Esempi di cancellazione
Cancellazione in un albero ordinato BST (segue)
Cancellare la radice
Esercizio
Sia assegnato un albero binario, scrivere un algoritmo tale che sposti ogni figlio sinistro nel corrispondente figlio destro e viceversa.
Esercizio (segue)
Mostra codiceAllegato: alberi vari
Per utilizzare il codice Allegato: alberi vari è necessario costruire un file di nome TREE11 .txt in cui vanno inserite le chiavi dei singoli nodi dell'albero che si vuole costruire
Esercizio (segue)
Mostra codice
