PDA

Visualizza la versione completa : [ C ] Alberi binari ordinati, un parere.


810106
08-06-2008, 19:22
Salve, come bravo appassionato mi sto studiando gli alberi binari. Dopo un pò di casini
con l'algoritmo per la rimozione di un nodo in un albero binario ordinato ho scritto il mio primo
programma di prova, potete darci un'occhiata tanto per dirmi se c'è qualcosa che non
so?



#include <stdlib.h>
#include <stdio.h>

typedef struct bt
{
int value;
struct bt *low;
struct bt *high;
} bt_t;

#define MINOR(P) (P)->low
#define MAJOR(P) (P)->high
#define VALUE(P) (P)->value

/* Crea un nuovo nodo assegnandogli il valore v
* e impostando i nodi figli l e v */
static bt_t * bt_alloc(const int v, bt_t *l, bt_t *h)
{
bt_t *b = (bt_t*) malloc(sizeof(bt_t));
MINOR(b) = l;
MAJOR(b) = h;
VALUE(b) = v;
return b;
}

/* Elimina una albero a partire dal nodo `n' */
static void bt_delete(bt_t *n)
{
if(n == NULL)
return;
if(MINOR(n))
bt_delete(MINOR(n));
if(MAJOR(n))
bt_delete(MAJOR(n));
free(n);
}

/* Posiziona il cursore per la stampa del nodo */
#define MOVETO(L, C) printf("\x1b[%d;%dH", L, C)

/* Stampa l'albero */
static void bt_print(bt_t *node, unsigned int sl, unsigned int sc)
{
static char l = 1;
int line[] = {0, 20, 10, 5, 5, 5};

MOVETO(l + sl, sc);
printf("%d", VALUE(node));

l++;

if(MAJOR(node))
{
MOVETO(l + sl, sc);
printf("+>");
bt_print(MAJOR(node), sl, sc + line[l]);
}

if(MINOR(node))
{
MOVETO(l + sl, sc - 1);
printf("<+");
bt_print(MINOR(node), sl, sc - line[l]);
}

l--;
}

/* Effettua una ricerca in maniera ricorsiva
* restituisce il nodo contenente il valore
* ricercato oppure NULL se il nodo non
* è stato trovato. */
static bt_t * bt_search(bt_t *b, const int v)
{
if(b == NULL)
return b;
return (VALUE(b) == v) ? b : bt_search(VALUE(b) > v ? MINOR(b) : MAJOR(b), v);
}

/* Inserisce un valore nell'albero */
static bt_t * bt_insert(bt_t *b, const int v)
{
if(b == NULL)
return bt_alloc(v, NULL, NULL);
if(v != VALUE(b))
{
bt_t **n = VALUE(b) > v ? &MINOR(b) : &MAJOR(b);
*n = bt_insert(*n, v);
}
return b;
}

static char bt_remove(bt_t *b, const int v)
{
static bt_t *up = NULL;

if(b == NULL)
return 0;
else if(VALUE(b) != v)
{
up = b;
return bt_remove(VALUE(b) > v ? MINOR(b) : MAJOR(b), v);
}
else
/* Trovato il nodo da eliminare */
{
/* Nessun figlio. Elimina il nodo e
* il collegamento dal padre */
if(!MINOR(b) && !MAJOR(b))
{
bt_t **f;
if(up)
{
f = MAJOR(up) == b ? &MAJOR(up) : &MINOR(up);
*f = NULL;
}
free(b);
return 1;
}
/* 1 figlio */
else if(!MINOR(b) || !MAJOR(b))
{
bt_t **f;
if(up)
{
f = MAJOR(up) == b ? &MAJOR(up) : &MINOR(up);
*f = MINOR(b) ? MINOR(b) : MAJOR(b);
}
free(b);
return 1;
}
/* 2 figli */
else
{
bt_t *x;
for(x = MAJOR(b); MINOR(x) != NULL; )
x = MINOR(x);
VALUE(b) = VALUE(x);
VALUE(x) = v;
up = b;
return bt_remove(MAJOR(b), v);
}
}
return 0;
}

