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 si 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.
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.
10
3
30
44
35
3
10
28
35
44
35
50
8
3
28
3
8
35
38
50
38
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.
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
riguardava. 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).
ELIMINAZIONE DI UN NODO SU UN BST
(b)
(a)
Parent
Parent
Old
Old
Old
(c)
New
Parent
(d)
Old
New
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.
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.
Nodo da cancellare
35
30
40
5
3
3
40
5
8
80
35
8
80
35
38
38
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.
Parent
Candidate
QQQ
Il puntatore che da Parent
prima puntava a Candidate ora
acquista il valore del puntatore
a RRR ottenuto in questo caso
da Candidate->right
RRR
left
right10
Analizziamo il problema della riorganizzazione dell’albero una
volta eliminato un nodo.
Caso a- il nodo (QQQ) da eliminare ha il sotto albero sinistro
Parent
Candidate
Eliminare
Riccardo
QQQ
Maria
RRR
Giulio
Dora
Anna
Sergio
Guido
Riccardo
Roberto
Toni
left
right
Caso b- il nodo da eliminare ha il sotto albero destro vuoto.
11
La procedura è analoga alla precedente.
Pseudo Codice
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
Parent
Candidate
QQQ
RRR
left
right
void LegaPadre(Tnodo OldChild, Tnodo NewChild, Tnodo Padre, Tnodo &Tree)
{riorganizza l’albero BST dopo l’eliminazione di un nodo}
void LegaPadre(Tnodo OldChild, Tnodo NewChild, Tnodo Padre, Tnodo &Tree)
//collega il nodo genitore con il sottoalbero connesso al nodo da cancellare
{
if (Padre==NULL)
//
{sostituiamo la root}
Tree= NewChild;
else
if (OldChild ==Padre->left)
Padre->left=NewChild; //
{sostituiamo al genitore il figlio sinistro}
else
Padre->right=NewChild; //
{sostituiamo al genitore il figlio destro}
}
Old
Parent
Old
New
New
Riassunto dei tipi di cancellazione
Old
Parent
New
Old
New
35
40
5
3
40
5
30
3
8
80
35
38
8
80
35
38
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}
Pesudo codice di DelTNode(Key, Tree, Done)
Cerca(Tree, Key, Candidato, Parent)
Fornisce il puntatore della Key da eliminare e
quello del suo genitore. Se Candidato=NULL
significa che la Key non c’è.
DammiChiave(Candidato, CandsKey)
Fornisce la chiave CandsKey di Candidato
if CandsKey<> Key
Se la chiave trovata e quella di partenza non
corrispondono CandsKey=NULL allora esci
else
Se il sottoalbero sinistro è
vuoto collega il genitore di
Candidato con la radice del
sotto albero destro. Se
Parent=NULL, cioè si vuole
cancellare la radice allora poni
in Tree la radice del sotto
albero destro.
Se il sottoalbero destro è vuoto
collega il genitore di
Candidato con la radice del
sotto albero sinistro. Se
Parent=NULL, cioè si vuole
cancellare la radice allora poni
in Tree la radice del sotto
albero sinistro.
Se nessuno dei due sotto
alberi è vuoto allora
chiama NuovoCandidato
15
void DelTNode(int KeyValue, Tnodo &Tree, bool &Done)
{ Tnodo Candidato;
// puntatore al nodo candidato per la cancellatura
Tnodo Padre;
// puntatore al genitore del nodo candidato}
int CandsKey;
Se il sottoalbero sinistro è vuoto
Done=true;
collega il genitore di candidato
Cerca( Tree, KeyValue, Candidato, Padre);
con la radice del sotto albero
DammiChiave(Candidato, CandsKey);
destro. Se Padre =NULL, cioè si
vuole cancellare la radice allora
if (CandsKey!=KeyValue)
poni in Tree la radice del sotto
Done=false;
Non c’è niente da cancellare
albero destro.
else
if (Candidato->left==NULL)
LegaPadre(Candidato, Candidato->right, Padre, Tree);
else
if (Candidato->right==NULL) {
LegaPadre(Candidato, Candidato->left, Padre, Tree);
}
else
NuovoCandidato(KeyValue, Candidato, Tree); Se il sottoalbero destro è vuoto
collega il genitore di candidato
KillTNode(Candidato);
con la radice del sotto albero
}
sinistro. Se Padre=NULL, cioè
Se nessuno dei due sotto
alberi è vuoto allora
chiama NuovoCandidato
si vuole cancellare la radice
allora poni in Tree la radice
del sotto albero sinistro.
void NuovoCandidato(int KeyValue, Tnodo &Candidato, Tnodo &Tree)
{
Tnodo Dummy; //variabile ausiliare per la chiamata a Cerca
Tnodo Padre; Tnodo OldCandidato;
Ricerca OldCandidate a partire dal suo
int CandsKey;
nodo destro con la conseguenza che trova
OldCandidato= Candidato;
il più piccolo di questo sottoalbero
(Candidato) (Dummy vale NULL)
Cerca(OldCandidate->right, KeyValue, Dummy, Candidato)
OldCandidato->key= Candidato->key;
Sostituisci il nodo da cancellare con Candidate
DammiChiave(Candidato, CandsKey);
Riprendi la chiave del nodo spostato
Cerca(OldCandidate->right, CandsKey, Dummy, Padre)
Cerca il più piccolo nodo del sottoalbero destro del nodo
spostato a partire dalla sua primitiva posizione
Se il nodo da cancellare è la root allora collega il sottoalbero
destro con la root
if (Padre==NULL)
LegaPadre(Candidato, Candidato->right, OldCandidato, Tree);
else
LegaPadre(Candidato, Candidato->right, Padre, Tree);
}
Collega il sottoalbero destro con il padre del nodo spostato
Cerca
Il padre dell’ultimo nodo esaminato
durante la ricerca di KeyValue
Cerca(Tree, KeyValue, TNode, Padre)
Obiettivo: cercare un cammino verso un determinato nodo dell’albero.
Se il nodo non esiste ritorna NULL. Se esiste ritorna il puntatore al nodo individuato e
quello di suo padre.
Pseudo Codice
Padre  NULL {la root non ha genitori}
TNode  Tree {la radice è il primo nodo esaminato}
DammiChiave(TNode, NodesKey)
{estrai la chiave del nodo in esame}
while ci sono altri nodi da esaminare AND non si è ancora trovato il nodo {
Padre  TNode
Tnode  il sottoalbero legato al KeyValue
DammiChiave(TNode, NodesKey)
{estrai la chiave del nodo in esame}
Tnode==NULL
NodesKey <> KeyValue
if (NodesKey > KeyValue)
TNode  radice del sottoalbero sinistro
else
TNode  radice del sottoalbero destro
void Cerca(Tnodo Tree, int KeyValue, Tnodo &Node, Tnodo &Padre)
{
int NodesKey;
Padre=NULL;
Node=Tree;
DammiChiave(Node, NodesKey) ;
while ((Node!=NULL) && (NodesKey!=KeyValue))
{
Padre=Node;
if (NodesKey>KeyValue)
Ricordarsi che DammiChiave nel
Node=Node->left;
caso trovi NULL ritorna una chiave
else
nulla.
Node=Node->right;
DammiChiave(Node, NodesKey);
}
};
void DammiChiave(Tnodo TNode, int &TheKey)
{ //ritorna il key field del nodo puntato da Tnode, se Tnode è
// NULL allora ritorna il valore di -100
if (TNode != NULL )
TheKey= TNode ->key;
else
TheKey= -100;
}
RICAPITOLANDO
Cancella il
nodo K
dell’albero T
DelTNode
(K,T,d)
Cerca in T il nodo
K. Il suo puntatore
è N e P è suo
padre
Verifica che a N
corrisponde la
chiave K
Cerco il più
piccolo a destra.
Parto a destra di K
cerco K e così
ottengo il più
piccolo, U
Cerca
(T,K,N,P)
Cerca
(N->right, K, D, U)
DammiChiave
(Uk,U)
DammiChiave
(K,N)
A partire dal sotto
albero destro di N,
cerco Uk per
avere suo padre P
La chiave non cè:
ESCI
N->left=NULL
NuovoCandidato
(K,N,T)
Cerca
(N->right, Uk, D, P)
N->right=NULL
LegaPadre
(N,N->right,P,T)
LegaPadre
(N,N->left,P,T)
Collega il padre
P con N->right e
cancella N
Collega il padre
P con N->left e
cancella N
NuovoCandidato
(K,N,T)
P=NULL
PNULL
LegaPadre
(U,U->right,N,T)
LegaPadre
(U,U->left,N,T)
RICAPITOLANDO
Pesudo codice di DeleteTNode(Key, Tree, Done)
Cerca(Tree, Key, Candidato, Parent)
Fornisce il puntatore della Key da eliminare e
quello del suo genitore. Se Candidato=NULL
significa che la Key non c’è.
DammiChiave(Candidato, CandsKey)
Fornisce la chiave CandsKey di Candidato
if CandsKey<> Key
Se la chiave trovata e quella di partenza non
corrispondono CandsKey=NULL allora esci
else
Se il sottoalbero sinistro è
vuoto collega il genitore di
Candidato con la radice del
sotto albero destro. Se
Parent=NULL, cioè si vuole
cancellare la radice allora poni
in Tree la radice del sotto
albero destro.
Se il sottoalbero destro è vuoto
collega il genitore di
Candidato con la radice del
sotto albero sinistro. Se
Parent=NULL, cioè si vuole
cancellare la radice allora poni
in Tree la radice del sotto
albero sinistro.
Se nessuno dei due sotto
alberi è vuoto allora
chiama NuovoCandidato
21
RICAPITOLANDO
Cerca(Tnodo Tree, int KeyValue, Tnodo &Node, Tnodo &Padre)
fornisce il puntatore Candidato del node che ha chiave Key e il puntatore Padre come padre
a
b
KeyValue=b
Node=P(b)
Padre =P(a)
LegaPadre(Tnodo OldChild, Tnodo NewChild, Tnodo Padre, Tnodo &Tree)
collega NewChild con Parent eliminando OldChild,
se Padre =NULL, cioè Old=Tree è la radice allora mette NewChild al posto di OldChild e
quindi di Tree
Padre
OldChild
NewChild
OldChild
NewChild
RICAPITOLANDO
NuovoCandidato(int KeyValue, Tnodo &Candidato, Tnodo &Tree)
Cerca nel sottoalbero destro di OldCandidato il nodo con chiave minima. Questa chiave va a
sostituire quella del nodo OldCandidato. Inoltre se il nodo con chiave minima ha sotto alberi
allora opera come precedentemente visto.
void NuovoCandidato(int KeyValue, Tnodo &Candidato, Tnodo &Tree)
{ Tnodo Dummy; //variabile ausiliare per la chiamata a Cerca
Tnodo Padre; Tnodo OldCandidato;
int CandsKey;
OldCandidato= Candidato;
Cerca(OldCandidate->right, KeyValue, Dummy, Candidato)
OldCandidato->key= Candidato->key;
DammiChiave(Candidato, CandsKey);
Cerca(OldCandidate->right, CandsKey, Dummy, Padre)
if (Padre==NULL)
LegaPadre(Candidato, Candidato->right, OldCandidato, Tree);
else
LegaPadre(Candidato, Candidato->right, Padre, Tree);
}
OldCandidato
35
40
5
3
8
80
35
Candidato
38
Cancellare il nodo 30
DelTNode(KeyValue, Tree, Done)
90
50
93
30
34
17
Cerca(Tree, KeyValue, Candidate, Parent)
DammiChiave(Candidate, CandsKey);
if CandsKey<> KeyValue Done=FALSE
else
95
if (Candidate->left==NULL)
LegaPadre(Candidate, Candidate-> Right, Parent, Tree)
else
if (Candidate->right==NULL))
98 LegaPadre(Candidate, Candidate-> Left, Parent, Tree)
else
NuovoCandidato(KeyValue, Candidate, Tree);
KillTNode(Candidate);
40
100
NuovoCandidato(KeyValue, Candidate, Tree)
P30
13
15
36
47
34
38
35
30
OldCandidate = Candidate
P40
Cerca( OldCandidate->right),
KeyValue,
34
OldCandidate->Key = Candidate^.Key;
34
34
CandsKey = Candidate->Key;
P40
NULL
P34
Dummy, Candidate)
P34
P36
Dummy, Parent);
Cerca(OldCandidate->right,
CandsKey,
if Parent = NULL THEN
LegaPadre(Candidate, Candidate ->right, OldCandidate, Tree)
else
P36
P34
P35
LegaPadre(Candidate, Candidate ->right, Parent, Tree);
24
Cancella un nodo
500
600
400
500
600
400
700
700
440
450
800
420
410
460
430 450
900
480
800
420
410
460
430
480
470
455
454
470
475
456
900
455
454
475
456
Cancella la root
500
400
550
600
400
600
550
564
564
553
553
566
558
558
556
555
556
559
557
566
555
559
557
ESERCIZIO
Sia assegnato un albero binario, scrivere un algoritmo tale che sposti ogni figlio
sinistro nel corrispondente figlio destro e viceversa.
A
A
B
D
C
E
G
C
F
B
F
H
H
E
D
G
void ScambiaNodi(Tnodo Tree)
{Tnodo Temp;
if (Tree != NULL)
{
ScambiaNodi(Tree->left);
ScambiaNodi(Tree->right);
Temp=Tree->left;
Tree->left= Tree->right;
Tree->right=Temp;
};
};
post-order
albvari
/* Sviluppare una funzione che, assegnato un albero binario T,
conti quanti nodi sinistri, hanno come unico figlio un nodo foglia. */
int contafigli(Tnodo A)
A
{
A->right
if (A==NULL)
A->left
return 0;
else
{
if (
A-> left -> right
A-> left ->left
(
(A->left!=NULL)&&
(A->left->left==NULL)&&
(A->left->right==NULL)&&
(A->right==NULL)
)
)
{ cout<<" "<<A->key<<" ha come unico figlio un nodo foglia "<<endl;
return contafigli(A->left)+contafigli(A->right)+1;
}
else
return contafigli(A->left)+contafigli(A->right);
Albvari
}
}
/* A1L08
Data una lista di interi eliminare un nodo ogni K incontrati. Nel caso il numero totale dei nodi non
sia multiplo di K aggiungere quanti nodi servono per soddisfare questa condizione attribuendo
ad essi una chiave di valore uguale a K.
*/
void provaA3L(Pnodo &TL, Pnodo L, int cont,int k, Pnodo prec)
{ Pnodo Temp;
if ((L==NULL)&&((cont-1)%k==0)) // se L non è finita e cont è mod k
return;
else
{ if (L!=NULL)
{
if (cont%k!=0) {
provaA3L(TL, L->next, cont+1, k, L);}
else
{
prec->next=L->next;
cout<<"cancello "<<L->info<<endl;
delete L;
provaA3L(TL, prec->next, 1, k, prec);
}
}
else
{
creaNodo(k,Temp);
prec->next=Temp;
provaA3L(TL, Temp->next, cont+1, k, Temp);
}}
}