[ANSI C] - Albero binario di ricerca

[misterx]

ciao,
elimino quanto richiesto in quanto sentivo di essere parecchio fuori strada.

Devo usare gli alberi binari di ricerca e mi è venuta la seguente intutizione: costruisco la mia struttura dati che contiene tutti i dati necessari. Ogni puntatore di queste strutture lo memorizzo nei nodi di un ABR e poi con le consuete funzioni faccio ricerche, riordini eventuali è giusto ?

ciao

p.s.
aggiungo uno scorcio di codice


solitamente la struttura di un albero di ricerca è la seguente:

struct alberodiricerca {
int nodo;
struct alberodiricerca *left, *right, *up;
};


ma sarebbe corretta anche questa ?

struct alberodiricerca {
int chiave;
char *nome;
char *cognome;
char *indirizzo
char *città;
struct alberodiricerca *left, *right, *up;
};

[misterx]

edit

[misterx]

ciao,
aggiungo anche questa domanda relativa a questo codice:

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

typedef int key;

struct searchtree {
	key v;
	struct searchtree *left, *right, *up;
}; 

typedef struct searchtree searchtree;

searchtree *createsearchtree(void);
...........
...........
searchtree *createsearchtree(void)
{
	return NULL;
}

mi riferisco alla funzione createsearchtree() che ritorna un NULL mentre io mi aspettavo che ritornasse un puntatore alla radice, ma a cosa serve quindi ?

grazie

[misterx]

come non detto, sono passato agli alberi RB

ciao

[coocooche]

Ciao,
sto studiando pure io le strutture dati in C. Se non lo sapessi e ti puo aiutare, ci sta questo libro che tratta per bene le strutture dati ed è conosciuto:

Addison Wesley - Algorithms In C di Sedgewick

[Fibrizio]

Originariamente inviato da misterx

ciao,
elimino quanto richiesto in quanto sentivo di essere parecchio fuori strada.

Devo usare gli alberi binari di ricerca e mi è venuta la seguente intutizione: costruisco la mia struttura dati che contiene tutti i dati necessari. Ogni puntatore di queste strutture lo memorizzo nei nodi di un ABR e poi con le consuete funzioni faccio ricerche, riordini eventuali è giusto ?

ciao

p.s.
aggiungo uno scorcio di codice


solitamente la struttura di un albero di ricerca è la seguente:

struct alberodiricerca {
int nodo;
struct alberodiricerca *left, *right, *up;
};


ma sarebbe corretta anche questa ?

struct alberodiricerca {
int chiave;
char *nome;
char *cognome;
char *indirizzo
char *città;
struct alberodiricerca *left, *right, *up;
};

cosa sarebbe up? gli alberi binari si costruiscono con due rami, né più né meno, se no il criterio di ordinamento(ricerca non funziona.

[fero86]

Originariamente inviato da Fibrizio

cosa sarebbe up? gli alberi binari si costruiscono con due rami, né più né meno, se no il criterio di ordinamento(ricerca non funziona.

"up" é evidentemente il puntatore al padre, un campo che nel 99% dei casi indica una pessima implementazione
a partire dal fatto che se introduci quel campo introduci anche la possibilitá di stati inconsistenti della struttura dati: affinché la struttura sia consistente dovrebbe esserci uno e un solo nodo che ha up = NULL e in tutti gli altri nodi il nodo puntato da up dovrebbe puntare al nodo stesso o con left o con right. troppo complicato da gestire.

[DanieleC88]

Originariamente inviato da fero86

"up" é evidentemente il puntatore al padre, un campo che nel 99% dei casi indica una pessima implementazione
a partire dal fatto che se introduci quel campo introduci anche la possibilitá di stati inconsistenti della struttura dati: affinché la struttura sia consistente dovrebbe esserci uno e un solo nodo che ha up = NULL e in tutti gli altri nodi il nodo puntato da up dovrebbe puntare al nodo stesso o con left o con right. troppo complicato da gestire.

Scusa, perché? La radice avrà un genitore nullo, tutti gli altri verranno aggiornati di conseguenza durante gli inserimenti o le rimozioni, non vedo il problema. Quella di avere un puntatore al nodo padre è una prassi comune e sicuramente utile, tanto che sono sicuro sia riportata dalla stragrande maggioranza dei testi introduttivi agli algoritmi e alle strutture dati.
Tanto per fare un esempio, senza avere un riferimento al nodo padre, se io ti chiedessi di scrivere una routine che riceve in input un generico nodo di un albero binario di ricerca e mi restituisce in output 1) il nodo suo successore, o 2) un valore nullo, se questo non esiste, come faresti?

