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.

30

35

3

44

35

8

38

28

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

50 35

3

44

35

8

38

28

10

3

50

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

New

Old

Parent

Old

New

Parent

Old

Parent

Old

(a)

(d)

(b)

(c)

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

30

5

3

40

35

80

38

8

35

5

3

40

35

80

38

8

10

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.

QQQ

RRR

Parent

Candidate

left right

Il puntatore che da Parent prima puntava a Candidate ora acquista il valore del puntatore a RRR ottenuto in questo caso da Candidate->right

11

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.

QQQ

RRR

Parent

Candidate

left right

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

Caso b- il nodo da eliminare ha il sotto albero destro vuoto.La procedura è analoga alla precedente.

Eliminare Riccardo

Pseudo Codice

if (Candidate->left==NULL)LegaPadre(Candidate, Candidate ->right, Padre, Tree)

elseif (Candidate->right==NULL)) LegaPadre(Candidate, Candidate ->left, Padre, Tree) else continua a riorganizzare l’albero

void LegaPadre(Tnodo OldChild, Tnodo NewChild, Tnodo Padre, Tnodo &Tree){riorganizza l’albero BST dopo l’eliminazione di un nodo}

QQQ

RRR

Parent

Candidate

left right

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

New

Old

Parent

Old

New

Riassunto dei tipi di cancellazione

New

Old

Parent

Old

New

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}

30

5

3

40

35

80

38

8

35

5

3

40

3580

38

8

15

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 nessuno dei due sotto alberi è vuoto allora chiama NuovoCandidato

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 il sottoalbero destro è vuoto collega il genitore di candidato con la radice del sotto albero sinistro. Se Padre=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

Non c’è niente da cancellare

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; Done=true; Cerca( Tree, KeyValue, Candidato, Padre); DammiChiave(Candidato, CandsKey); if (CandsKey!=KeyValue) Done=false; 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); KillTNode(Candidato);}

Se il sottoalbero sinistro è vuoto collega il genitore di candidato con la radice del sotto albero destro. Se Padre =NULL, cioè si vuole cancellare la radice allora poni in Tree la radice del sotto albero destro.

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);}

Ricerca OldCandidate a partire dal suo nodo destro con la conseguenza che trova il più piccolo di questo sottoalbero (Candidato) (Dummy vale NULL)

Sostituisci il nodo da cancellare con Candidate

Riprendi la chiave del nodo spostato

Cerca il più piccolo nodo del sottoalbero destro del nodo spostato a partire dalla sua primitiva posizione

Collega il sottoalbero destro con il padre del nodo spostato

Se il nodo da cancellare è la root allora collega il sottoalbero destro con la root

CercaCerca(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 sinistroelse TNode radice del sottoalbero destro

Il padre dell’ultimo nodo esaminatodurante la ricerca di KeyValue

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) Node=Node->left; else Node=Node->right; DammiChiave(Node, NodesKey); }};

Ricordarsi che DammiChiave nel caso trovi NULL ritorna una chiave nulla.

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;

}

DelTNode(K,T,d)

Cancella il nodo K dell’albero T

Cerca(T,K,N,P)

Cerca in T il nodo K. Il suo puntatore è N e P è suo padre

DammiChiave(K,N)

Verifica che a N corrisponde la chiave K

La chiave non cè: ESCI

N->left=NULL N->right=NULL

LegaPadre(N,N->right,P,T)

Collega il padre P con N->right e cancella N

Collega il padre P con N->left e cancella N

LegaPadre(N,N->left,P,T)

NuovoCandidato(K,N,T)

NuovoCandidato(K,N,T)

Cerca(N->right, K, D, U)

DammiChiave(Uk,U)

Cerca(N->right, Uk, D, P)

P=NULL PNULL

LegaPadre(U,U->right,N,T)

LegaPadre(U,U->left,N,T)

Cerco il più piccolo a destra. Parto a destra di K cerco K e così ottengo il più piccolo, U

A partire dal sotto albero destro di N, cerco Uk per avere suo padre P

RICAPITOLANDO

21

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 nessuno dei due sotto alberi è vuoto allora chiama NuovoCandidato

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.

RICAPITOLANDO

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=bNode=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

NewChild

OldChild

OldChildNewChild

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.

35

5

3

40

3580

38

8

OldCandidato

Candidato

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);}

24

90

50 95

30

34

40

3615

93 98

10017

13

35

47

Cerca(Tree, KeyValue, Candidate, Parent)

DammiChiave(Candidate, CandsKey);

if CandsKey<> KeyValue Done=FALSE

else

if (Candidate->left==NULL) LegaPadre(Candidate, Candidate-> Right, Parent, Tree) else if (Candidate->right==NULL)) LegaPadre(Candidate, Candidate-> Left, Parent, Tree) else NuovoCandidato(KeyValue, Candidate, Tree);KillTNode(Candidate);

Cancellare il nodo 30

OldCandidate = Candidate

Cerca( OldCandidate->right), KeyValue, Dummy, Candidate)

OldCandidate->Key = Candidate^.Key;

CandsKey = Candidate->Key;

Cerca(OldCandidate->right, CandsKey, Dummy, Parent);

if Parent = NULL THEN

LegaPadre(Candidate, Candidate ->right, OldCandidate, Tree)

else

LegaPadre(Candidate, Candidate ->right, Parent, Tree);

P30

P4030 NULL P34

34

34

P40 34 P34 P363834

P34 P35 P36

NuovoCandidato(KeyValue, Candidate, Tree)

DelTNode(KeyValue, Tree, Done)

500

400600

700

800

420

410

454 456

900

430

Cancella un nodo

440

470

455 475

460

450 480

500

400600

700

800

420

410

454 456

900

430

450

470

455 475

460

480

500

400 600

550

564

558

553

556

555 557

566

559

550

400 600

553

564

556

558

555557

566

559

Cancella la root

ESERCIZIO

Sia assegnato un albero binario, scrivere un algoritmo tale che sposti ogni figlio sinistro nel corrispondente figlio destro e viceversa.

A

B C

D E F

G H

A

C B

DF E

H 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) { if (A==NULL) return 0; else { if ( ( (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

A

A->rightA->left

A-> left ->left A-> left -> right

/* A1L08Data 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); }}}