int main(int argc, char **argv, char **argp)
{
bt_t *top;
bt_t *found;
int val;
unsigned int i;
/* Primo nodo */
top = bt_insert(NULL, 5);

/* Inserimento */
bt_insert(top, 7);
bt_insert(top, 3);
bt_insert(top, 4);
bt_insert(top, 6);
bt_insert(top, 2);
bt_insert(top, 8);
bt_insert(top, 1);
bt_insert(top, 9);

/* Stampa */
printf("\033[2J");
MOVETO(1, 1);
printf("ALBERO:\n");
bt_print(top, 2, 40);

bt_remove(top, 5);
bt_remove(top, 7);
bt_remove(top, 1);
MOVETO(8, 1);
printf("ALBERO DOPO LA RIMOZIONE DI 5, 7 E 1:\n");
bt_print(top, 9, 40);

MOVETO(14, 1);
printf("RICERCA:\n");
/* Ricerca */
for(i = 0; i < 5; i++)
{
val = rand() % 15;
found = bt_search(top, val);
if(found)
printf(" %d è nel nodo: %p.\n", val, found);
else
printf(" %d non esiste\n", val);
}

/* Elimina la lista */
bt_delete(top);

return EXIT_SUCCESS;
}


L'output è corretto, solo che vorrei sapere se ci sono algoritmi migliori di quelli che ho usato io
e che ho imparato da wiky... :fagiano:

L'output:


ALBERO:

5
3 <+> 7
2 <+> 4 6 <+> 8
1 <+ +> 9

ALBERO DOPO LA RIMOZIONE DI 5, 7 E 1:

6
3 <+> 8
2 <+> 4 +> 9

RICERCA:
13 non esiste
1 non esiste
12 non esiste
10 non esiste
8 è nel nodo: 0x804a0b0.

bash-3.00$

mondobimbi
08-06-2008, 19:40
solo una occhiata superficiale : è bilanciato?
ciao
sergio

810106
08-06-2008, 19:46
Il bilanciamento lo sto imparando adesso :D

menphisx
08-06-2008, 20:48
Non controlli i valori di ritorno delle malloc

:ciauz:

810106
08-06-2008, 21:09
E un programmino che ho fatto tanto per implementare un'albero non ho guardato le piccole cose come malloc
sapendo che lo eseguo io e che non fallirà mai l'allocazione... sul codice che si occupa di ricerca inserimento e cancellazione ci sono errori?

mondobimbi
08-06-2008, 21:14
sei tu che devi dirci se riscontri dei malfunzionamenti,

ciao
sergio

810106
08-06-2008, 21:22
Il programma fa esattamente quello che deve fare, l'unica cosa che volevo capire è se
le funzioni che lavorano sull'albero possono essere implementate diversamente per ottenere maggiori
prestazioni è solo curiosità o meglio, voglia di imparare... :)

menphisx
08-06-2008, 21:32
Una implementazione iterativa, renderebbe tutto più veloce :)

:ciauz:

mondobimbi
08-06-2008, 21:34
e il bilanciamento più efficiente

810106
09-06-2008, 02:00
A parte gli scherzi, gli alberi bilanciati so cosa sono ma ci sto arrivando, vorrei imparare na cosa alla volta
e impararla bene. Ora sto cercando di capire gli alberi binari ordinati non bilanciati... leggendo di qua e
di la sono riuscito a capire come funzionano la ricerca l'inserimento e la cancellazione su questo tipo
di albero implementato attraverso una struttura.
Ora sto cercando di implementarlo in un array auto espandibile. Poi inizierò gli alberi binari bilanciati, che da quel che ho intravisto e se ho visto giusto si chiamano anche alberi binari di ricerca. Poi ho intravisto altri tipi ma una cosa alla volta altrimenti faccio solo confusione...

Riformulo la mia domanda: il mio codice implementa un albero binario ordinato non bilanciato. C'è qualcosa che
non so che potrebbe migliorare le operazioni su questo tipo di albero? :)

menphisx per implementazione iterativa intendi usare cicli for/while al posto delle chiamate ricorsive?

Loading