ciao

[Fibrizio]

Originariamente inviato da DanieleC88

Scusa, perché? La radice avrà un genitore nullo, tutti gli altri verranno aggiornati di conseguenza durante gli inserimenti o le rimozioni, non vedo il problema. Quella di avere un puntatore al nodo padre è una prassi comune e sicuramente utile, tanto che sono sicuro sia riportata dalla stragrande maggioranza dei testi introduttivi agli algoritmi e alle strutture dati.
Tanto per fare un esempio, senza avere un riferimento al nodo padre, se io ti chiedessi di scrivere una routine che riceve in input un generico nodo di un albero binario di ricerca e mi restituisce in output 1) il nodo suo successore, o 2) un valore nullo, se questo non esiste, come faresti?

ciao

a questo sopperisce il criterio di ricerca che sottostà all'albero, per cui il riferimento al genitore è perfettamente inutile.

[DanieleC88]

In che modo?

Io ti domando di fare una cosa di questo tipo. Hai un albero come questo:

              4
         /         \
     2               5
  /     \           /    \
1        3      6       7

Sei nella situazione in cui conosci solo il puntatore ad un nodo che sai appartenere all'albero, una cosa del tipo:

node_t *ptr;

che, nell'esempio che ti faccio io, punta alla foglia con chiave 3.
Come scrivi - senza avere riferimenti al nodo genitore - un algoritmo che mi dia un puntatore al nodo che è successivo (in una visita in-order) a quello ricevuto in input? Nel mio caso vorrei restituisse un puntatore alla radice con chiave 4.

ciao

[fero86]

Originariamente inviato da DanieleC88

Scusa, perché? La radice avrà un genitore nullo, tutti gli altri verranno aggiornati di conseguenza durante gli inserimenti o le rimozioni, non vedo il problema. Quella di avere un puntatore al nodo padre è una prassi comune e sicuramente utile, tanto che sono sicuro sia riportata dalla stragrande maggioranza dei testi introduttivi agli algoritmi e alle strutture dati.

é naturale che la possibilitá di gestire la struttura dati esiste e che la speranza sia quella di non sbagliare mai e di non portarla mai in stato inconsistente, ma l'uomo inevitabilmente sbaglia e una struttura dati come quella é inutilmente complessa nel senso che ci sono molte piu possibilitá di inconsistenza e che é comunque possibile trovare implementazioni alternative dove i nodi non hanno il puntatore al padre.

Tanto per fare un esempio, senza avere un riferimento al nodo padre, se io ti chiedessi di scrivere una routine che riceve in input un generico nodo di un albero binario di ricerca e mi restituisce in output 1) il nodo suo successore, o 2) un valore nullo, se questo non esiste, come faresti?

non lo faccio e basta perché é una porcheria
o, come dicevo sopra, una pessima implementazione.
quando si espone un'interfaccia d'uso per uno strato di software la correttezza di design richiede che si esponga tutto in maniera opaca: non esiste che tu rifili al programmatore finale i puntatori alle tue strutture dati interne e che li rivuoi pure indietro
con un design del genere la validazione dell'input diventa impossibile.

