1. Definizione di Albero


Rappresentazione delle Operazioni Primitive dell’ABR



Scaricare 142.5 Kb.
Pagina8/11
21.12.2019
Dimensione del file142.5 Kb.
1   2   3   4   5   6   7   8   9   10   11

3.1.Rappresentazione delle Operazioni Primitive dell’ABR

boolean EmptyABR(abr n)

{

return(n==ALBEROVUOTO);



}
boolean FullABR(abr n)

{

return(0);



}
abr LeftChild(abr n)

{

if (!EmptyABR(n))



return(n->leftchild);

}
abr RightChild(abr n)

{

if (!EmptyABR(n))



return(n->rightchild);

}
tipobaseABR Label(abr n)

{

if (!EmptyABR(n))



return(n->info);

}
void MakeNullABR(abr *p)

{

*p=ALBEROVUOTO;



}


  • Member(n,x). La strategia di ricerca può essere realizzata nella seguente maniera:

  1. se il sottoalbero la cui radice è il nodo n è vuoto allora l'elemento x cercato non è presente.

  2. se il sottoalbero la cui radice è il nodo n non è vuoto e x compare nella radice n, allora x esiste e la funzione ritorna il valore vero.

  3. se il sottoalbero la cui radice è il nodo n non è vuoto e x non compare nella sua radice n, allora bisogna considerare il sottoalbero di destra se x è superiore, secondo la relazione d'ordine ">", dell'elemento contenuto nella radice n. Viceversa, la ricerca deve essere applicata al sottoalbero di sinistra.

I precedenti passi possono essere espressi dal seguente algoritmo ricorsivo:
boolean Member(abr n, tipobaseABR x)

{

if (EmptyABR(n)) return(0);



if (!Confronta(n->info,x)) return(1);

if (Confronta(n->info,x)>0) return(Member(n->leftchild,x));

else return(Member(n->rightchild,x));

}


  • InsertABR(n, x). La strategia di inserimento può essere realizzata nella seguente maniera:

  1. se il sottoalbero la cui radice è il nodo n è vuoto allora viene generato un nuovo sottoalbero contenente unicamente un nodo radice, nella quale viene memorizzato l'elemento x.

  2. se il sottoalbero la cui radice è il nodo n non è vuoto e x compare nella radice di tale sottoalbero, allora x esiste e non si deve inserire.

  3. se il sottoalbero non è vuoto e x non compare nella sua radice, allora bisogna considerare il sottoalbero di destra se x è superiore, secondo la relazione d'ordine ">", dell'elemento contenuto nella radice. Viceversa, l'inserimento deve essere applicato al sottoalbero di sinistra.

I precedenti passi possono essere espressi dal seguente algoritmo ricorsivo:
void InsertABR(abr *p, tipobaseABR x)

