Ciao a tutti, sono nuovo!
Sto impazzendo per implementare un semplice inserimento in un albero rosso nero in c ( ). La struct l'ho dichiarata in questo modo:
typedef enum {rosso, nero} colore_t;
typedef struct nodo
{
int valore;
colore_t colore;
struct nodo *sinistro, *destro, *padre;
} alberorn_t;
Inserimento:
int inserisci(alberorn_t* sent, int valore)
{
int inserito;
alberorn_t *nodo, *padre, *nuovo;
for(nodo = sent->sinistro, padre = sent;
((nodo != sent) && (nodo->valore != valore));
padre = nodo, nodo = (valore < nodo->valore)?
nodo->sinistro:
nodo->destro);
if(nodo != sent)
{
inserito = 0;
}
else
{
inserito = 1;
nuovo = (alberorn_t *)malloc(sizeof(alberorn_t));
nuovo->valore = valore;
nuovo->colore = rosso;
nuovo->sinistro = nuovo->destro = sent;
nuovo->padre = padre;
if(padre == sent)
{
sent->sinistro = sent->destro = nuovo;
}
else
{
if(valore < padre->valore)
{
padre->sinistro = nuovo;
}
else
{
padre->destro = nuovo;
}
}
ripristina(sent, nuovo);
}
return(inserito);
}
Rotazione sinistra:
void rotazione_sx(alberorn_t* nodo, alberorn_t* x)
{
alberorn_t *y;
y = x->destro;
x->destro = y->sinistro;
y->sinistro->padre = x;
y->padre = x->padre;
if(x == nodo->sinistro)
{
nodo->sinistro = nodo->destro = y;
}
else
{
if(x == x->padre->sinistro)
{
x->padre->sinistro = y;
}
else
{
x->padre->destro = y;
}
}
y->sinistro = x;
x->padre = y;
}
La rotazione destra è speculare alla sinistra.
Funzione di ripristino dopo un inserimento:
void ripristina(alberorn_t* sent, alberorn_t* nodo)
{
alberorn_t *zio;
while(nodo->padre->colore == rosso)
{
if(nodo->padre == nodo->padre->padre->sinistro)
{
zio = nodo->padre->padre->destro;
if(zio->colore == rosso)
{
nodo->padre->colore = nero;
zio->colore = nero;
nodo->padre->padre->colore = rosso;
nodo = nodo->padre->padre;
}
else
{
if(nodo == nodo->padre->destro)
{
nodo = nodo->padre;
rotazione_sx(sent, nodo);
}
nodo->padre->colore = nero;
nodo->padre->padre->colore = rosso;
rotazione_dx(sent, nodo->padre->padre);
}
}
else
{
zio = nodo->padre->padre->sinistro;
if(zio->colore == rosso)
{
nodo->padre->colore = nero;
zio->colore = nero;
nodo->padre->padre->colore = rosso;
nodo = nodo->padre->padre;
}
else
{
if(nodo == nodo->padre->sinistro)
{
nodo = nodo->padre;
rotazione_dx(sent, nodo);
}
nodo->padre->colore = nero;
nodo->padre->padre->colore = rosso;
rotazione_sx(sent, nodo->padre->padre);
}
}
}
sent->sinistro->colore = nero;
}
Per quanto riguarda il main:
int scelta;
alberorn_t *sent;
FILE *file;
int valore;
int esito;
int n = 0;
sent = (alberorn_t *)malloc(sizeof(alberorn_t));
sent->sinistro = sent;
sent->destro = sent;
sent->padre = sent;
while((scelta = menu()))
{
switch(scelta)
{
case 1:
file = fopen("file.txt","r");
while((fscanf(file, "%d", &valore)) == 1)
{
esito = inserisci(sent, valore);
if(esito == 1)
{
printf("%d: Inserito\n", sent->valore);
}
else
{
printf("%d: Errore durante l'inserimento\n", sent->valore);
}
n++;
printf("numero iterazioni: %d\n", n);
}
break;
Premetto che il codice è quello delle dispense del mio professore dell'università. A quanto pare non mi inserisce proprio nulla; se riuscite a dirmi dove sbaglio vi sarò eternamente grato
EDIT: Aggiungo che durante la compilazione non mi da nessun errore né warning, ma quando cerco di stampare l'albero con una semplice funzione di stampa mi dà il seguente errore:
"Errore di segmentazione (core dump creato)"