per la visita ordinata di un albero in cui i nodi non hanno il puntatore al padre la soluzione migliore é esporre una funzione che visita tutti i nodi in ordine e per ogni nodo richiama una funzione di callback specificata dal programmatore finale. in alternativa il programmatore finale puó specificare un qualche dato che identifichi il nodo "corrente" della visita (ma non il puntatore al nodo stesso!), ad esempio l'indice del nodo nell'ordinamento, ma in questo modo la soluzione diventa inefficiente perché ad ogni passo in avanti devi ritrovare il nodo identificato da quell'indice; la cosa puó essere resa piu efficiente se si possono fare assunzioni, per esempio che l'albero sia completo e abbia altezza nota, oppure che avrá un certo numero massimo di nodi poiché in questo caso é possibile allocare staticamente un array ordinato di puntatori ai nodi che permette di ritrovare immediatamente il nodo i-esimo dell'ordinamento.

ciao

ah, gli effetti della VICIUS-ite, ancora a distanza di anni

[DanieleC88]

Originariamente inviato da fero86

é naturale che la possibilitá di gestire la struttura dati esiste e che la speranza sia quella di non sbagliare mai e di non portarla mai in stato inconsistente, ma l'uomo inevitabilmente sbaglia e una struttura dati come quella é inutilmente complessa nel senso che ci sono molte piu possibilitá di inconsistenza e che é comunque possibile trovare implementazioni alternative dove i nodi non hanno il puntatore al padre.

Nah, ti assicuro che l'ho implementato di persona con i puntatori al padre (sia nel caso di alberi normalissimi che alberi binari di ricerca che alberi AVL), e non aggiunge un grado di complicazione così elevato.

Originariamente inviato da fero86

non lo faccio e basta perché é una porcheria
o, come dicevo sopra, una pessima implementazione.
quando si espone un'interfaccia d'uso per uno strato di software la correttezza di design richiede che si esponga tutto in maniera opaca: non esiste che tu rifili al programmatore finale i puntatori alle tue strutture dati interne e che li rivuoi pure indietro
con un design del genere la validazione dell'input diventa impossibile.

Be', guarda, se scrivi il codice in C hai per forza di cose una struttura ben poco opaca, perché o ricorri a puntatori a strutture (che quindi esporranno i loro dati all'utente) o fai un giro contorto che - quello sì - complica in una maniera spropositata l'implementazione.
E magari ti taglia fuori anche la possibilità di scrivere funzioni che nella pratica sono semplicissime (vedasi la funzione "successivo" che ti dicevo prima).

Originariamente inviato da fero86

per la visita ordinata di un albero in cui i nodi non hanno il puntatore al padre la soluzione migliore é esporre una funzione che visita tutti i nodi in ordine e per ogni nodo richiama una funzione di callback specificata dal programmatore finale. in alternativa il programmatore finale puó specificare un qualche dato che identifichi il nodo "corrente" della visita (ma non il puntatore al nodo stesso!), ad esempio l'indice del nodo nell'ordinamento, ma in questo modo la soluzione diventa inefficiente perché ad ogni passo in avanti devi ritrovare il nodo identificato da quell'indice; la cosa puó essere resa piu efficiente se si possono fare assunzioni, per esempio che l'albero sia completo e abbia altezza nota, oppure che avrá un certo numero massimo di nodi poiché in questo caso é possibile allocare staticamente un array ordinato di puntatori ai nodi che permette di ritrovare immediatamente il nodo i-esimo dell'ordinamento.

Be', ti sei risposto da solo: diventa o 1) macchinoso, o 2) inefficiente, o 3) limitante.
E poi non vedo il problema: esulando dal linguaggio C, metti che passiamo al C++, se invece di avere una struttura nodo (di cui posso leggere e modificare tutti i campi) avessi avuto una classe nodo, dove i riferimenti a figli, nipoti, cugini e padri sono in campi privati?
Lì i "design issues" scompaiono senza alcun problema.

Originariamente inviato da fero86

ah, gli effetti della VICIUS-ite, ancora a distanza di anni

In realtà l'ho presa come abitudine non perché la usasse VICIUS, ma perché dà un tono più cordiale alla discussione. In questo forum c'è troppa gente che si vanta di conoscenze che non ha e scatena flame ad ogni occasione che può. A me invece interessa solo discutere.