{

if (EmptyABR(*p)) {



*p=(struct nodoABR *)malloc(sizeof(struct nodoABR));

(*p)->info=x;

(*p)->leftchild=(*p)->rightchild=ALBEROVUOTO;

} else if (Confronta((*p)->info,x)>0) InsertABR(&(*p)->leftchild,x);

else if (Confronta((*p)->info,x)<0) InsertABR(&(*p)->rightchild,x);

}
/*da notare che se Confronta((*p*)->info,x)==0 allora l’elemento x non viene inserito*, visto che è già presente nell’ABR/




  • Delete(n, x). L'algoritmo di cancellazione è più complesso rispetto quello di inserimento e di ricerca. I passi principali di cui si compone possono essere riassunti nel seguente modo:

  1. se il sottoalbero, la cui radice è il nodo n, è vuoto allora l'elemento x cercato non è presente, dunque non può essere cancellato.

  2. se il sottoalbero, la cui radice è il nodo n, non è vuoto e x non compare nella sua radice, allora bisogna considerare il sottoalbero di destra se x è superiore dell'elemento contenuto nella radice. Viceversa si deve considerare il sottoalbero di sinistra.

  3. se il sottoalbero, la cui radice è il nodo n, non è vuoto e x compare nella radice di tale sottoalbero, allora x esiste e deve essere cancellato. La cancellazione deve continuare a garantire le proprietà dell'ALBERO BINARIO DI RICERCA. La modalità con cui l'elemento deve essere cancellato è differente e dipende dal fatto che il nodo è interno o è una foglia. Si consideri l'esempio mostrato in Figura 1.


Figura 1
In riferimento all’ABR mostrato in Figura 1, sono possibili differenti casi:



  • Caso 1. Il nodo da cancellare è una foglia allora la cancellazione è semplice e consiste nell'eliminazione della foglia stessa. In tal caso le proprietà dell'ABR sono palesemente mantenute. Ciò accade quando, considerando l’esempio precedente bisogna cancellare il nodo 7, 11, 13, 15, 18 o 20.

  • Caso2. Se il nodo è interno allora bisogna differenziare se esso possiede uno o due figli. Se possiede un solo figlio allora il nodo può essere eliminato e sostituito dalla radice dell'unico sottoalbero. Le proprietà dell'ABR sono mantenute perché il nodo cancellato apparteneva ad un sottoalbero contenente elementi tutti più grandi o tutti più piccoli rispetto al genitore del nodo cancellato. Dunque se noi sostituiamo il nodo cancellato con il nodo radice del suo sottoalbero, tutto questo sottoalbero continua a contenere elementi o tutti più grandi o tutti più piccoli del genitore del nodo cancellato, mantenendo le proprietà dell'ABR. Il caso 2 si verifica ad esempio quando si deve cancellare il nodo 6, 10 o 17.

  • Caso 3. Le cose sono più complesse se il nodo da cancellare presenta due figli. In tal caso la cancellazione del nodo comporta la presenza di due sottoalberi distinti aventi come radice il figlio destro e il figlio sinistro del nodo da cancellare. Il problema è come connettere questi sottoalberi mantenendo le proprietà dell'ABR. Sia TS il sottoalbero la cui radice è il figlio sinistro del nodo da cancellare e TD il sottoalbero la cui radice è il figlio destro del nodo da cancellare. È chiaro che tutti gli elementi di TD sono più grandi di tutti gli elementi di TS. Una soluzione potrebbe essere quella di sostituire il nodo cancellato con il più piccolo elemento di TD o con il più grande elemento di TS. Nel primo caso sia min l'elemento più piccolo di TD. Se min è messo al posto del nodo cancellato verrà formato un albero T che ha per radice un elemento min, che risulta più grande di tutti gli elementi di TS, perchè min apparteneva a TD, e più piccolo di tutti gli elementi di TD per ipotesi. Dunque la proprietà dell'ABR è mantenuta. Nel secondo caso, se max è l'elemento più grande di TS, e se esso viene sostituito al nodo cancellato, otteniamo un albero T che ha come radice l'elemento max, che è più grande di tutti gli elementi di TS per ipotesi e più piccolo di tutti gli elementi di TD perché max apparteneva a TS. Quindi anche in questo caso la proprietà degli ABR è mantenuta. Con riferimento all’esempio fornito, si supponga di dover cancellare il nodo 16. In tal caso, esso può essere sostituito dal massimo nodo del sottoalbero di sinistra, ossia dal nodo 15. Oppure esso può essere sostituito dal più piccolo nodo del sottoalbero di destra, ossia dal nodo 17. In entrambi i casi la proprietà degli ABR è rispettata. Nel seguito si farà l'ipotesi di sostituire il nodo cancellato con il più piccolo tra gli elementi del sottoalbero di destra TD. In accordo a tale ipotesi, l’albero mostrato in Figura 1, diventa quello mostrato in Figura 2, a seguito della cancellazione del nodo 16.








Condividi con i tuoi amici:
1   2   3   4   5   6   7   8   9   10   11


©astratto.info 2019
invia messaggio

    Pagina principale