[Java] alberi 2-3

[avaj]

raga...
mi date due dritte sugli alberi ddue tre e sulla loro gestione in java?

[Paoletta_r]

Ciao non so se ti può essere utile ma ti mando lo pseudocodice..se vuoi ho la riduci(cancella in c...se la vuoi chidi pure.
CODICE:
link CERCA (a,v){ // avalore da ricercare; vradice dell’albero
If (“v->f1 è una foglia”)
Return v;
else if (a<=v->max1)
return CERCA(a,v->f1);
else if ((v->f3==null) || (a<=v->max2))
return CERCA(a,v->f2);
else
return CERCA(a,v->f3);
} // end CERCA
// Questa funzione fa si che ci si fermi sempre e comunque al penultimo livello dell’albero, sia che il valore cercato esista, sia che il valore cercato non esista.

Int MEMBER (a,r){
p = CERCA(a,r);
if (“a è figlio di p”) // se a esiste
retirn 1;
//else
return 0; // a non esiste
}// end MEMBER

void RIDUCI (v,F1,F2,F3,F4){
if (F4 != null){ // se F4 è = null non devo fare nessuna operazione
“crea un nodo v”;
v->f1=F1;
v->f2=F2;
v->f3=null;
v->f1=F3;
v->f2=F4;
v->f3=null;
F1->padre = v;
F2->padre = v;
F3->padre = v;
F4->padre = v;
if (v->padre == null){ // se v è radice
“crea una nuova radice r”;
r->f1=v;
r->f2=v;
r->f3=null;
v->padre=v->padre=r;
“aggiusta le etichette di r, v, v”;
}// end if
else{ // non siamo nella radice: dobbiamo propagare il problema verso l’alto
u = v->padre;
if(u->f1 == v) // se v è il figlio sinistro
RIDUCI(u,v,v,u->f2,u->f3);
else if (u->f2 == v) // se v è il figlio centrale
RIDUCI(u,u->f1,v,v,u->f3);
else if (u->f2 == v) // se v è il figlio destro
RIDUCI(u, u->f1, u->f2,v,v);
}//end else
} // end if
} // end RIDUCI

[avaj]

sisi scrivi pure anche in c...
traduco poi io

[Paoletta_r]

A suo tempo mi era stata molto utile...spero possa servire anche a te...............

questa è la riduci che viene chiamata dalla cancella
typedef CHIAVE int;

struct NODO {
struct NODO *f1;
struct NODO *f2;
struct NODO *f3;
struct NODO *padre;
CHIAVE max1;
CHIAVE max2;
}

typedef struct NODO NODO;

/* v è un nodo con 4 ipotetici figli F1, F2, F3 e F4 con etichette corrette */
/* pos indica quale nodo ha originato la scomposizione – ovvero quale coppia */
/* di figli deve essere considerata frutto della scomposizione al livello sottostante */
/* pos=1~ (F1,F2), pos=2~ (F2,F3), pos=3~ (F3,F4), */
void riduci(NODO *v,NODO *F1,NODO *F2, NODO *F3, NODO *F4,int pos)
{
NODO * r1;
NODO * r2;
if (F4 != NULL) /* v ha 4 figli */
{ r1 = malloc(sizeof(NODO)); /*creiamo un fratello sinistro di v */
r1->f1 = F1;
r1->f2 = F2;
r1->f3 = NULL;
r1->padre = v->padre;
v->f1 = F3;
v->f2 = F4;
v->f3 = NULL;
F1->padre = F2->padre = r1;
F3->padre = F4->padre = v;
\* aggiusta le etichette di v e di r1 *\
switch(pos) {
case 1 : /* il nodo scomposto era il primo figlio */
r1->max1 = F1->max2;
r1->max2 = v->max1; /* equivale a r1->max2 = F2->max2 */
v->max1 = v->max2 ;
v->max2 = max(F4) ;
break;
case 2 : /* il nodo scomposto era il secondo figlio */
r1->max1 = v->max1;
r1->max2 = F2->max2;
v->max1 = v->max2 ; /* equivale a v->max1 = F3->max2 */
v->max2 = max(F4) ;
break;
case 3 : /* il nodo scomposto era il terzo figlio */
r1->max1 = v->max1;
r1->max2 = v->max2;
v->max1 = F3->max2 ;
v->max2 = F4->max2 ;
break;
}
if (v->padre == NULL) /* v è la radice */
{
r2 = malloc(sizeof(NODO)); /* crea un nuovo nodo*/
*r2 = *v; /* ora r2 è uguale a v */
/* e v può assumere i nuovi valori */
v->f1 = r1;
v->f2 = r2;
v->f3 = v->padre = NULL;
r2->padre = r1->padre = v;
v->max1 = r1->max2 ;
v->max2 = r2->max2 ;
}
else /* v ha un padre */
{
r2 = v->padre;
if (r2->f1 == v) riduci(r2,r1,v,r2->f2,r2->f3,1);
else if (r2->f2 == v) riduci(r2,r2->f1,r1,v,r2->f3,2);
else if (r2->f3 == v) riduci(r2,r2->f1 ,r2->f3,r1,v,3);
}
}
else /* occorre solo sistemare le etichette: v ha tre figli */
{
if (pos == 1)
{
v->max1 = F1->max2;
v->max2 = F2->max2;
}
else /* pos può essere solo 2*/
{
if (v->max2 != F3->max2)
{ v->max2 = F2->max2; /* aggiorna l'etichetta di v e poiché */
/* è cambiato il massimo nel sottoalbero di v */
aggiorna(v->padre,v,F3->max2); /* propaga la modifica */
}
else v->max2 = F2->max2;
}
}
}



/* v è un nodo che ha un figlio w con un nuovo massimo val */
void aggiorna(NODO * v, NODO * w, CHIAVE val)
{
if (v->f1 == w) /* w è il primo figlio: basta modificare la prima etichetta */
{
v->max1 = val;
}
if (v->f2 == w) /* w è il secondo figlio: modifichiamo la seconda etichetta */
{ v->max2 = val;
if ((v->f3 == NULL) && (v->padre != NULL))
aggiorna(v->padre,v,val); /* poiché non c'è un fratello maggiore */
/* occorre propagare il nuovo massimo */
}
if ((v->f3 == w) && (v->padre != NULL)) aggiorna(v->padre,v,val);
}

Per quanto riguarda la cancellazione, invece, se il nodo dal quale si cancella un figlio aveva già tre figli, non ci sono problemi, altrimenti (se il padre del nodo da cancellare aveva solo due figli) con la cancellazione, il padre del nodo cancellato avrà solo un figlio, causando così un problema: le proprietà principali di un albero bilanciato non sono più verificate. Si deve quindi trovare un metodo per ripristinare le caratteristiche dell’albero; si hanno due possibilità: il nodo dal quale è stato eliminato un figlio può adottarne uno da un suo fratello (se questo non causa altri problemi: il fratello che cede un figlio ne deve avere per forza tre, in modo tale da non compromettere le caratteristiche dell’albero), oppure può cedere il proprio figlio a un fratello, e poi eliminarsi. In quest’ultimo caso, il problema potrebbe propagarsi verso l’alto: si deve quindi risolvere il problema ricorsivamete.

#define PRIMO_FIGLIO(v) (v->padre->f1 == v)
#define SECONDO_FIGLIO(v) (v->padre->f2 == v)
#define HA_DUE_FRATELLI(v) (v->padre->f3 != NULL)
#define SI 1
#define NO 0
#define SINISTRA 0
#defie DESTRA 1
#define DONTCARE 0
#define CHIAVE int
#define CHIAVENULLA 0

int possibile_adozione_destra(NODO * v)
{
if (PRIMO_FIGLIO(v)) return v->padre->f2->f3 != NULL;
if (SECONDO_FIGLIO(v))
{ if (HA_DUE_FRATELLI(v))
return v->padre->f3->f3 != NULL;
else return NO; /* non esiste fratello a destra */
}
return NO;
}

int possibile_adozione_sinistra(NODO * v)
{
if (PRIMO_FIGLIO(v))
return NO; /* non esiste un fratello a sinistra */
if (SECONDO_FIGLIO(v)) return v->padre->f1->f3 != NULL;
return v->padre->f2->f3 != NULL;
}

/* questa funzione sposta il figlio unico del nodo indicato nella direzione specificata, restituendo l'avvenuto spostamento (SI/NO) */
int sposta_figlio(NODO *v, int direzione)
{
if (v->f1 != NULL)
{
if (direzione == SINISTRA) return NO;
v->max2 = v->max1;
v->f2 = v->f1;
v->f1 = NULL;
return SI;
}
else /* l'unico figlio di v è in seconda posizione */
if (direzione == DESTRA) return NO;
else
{v->max1 = v->max2;
v->f1 = v->f2;
v->f2 = NULL;
return SI;
}
}

/* questa funzione prende un nodo v con un solo figlio e gli aggiunge un nuovo figlio prelevato dal fratello a destra, aggiustando di conseguenza tutte le etichette (padre di v compreso) */
void adotta_a_destra(NODO *v)
{ NODO * donatore;
sposta_figlio(v,SINISTRA);
if (PRIMO_FIGLIO(v)) donatore = v->padre->f2;
else donatore = v->padre->f3;
v->f2 = donatore->f1;
v->max2 = donatore->max1;
donatore->max1 = donatore->max2;
donatore->f1 = donatore->f2;
donatore->f2 = donatore->f3;
donatore->f3 = NULL;
donatore->max2 = max(donatore->f2);
if (PRIMO_FIGLIO(v)) v->padre->max1 = v->max2;
else v->padre->max2 = v->max2;
}

/* questa funzione prende un nodo v con un solo figlio e gli aggiunge un nuovo figlio prelevato dal fratello a sinistra, aggiustando di conseguenza tutte le etichette (padre di v compreso, antenati se è il caso */
void adotta_a_sinistra(NODO *v)
{ NODO * donatore;
int cambiato;
cambiato= sposta_figlio(v,DESTRA);
if (SECONDO_FIGLIO(v))
{donatore = v->padre->f1;
v->max1 = v->padre->max1;
/* è il massimo del figlio adottato */
v->padre->max1 = donatore->max2;
v->padre->max2 = v->max2;
}
else
{donatore = v->padre->f2;
v->max1 = v->padre->max2;
v->padre->max2 = donatore->max2;
}
/* ora v, padre di v e donatore hanno etichette corrette */
v->f1 = donatore->f3;
donatore->f3 = NULL;
/* controlla le etichette verso l'alto */
if (SECONDO_FIGLIO(v) && HA_DUE_FRATELLI(v)) return;
else /* v è il terzo figlio o il secondo di due */
{ if (cambiato && (v->padre->padre != NULL))
aggiorna(v->padre->padre,v->padre,v->max2);
}
}

/* v è un nodo con il solo primo figlio, la funzione affida tale figlio al fratello sx di v, aggiusta le etichette del fratello e del padre e termina dopo aver cancellato v */
void affida_a_sinistra(v)
{
if (SECONDO_FIGLIO(v))
{ /* affida il figlio al primo fratello */
v->padre->f1->f3 = v->f1;
/* è cambiato il max del I sottoalbero di padre->v */
v->padre->max1 = v->max1;
if (HA_DUE_FRATELLI(v))
{
v->padre->f2 = v->padre->f3;
v->padre->f3 = NULL;
v->padre->max2 = v->padre->f2->max2;
}
else
{
v->padre->f2 = NULL;
v->padre->max2 = CHIAVENULLA;
}
}
else /* v è il terzo figlio */
{/* affida il figlio al secondo fratello */
v->padre->f2->f3 = v->f1;
/* è cambiato il max del II sottoalbero di padre->v */
v->padre->max2 = v->max1;
}
free(v);
}

/* v è un nodo con il solo primo figlio, la */
/* funzione affida tale figlio al fratello dx di v, */
/* aggiusta le etichette del fratello e del padre e */
/* termina dopo aver cancellato v */
void affida_a_destra(v)
{ NODO * adottante;
if (PRIMO_FIGLIO(v))
{adottante = v->padre->f2;
adottante->f3 = adottante->f2;
adottante->f2 = adottante->f1;
/* affida il figlio al secondo fratello */
adottante->f1 = v->f1;
adottante->max2 = adottante->max1;
adottante->max1 = v->max1;
v->padre->max1 = v->padre->max2;
v->padre->f1 = v->padre->f2;
v->padre->f2 = v->padre->f3;
v->padre->f3 = NULL;
if (HA_DUE_FRATELLI(v))
v->padre->max2= max(v->padre->f2);
else
v->padre->max2 = CHIAVENULLA;
}
else /* v è il secondo figlio */
{adottante = v->padre->f3;
adottante->f3 = adottante->f2;
adottante->f2 = adottante->f1;
/* affida il figlio al terzo fratello */
adottante->f1 = v->f1;
adottante->max2 = adottante->max1;
adottante->max1 = v->max1;
v->padre->f2 = v->padre->f3;
v->padre->f3 = NULL;
v->padre->max2= max(v->padre->f2);
}
free(v);
}

/* v è un nodo con al più 2 figli F1,F2 (con etichette corrette), pos indica la posizione del figlio che si è suicidato, up indica se è variato il massimo di v e quindi occorre una risalita nell'albero */
void riduci2(NODO *v,NODO *F1,NODO *F2, int up, int max)
{
NODO * r1;
NODO * r2;
CHIAVE val;
int propaga;

if (F2 != NULL) /* v ha 2 figli, controlliamo le etichette */
{if (v->padre == NULL) return; /* v è la radice */
if (up) aggiorna(v->padre,v,max);
return;
}
else /* v ha un solo figlio */
{
if (v->padre == NULL) /* v è la radice */
{sposta_figlio(v,SINISTRA);
v=v->f1;
free(v->f1);
return;
}
if (PRIMO_FIGLIO(v))
{if (possibile_adozione_destra(v))
{adotta_a_destra(v); return;}
else
{sposta_figlio(v,SINISTRA);
affida_a_destra(v);
riduci2(v->padre,v->padre->f2,v->padre->f3,NO,DONTCARE);
return;
}
}
if (SECONDO_FIGLIO(v))
{if (possibile_adozione_destra(v))
{adotta_a_destra(v); return;}
if (possibile_adozione_sinistra(v))
{adotta_a_sinistra(v); return;}
if (HA_DUE_FRATELLI(v))
{sposta_figlio(v,SINISTRA);
affida_a_destra(v);
riduci2(v->padre,v->padre->f1,v->padre->f3,NO,DONTCARE);
return;
}
else
{sposta_figlio(v,SINISTRA);
val = v->max1;
affida_a_sinistra(v);
riduci2(v->padre,v->padre->f1,NULL,SI,val);
return;
}
}
/* v è il terzo fratello */
if (possibile_adozione_sinistra(v))
{adotta_a_sinistra(v); return;}
else
{sposta_figlio(v,SINISTRA);
val = v->max1;
affida_a_sinistra(v);
riduci2(v->padre,v->padre->f1,v->padre->f2,SI,val);
return;
}
}
}

/* v è un nodo che ha un figlio w con un nuovo max val */
void aggiorna(NODO * v, NODO * w, CHIAVE val)
{
if (v->f1 == w) /* w è il I figlio: basta modificare la I etichetta */
{
v->max1 = val;
return v;
}
if (v->f2 == w) /* w è il II figlio: modifichiamo la II etichetta e... */
{ v->max2 = val;
if (v->f3 == NULL && (v->padre != NULL)) aggiorna(v->padre,v,val);
return;
}
/* w è il III figlio propaghiamo il nuovo massimo */
if (v->padre != NULL) aggiorna(v->padre,v,val);
}

[avaj]

grazie mille!!!