ciao

[misterx]

ciao,
una dritta più che altro.
Devo inserire in un albero RB un certo numero di dati ed inizialmente la chiave è il codice di riconoscimento del dispositivo che inserisco nell'albero:

chiave, dato1, dato2, dato3 etc.....

Sapendo che gli alberi RB sono una estensione degli ABR e che quindi le chiavi vengono memorizzate in ordine, mi chiedevo se ad esempio si ha la richiesta di visualizzare l'intero albero ordinato per dato2 che non è chiave, se ha senso costruire un albero binario temporaneo usando come chiave dato2 e quindi fare una visita inorder partendo dalla foglia più a sx

grazie

ciao


approfitto per chedervi secondo voi cosa fa questa parte di codice di un RB

void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
	if(p != nil) {
        	inord(p->left,nil,op);
		(*op)(p);
        	inord(p->right,nil,op);
	}
}

/****************************************************************************/

void inorder(rbtree *p, void (*op)(rbnode *))
{
	inord(p->root, p->nil, op);
}

a me sembra che visiti l'albero in ordine ma mi chiedo se per stampare le chiavi contenute bell'albero devo aggiungere codice oppure c'è un modo per evitare di toccare tali funzioni già fatte

[DanieleC88]

Originariamente inviato da misterx

Sapendo che gli alberi RB sono una estensione degli ABR e che quindi le chiavi vengono memorizzate in ordine, mi chiedevo se ad esempio si ha la richiesta di visualizzare l'intero albero ordinato per dato2 che non è chiave, se ha senso costruire un albero binario temporaneo usando come chiave dato2 e quindi fare una visita inorder partendo dalla foglia più a sx

Mi sembra troppo complicato da fare... Io terrei traccia del numero di nodi presente nell'albero, creerei un'array con un numero uguale di elementi, e lo riempirei con una visita in-order. Poi lo ordinerei in base a dato2.
Verrebbe un tempo O(n) per la creazione dell'array, più O(n·log(n)) per l'ordinamento dell'array (dove n è il numero di nodi dell'albero), quindi per un costo totale di O(n·log(n)).

Originariamente inviato da misterx

mi chiedo se per stampare le chiavi contenute bell'albero devo aggiungere codice oppure c'è un modo per evitare di toccare tali funzioni già fatte

Devi scrivere una funzione che stampi il valore del nodo e passarla come secondo argomento ad "inorder()".

P.S.: un consiglio, quando hai:

Originariamente inviato da misterx

void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
	if(p != nil) {
        	inord(p->left,nil,op);
		(*op)(p);
        	inord(p->right,nil,op);
	}
}

quel (*op)(p) è un appesantimento sintattico inutile, funzionerà anche senza l'asterisco:

void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
	if(p != nil) {
        	inord(p->left,nil,op);
		op(p);
        	inord(p->right,nil,op);
	}
}

Mi sembra molto più leggibile.

[Fibrizio]

Originariamente inviato da DanieleC88

In che modo?

Io ti domando di fare una cosa di questo tipo. Hai un albero come questo:

              4
         /         \
     2               5
  /     \           /    \
1        3      6       7

Sei nella situazione in cui conosci solo il puntatore ad un nodo che sai appartenere all'albero, una cosa del tipo:

node_t *ptr;

che, nell'esempio che ti faccio io, punta alla foglia con chiave 3.
Come scrivi - senza avere riferimenti al nodo genitore - un algoritmo che mi dia un puntatore al nodo che è successivo (in una visita in-order) a quello ricevuto in input? Nel mio caso vorrei restituisse un puntatore alla radice con chiave 4.

ciao

basta guardare wikiedia, che riporta l'esempio del Lingaggio C
http://it.wikipedia.org/wiki/Albero_binario

[DanieleC88]

Su quella pagina vedo solo un'infarinatura abbastanza confusa di alberi, condita con con un codice C illeggibile e pieno di commenti al limite del ridicolo... ma non c'è la risposta alla mia domanda.

[Fibrizio]

Originariamente inviato da DanieleC88

Su quella pagina vedo solo un'infarinatura abbastanza confusa di alberi, condita con con un codice C illeggibile e pieno di commenti al limite del ridicolo... ma non c'è la risposta alla mia domanda.

essendo impossibile che tu conosca solo il nodo e non tutto l'albero la tua domanda è priva di senso, per questo ti ho rimandato alla pagina di wikipedia dove ci sono per lo meno le basi.

[DanieleC88]

Credimi, non c'è bisogno di insegnarmi le basi...
E la mia domanda non è affatto priva di senso. Pur conoscendo l'albero per intero (che non è scontato come pensi, dipende dall'implementazione), ripeto, come determini il successivo di un nodo avendo a disposizione un riferimento a quel preciso nodo e non sapendo dove è dentro un albero? Dovresti fare una intera visita per poter dire qual è che lo segue? Ok, ma in questo modo fai un bel salto di complessità da un tempo O(log(n)) ad O(n), con n il numero di nodi dell'albero. Ed è un salto gravissimo: se io ho un albero con 1024 nodi, nel primo caso ti determino il successivo in al massimo 10 passi, nel secondo potrei aver anche bisogno di farne 1024...

ciao

[Fibrizio]

Originariamente inviato da DanieleC88

Credimi, non c'è bisogno di insegnarmi le basi...
E la mia domanda non è affatto priva di senso. Pur conoscendo l'albero per intero (che non è scontato come pensi, dipende dall'implementazione), ripeto, come determini il successivo di un nodo avendo a disposizione un riferimento a quel preciso nodo e non sapendo dove è dentro un albero? Dovresti fare una intera visita per poter dire qual è che lo segue? Ok, ma in questo modo fai un bel salto di complessità da un tempo O(log(n)) ad O(n), con n il numero di nodi dell'albero. Ed è un salto gravissimo: se io ho un albero con 1024 nodi, nel primo caso ti determino il successivo in al massimo 20 passi, nel secondo potrei aver anche bisogno di farne 1024...

ciao

le possibilità sono:

1. non fai l'albero, l'albero binario serve principalmente per fare ricerca o rispondere a determinate esigenze algoritmiche, operando la ricerca a priori (grazie alla strutturazione) anziché a posteriori
2. utilizzi altri sistemi: vettori, matrici, map

come ti ho detto quello che chiedi non ha senso. se non ti fidi, come d'altronde mi auguro per te, ti consiglio di fare un po' di prove e ti renderai conto che gli alberi servono solo per fare ricerche con un certo criterio, delegando all'inserimento il tempo che perderebbe l'algoritmo nella ricerca in uno schema "disordinato".

[DanieleC88]

Originariamente inviato da Fibrizio

le possibilità sono:

1. non fai l'albero, l'albero binario serve principalmente per fare ricerca o rispondere a determinate esigenze algoritmiche, operando la ricerca a priori (grazie alla strutturazione) anziché a posteriori
2. utilizzi altri sistemi: vettori, matrici, map

E... non mi hai risposto...

Originariamente inviato da Fibrizio

come ti ho detto quello che chiedi non ha senso. se non ti fidi, come d'altronde mi auguro per te, ti consiglio di fare un po' di prove e ti renderai conto che gli alberi servono solo per fare ricerche con un certo criterio, delegando all'inserimento il tempo che perderebbe l'algoritmo nella ricerca in uno schema "disordinato".

È talmente senza senso che ciò che ti ho chiesto lo puoi trovare ad esempio a p.259 di Introduction to Algorithms (seconda edizione), di Cormen, Leiserson, Rivest, Stein. (Il Rivest in questione è uno degli autori di RSA ed MD5, tanto per farti capire il calibro.)
Anzi, ti dirò di più, è una richiesta talmente senza senso che è un passo essenziale per la cancellazione di un nodo da un albero binario di ricerca. Ma magari non ti fidi, provaci anche tu.

ciao