View Full Version : [ANSI C] - Albero binario di ricerca
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;
};
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
come non detto, sono passato agli alberi RB
ciao
coocooche
01-06-2010, 22:33
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
01-06-2010, 22:43
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.
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 :asd:
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
02-06-2010, 01:12
"up" é evidentemente il puntatore al padre, un campo che nel 99% dei casi indica una pessima implementazione :asd:
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? :D
ciao ;)
Fibrizio
02-06-2010, 01:19
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? :D
ciao ;)
a questo sopperisce il criterio di ricerca che sottostà all'albero, per cui il riferimento al genitore è perfettamente inutile.
DanieleC88
02-06-2010, 01:39
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 ;)
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? :D non lo faccio e basta perché é una porcheria :stordita:
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 :stordita:
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 :D
DanieleC88
02-06-2010, 09:51
é 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. :)
non lo faccio e basta perché é una porcheria :stordita:
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 :stordita:
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).
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? :p
Lì i "design issues" scompaiono senza alcun problema.
ah, gli effetti della VICIUS-ite, ancora a distanza di anni :D
:asd:
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 ;)
:Prrr:
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
02-06-2010, 18:39
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)).
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:
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
02-06-2010, 21:43
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
02-06-2010, 21:49
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
02-06-2010, 22:00
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
02-06-2010, 22:08
Credimi, non c'è bisogno di insegnarmi le basi... :D
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
02-06-2010, 22:20
Credimi, non c'è bisogno di insegnarmi le basi... :D
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
02-06-2010, 22:42
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... :wtf:
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) (http://en.wikipedia.org/wiki/Introduction_to_Algorithms), 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 ;)
Fibrizio
02-06-2010, 22:49
È talmente senza senso che ciò che ti ho chiesto lo puoi trovare ad esempio a p.259 di Introduction to Algorithms (seconda edizione) (http://en.wikipedia.org/wiki/Introduction_to_Algorithms), 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 ;)
non vedo niente di simile a pagina 259 :stordita:
inoltre il fatto che non abbia senso non impedisce che lo si faccia.
edit: inoltre non è per nulla essenziale. la cancellazione si fa arrivando al valore precedente e verificando che il valore figlio contenga i parametri del nodo ricercato, se sì si sostituisce il puntatore al figlio col figlio del figlio. :asd: dunque non è essenziale.
DanieleC88
02-06-2010, 22:56
non vedo niente di simile a pagina 259 :stordita:
Io ho l'edizione americana, tu quale hai? Magari è solo su un'altra pagina, è l'algoritmo "Tree-Successor", lo descrive nel capitolo riguardante gli alberi binari di ricerca.
inoltre il fatto che non abbia senso non impedisce che lo si faccia.
E non è ciò che ti ho chiesto. È una cosa sensata e ben motivata, volevo arrivare a rendere chiaro questo punto... Non è uno "spreco".
ciao ;)
DanieleC88
02-06-2010, 23:26
edit: inoltre non è per nulla essenziale. la cancellazione si fa arrivando al valore precedente e verificando che il valore figlio contenga i parametri del nodo ricercato, se sì si sostituisce il puntatore al figlio col figlio del figlio. :asd: dunque non è essenziale.
Forse sono riuscito a decifrare questa frase. :stordita:
Hmm. Come arrivi al "valore precedente"? Diciamo che ci arrivo: se è una foglia funziona. Se il nodo ha un solo figlio, funziona. Se il nodo ha due figli, quale dei due prenderebbe il suo posto secondo la tua tecnica? :)
ciao ;)
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)).
Devi scrivere una funzione che stampi il valore del nodo e passarla come secondo argomento ad "inorder()".
P.S.: un consiglio, quando hai:
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. :)
ciao,
grazie come sempre. Quello che osservi è codice già pronto che sto utilizzando senza reinventare l'acqua calda, come dice il docente, ed in alcuni suoi punti lo trovo un C piuttosto complicato.
ciao
Fibrizio
03-06-2010, 06:37
Hmm. Come arrivi al "valore precedente"? Diciamo che ci arrivo: se è una foglia funziona. Se il nodo ha un solo figlio, funziona. Se il nodo ha due figli, quale dei due prenderebbe il suo posto secondo la tua tecnica? :)
E' irrilevante se ha uno o due figli, il problema si ripresenta anche se il nodo ha un riferimento al genitore e si risolve ordinando i due figli secondo il criterio di ordinamento dell'albero. Nel caso specifico del tuo esempio se togliamo il nodo con valore 2 possiamo tranquillamente reinserire sia l'1 che il 3, visto che l'ordinamento non dipende dall'ordine di inserimento.
Fibrizio
03-06-2010, 07:04
Io ho l'edizione americana, tu quale hai? Magari è solo su un'altra pagina, è l'algoritmo "Tree-Successor", lo descrive nel capitolo riguardante gli alberi binari di ricerca.
Ho giust'appunto l'edizione americana, dal momento che preferisco i libri di informatica in lingua originale. A pagina 259 non c'è niente di simile, ma un problema da risolvere. Il tema di successori e predecessori in un albero binario viene trattato nel capitolo 12.2 Querying a binary search tree (così non ci si sbaglia con le pagine), dove viene spiegato chiaramente che
The running time of TREE-SUCCESSOR on a tree of height h is O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR,which is symmetric to TREE-SUCCESSOR, also runs in time O(h).
Ossia il predecessore viene calcolato in maniera simmetrica al successore e non vi è necessità di un puntatore specifico, ma solo di destro e sinistro, e anzi impiegano perfino lo stesso tempo di calcolo!
Da cui deriva anche il teorema
The dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and
PREDECESSOR can be made to run in O(h) time on a binary search tree of height h.
Insomma non mi è ben chiaro dove hai trovato l'illuminante capitolo sull'essenzialità (?) di un puntatore al predecessore o alla radice dell'albero.
Che seppure sia possibile fare è tutt'altro che essenziale.
non vedo niente di simile a pagina 259 :stordita:
inoltre il fatto che non abbia senso non impedisce che lo si faccia.
edit: inoltre non è per nulla essenziale. la cancellazione si fa arrivando al valore precedente e verificando che il valore figlio contenga i parametri del nodo ricercato, se sì si sostituisce il puntatore al figlio col figlio del figlio. :asd: dunque non è essenziale.
Dipende tutto da quello che si vuole fare...se si cercano le prestazioni è sicuramente meglio avere il puntatore al nodo che il valore, perché si arriva direttamente al nodo senza, nel worst case, attraversare tutta la profondità dell'albero.
ciao,
non ho ancora ben chiaro questo codice per la visita in-ordine di un albero RB.
void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
if(p != nil) {
inord(p->left,nil,op);
printf("%d ", p->v);
inord(p->right,nil,op);
}
}
/****************************************************************************/
void inorder(rbtree *p, void (*op)(rbnode *))
{
inord(p->root, p->nil, op);
}
allocando un albero con:
rbtree *MioLberoRB;
MioLberoRB = creaAlberoRB();
e poi inserisco un pò di dati;
inserisci(MioLberoRB, 18 , 2, 3 ,4);
inserisci(MioLberoRB, 20 , 20, 30 ,40);
inserisci(MioLberoRB, 5 , 22, 32 ,42);
ora chiamo la inorder con: inord(MioLberoRB, treemin(MioLberoRB));
note: la treemin() mi ritorna la chiave minima dell'albero e che io passo come tipo nodo
Fibrizio
03-06-2010, 08:59
ciao,
non ho ancora ben chiaro questo codice per la visita in-ordine di un albero RB.
void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
if(p != nil) {
inord(p->left,nil,op);
printf("%d ", p->v);
inord(p->right,nil,op);
}
}
/****************************************************************************/
void inorder(rbtree *p, void (*op)(rbnode *))
{
inord(p->root, p->nil, op);
}
allocando un albero con:
rbtree *MioLberoRB;
MioLberoRB = creaAlberoRB();
e poi inserisco un pò di dati;
inserisci(MioLberoRB, 18 , 2, 3 ,4);
inserisci(MioLberoRB, 20 , 20, 30 ,40);
inserisci(MioLberoRB, 5 , 22, 32 ,42);
ora chiamo la inorder con: inord(MioLberoRB, treemin(MioLberoRB));
note: la treemin() mi ritorna la chiave minima dell'albero e che io passo come tipo nodo
cos'è che non ti è chiaro esattamente? La ricerca o l'ordinamento?
Fibrizio
03-06-2010, 09:05
Dipende tutto da quello che si vuole fare...se si cercano le prestazioni è sicuramente meglio avere il puntatore al nodo che il valore, perché si arriva direttamente al nodo senza, nel worst case, attraversare tutta la profondità dell'albero.
Non ti cambia nulla, dal momento che devi effettuare lo scorrimento fino al nodo in ogni caso per leggerlo.
ciao,
nel frattempo ho modificato il codice e quello che non mi è chiaro è come funziona questa parte di codice:
void inord(rbnode *p, rbnode *nil)
{
if(p != nil) {
inord(p->left,nil);
printf("%d ",p->v);
inord(p->right,nil);
}
}
void inorder(rbtree *p)
{
inord(p->root, p->nil);
}
ora passo solo il puntatore della radice ed inserendo valori casuali, questi mi vengono mostrati in odine; mi chiedo se avendo implementato un RB è perchè questi sono già ordinati nell'albero ?
Fibrizio
03-06-2010, 09:16
ciao,
nel frattempo ho modificato il codice e quello che non mi è chiaro è come funziona questa parte di codice:
void inord(rbnode *p, rbnode *nil)
{
if(p != nil) {
inord(p->left,nil);
printf("%d ",p->v);
inord(p->right,nil);
}
}
void inorder(rbtree *p)
{
inord(p->root, p->nil);
}
ora passo solo il puntatore della radice ed inserendo valori casuali, questi mi vengono mostrati in odine; mi chiedo se avendo implementato un RB è perchè questi sono già ordinati nell'albero ?
Ok, ho capito. Allora l'ordine deriva dal metodo con cui si compone l'albero. Per esempio inserendo dei numeri i più grandi a destra e i più piccoli a sinistra.
Quando cominci a leggere l'albero il codice dice:
if(p != nil) { se p è diverso da nil, ossia se quello che segue è un nodo allora
inord(p->left,nil);
richiama la funzione stessa sul ramo di sinistra
Ora immagina che l'albero sia quello proposto prima da DanieleC88
4
/ \
2 5
/ \ / \
1 3 6 7
Prendo 4, il ramo di sinistra ha un valore, è 2, prendo 2, il ramo di sinistra ha un valore, è 1, prendo 1, il ramo di sinistra non ha alcun valore,
la funzione inord sul ramo di sinistra di 1 non fa niente, segue
printf("%d ",p->v);
che stampa 1
segue inord sul ramo di destra di 1, non stampa nulla, la funzione finisce.
erano rimaste in pausa le funzioni inord su 2 e 4. torniamo a 2,
stampa 2 su schermo con printf, poi esegue il controllo sul ramo di destra, è 3, prende 3. esegue il controllo sul ramo di sinistra, non c'è nulla, stampa 3, esegue il controllo a destra, non c'è nulla. la funzione finisce, si torna a 2.
Anche su 2 non c'è altro da fare, si torna su 4 e si stampa, si prende la funzione sul ramo di destra.
ecc ecc
Alla fine come vedi abbiamo stampato 1, 2, 3, 4 ...e così via, in ordine. Se vuoi invertire l'ordine fai inord prima sul ramo di destra e poi su quello di sinistra.
ciao e grazie,
ho notato che per capire si dovrebbe scoprire come funzionala insertRB ma è piuttosto complessa e richiederebbe troppo tempo per essere compresa; importante è sapere che i dati vengono messi ordinati come negli ABR in quanto gli RB sono ABR con in aggiunta la colorazione in aggiunta alle funzioni per mantenerlo tale giusto ?
rbnode *simpleinsert(rbtree *tree, int k)
{
rbnode *q = malloc(sizeof(rbnode));
rbnode *r = tree->root;
rbnode *s = tree->nil;
if(!q) {
fprintf(stderr,"Errore di allocazione C\n");
exit(-4);
}
q->v = k;
q->left = q->right = tree->nil;
q->c = red;
while(r != tree->nil) {
s = r;
r = k < r->v ? r->left : r->right;
}
q->up = s;
if(s == tree->nil)
return tree->root = q;
if(k < s->v)
s->left = q;
else
s->right = q;
return q;
}
/****************************************************************************/
void rbinsert(rbtree *tree, int k)
{
rbnode *x = simpleinsert(tree, k);
rbnode *y;
while(x != tree->root && x->up->c == red) {
if(x->up == x->up->up->left) { /* caso L */
y = x->up->up->right;
if(y->c == red) {
x->up->c = black; /* caso 1L */
y->c = black; /* caso 1L */
x->up->up->c = red; /* caso 1L */
x = x->up->up; /* caso 1L */
} else {
if(x == x->up->right) /* caso 2L */
leftrotate(tree,x = x->up); /* caso 2L */
x->up->c = black; /* caso 3L */
x->up->up->c = red; /* caso 3L */
rightrotate(tree,x->up->up); /* caso 3L */
}
} else { /* caso R */
y = x->up->up->left;
if(y->c == red) {
x->up->c = black; /* caso 1R */
y->c = black; /* caso 1R */
x->up->up->c = red; /* caso 1R */
x = x->up->up; /* caso 1R */
} else {
if(x == x->up->left) /* caso 2R */
rightrotate(tree,x = x->up); /* caso 2R */
x->up->c = black; /* caso 3R */
x->up->up->c = red; /* caso 3R */
leftrotate(tree,x->up->up); /* caso 3R */
}
}
}
tree->root->c = black;
}
Non ti cambia nulla, dal momento che devi effettuare lo scorrimento fino al nodo in ogni caso per leggerlo.
Allora...mettiamo delle semplici operazioni per entrambi i casi.
Caso in cui si ritornano nodi:
struct node * find_first_greater_than(int x); //ritorna un nodo se presente o NULL
void delete(struct node * n); //elimina il nodo
Caso in cui si ritornano valori:
bool find_first_greater_than(int x, int * v); //ritorna true se l'ha trovato, mette il valore in *v
void delete(int v); //elimina il valore v
Prima di tutto i due approcci non sono equivalenti. Con la seconda delete non siamo sicuri di elminare proprio quel v, visto che nel frattempo l'albero potrebbe essere stato ribilanciato.
La prima funzione in entrambi i casi ha un tempo di esecuzione proporzionale alla profondità dell'albero.
La seconda invece:
- nel primo caso ha un tempo di esecuzione costante o al proporzionale al tempo necessario a ribilanciare l'albero
- nel secondo caso ha un tempo di esecuzione proporzionale al tempo necessario a ribilanciare l'albero + il tempo di ricerca
Nel caso di alberi di dimensione molto grande questa differenza è tutt'altro che trascurabile.
ciao e grazie,
ho notato che per capire si dovrebbe scoprire come funzionala insertRB ma è piuttosto complessa e richiederebbe troppo tempo per essere compresa; importante è sapere che i dati vengono messi ordinati come negli ABR in quanto gli RB sono ABR con in aggiunta la colorazione in aggiunta alle funzioni per mantenerlo tale giusto ?
Sono degli alberi binari di ricerca auto bilanciati. Tutto il codice che vedi in più serve per bilanciare nuovamente l'albero.
Stranamente wikipedia è fatta veramente bene in questo caso: http://it.wikipedia.org/wiki/RB-Albero
DanieleC88
03-06-2010, 11:27
E' irrilevante se ha uno o due figli, il problema si ripresenta anche se il nodo ha un riferimento al genitore e si risolve ordinando i due figli secondo il criterio di ordinamento dell'albero. Nel caso specifico del tuo esempio se togliamo il nodo con valore 2 possiamo tranquillamente reinserire sia l'1 che il 3, visto che l'ordinamento non dipende dall'ordine di inserimento.
La fai un po' troppo semplice, se ti avessi chiesto di cancellare la radice dell'albero nel mio esempio? (Che è uno particolarmente piccolo e ben ordinato, non è niente di complesso.)
[...] dove viene spiegato chiaramente che
The running time of TREE-SUCCESSOR on a tree of height h is O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR,which is symmetric to TREE-SUCCESSOR, also runs in time O(h).
Ossia il predecessore viene calcolato in maniera simmetrica al successore e non vi è necessità di un puntatore specifico, ma solo di destro e sinistro, e anzi impiegano perfino lo stesso tempo di calcolo!
Comincio a pensare che non sai leggere. Dal momento il successore di un nodo lo puoi trovare o come il nodo di valore minimo nel sottoalbero destro oppure... come il primo nodo antenato nel quale sali "da sinistra"... risalendovi appunto attraverso dei puntatori ai genitori. Nel testo che mi hai citato non c'è assolutamente niente che sostenga la tua tesi, semmai il contrario. :)
Il testo ti sta appunto dicendo che nel caso peggiore possibile hai l'invocazione dell'algoritmo in un albero completo, sulla foglia che contiene il valore massimo nel sottoalbero sinistro della radice, e che dovrà quindi risalire lungo tutta l'altezza dell'albero fino a raggiungere la radice (che è il suo successore), è da lì che viene il tempo O(h) = O(log(n)) che mi hai addirittura citato (con h = altezza dell'albero, n = numero di nodi).
Insomma non mi è ben chiaro dove hai trovato l'illuminante capitolo sull'essenzialità (?) di un puntatore al predecessore o alla radice dell'albero.
Che seppure sia possibile fare è tutt'altro che essenziale.
Ricapitoliamo: ti ho chiesto da due pagine di trovare un algoritmo che mi restituisca il successore di un nodo in un albero binario di ricerca senza avere riferimenti ai nodi genitori, e tu mi stai semplicemente dicendo che è un'operazione senza senso. Ti ho fatto l'esempio della cancellazione di un nodo in un albero binario di ricerca dove, guarda caso, un pezzo importante (e quindi sensato) è proprio la ricerca del nodo successore al nodo da cancellare, e continui a dirmi che non è così.
Che vogliamo fare a questo punto? Possiamo continuare ad oltranza, decidi tu. :)
Se poi non sei convinto di ciò che dico, puoi anche leggere l'ultima risposta di cionci e valutare da te. La sua parola è sicuramente più autorevole della mia, se non ti fidi né di me né del Cormen.
ciao ;)
Sono degli alberi binari di ricerca auto bilanciati. Tutto il codice che vedi in più serve per bilanciare nuovamente l'albero.
Stranamente wikipedia è fatta veramente bene in questo caso: http://it.wikipedia.org/wiki/RB-Albero
ciao,
effettivamente interessa maggiormente come lavora concettualmente un RB invece di conoscere a fondo l'implentazione finale.
Approfitto per una dritta visto il mio digiuno di C.
Devo leggere da standard input una stringa del tipo:
12 20 45 90 ......... e così via
avevo pensato ad una cosa del tipo
int cifra;
while((cifra = getchar()) != '\n')
ma credo di essere in parte sulla strada sbagliata
ciao
DanieleC88
03-06-2010, 11:58
Non andava bene scanf()? :D
Non andava bene scanf()? :D
ciao,
sai che lo sto provando proprio ora ma non funziona con lo '\n' ?
while((scanf("%d",&cifra)) != '\n')
ma funziona con '\0'
DanieleC88
03-06-2010, 12:06
Ma scanf() non ti restituisce l'ultimo carattere letto, ti restituisce il numero di elementi letti dall'input. :)
Ma scanf() non ti restituisce l'ultimo carattere letto, ti restituisce il numero di elementi letti dall'input. :)
ciao,
quindi while((scanf("%d",&cifra)) != '\0')
è corretto giusto ?
ciao,
quindi while((scanf("%d",&cifra)) != '\0')
è corretto giusto ?
Mi immagino che tu non sappia quanti valori hai nella riga...
In tal caso usa fgets per leggere una riga intera, poi usa sscanf per leggere i valori dalla riga fino a quando non ti torna 0.
DanieleC88
03-06-2010, 12:18
Dovrebbe funzionare, ma:
while((scanf("%d",&cifra)) != '\0')
dovrebbe diventare:
while((scanf("%d",&cifra)) != 0)
dal momento che ti restituisce un intero.
ciao ;)
Mi immagino che tu non sappia quanti valori hai nella riga...
In tal caso usa fgets per leggere una riga intera, poi usa sscanf per leggere i valori dalla riga fino a quando non ti torna 0.
ciao,
esatto. Per ora sto usando la scanf ed avendo provato con almeno 10000 valori in input credo che funzioni.
ciao e grazie
Dovrebbe funzionare, ma:
while((scanf("%d",&cifra)) != '\0')
dovrebbe diventare:
while((scanf("%d",&cifra)) != 0)
dal momento che ti restituisce un intero.
ciao ;)
ciao,
direi che ci siamo.
Un'altra dritta: ho l'albero RB popolato ed uso la funzione inorder per visualizzare il suo contenuto ordinato per chiave. I campi riferiti ad ogni nodo sono:
A, B, C, D, E
quando uso la inorder mi viene mostrato quindi l'albero riordinato per A; se necessitassi di riordinare per C ad esempio vale la pena ricostruirsi un nuovo albero usando C come chiave e quindi usare inorder per visualizzare l'albero ordinato per C oppure ci sono metodi più ingegnosi ?
ciao
DanieleC88
03-06-2010, 14:25
A questo ti avevo già risposto in prima pagina:
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)).
A questo ti avevo già risposto in prima pagina:
ciao,
scusa ma sono proprio fuso, non ricordavo più di averlo già chiesto.
Volevo evitare di aggiungere ulteriore codice e magari sfruttare la inorder esistente.
E se creassi un albero temporaneo solo con la chiave che mi serve riordindare mettendo a zero gli altri campi e poi sfruttando la inorder, riodinerei l'output dell'albero temporaneo usandolo però come argomento di input per la RBsearch, così facendo verrebbe troppo costoso ?
ciao
DanieleC88
03-06-2010, 14:47
Dovrebbe venire ugualmente O(n·log(n)), se ho capito bene cosa intendi fare. :)
è un'idea per continuare a sfruttare sempre la stessa struttura
ciao
ciao,
l'idea l'ho implementata e funziona correttamente. Ho un dubbio quando si cancella un nodo sia esso nero oppure rosso che se non ricordo va rimesso tutto com'era
niente, sto ripassando un pò la teoria :)
ciao,
è possibile con una qualche tecnica dopo aver memorizzato area e posizione di rettangoli in un albero RB conoscere se tali aree si sovrappongono ?
grazie
ciao,
è possibile con una qualche tecnica dopo aver memorizzato area e posizione di rettangoli in un albero RB conoscere se tali aree si sovrappongono ?
grazie
A che ti serve memorizzare area e posizione di un rettangolo in un albero RB ? Cioè...quale ordinamento attui ?
A che ti serve memorizzare area e posizione di un rettangolo in un albero RB ? Cioè...quale ordinamento attui ?
ciao,
onestamente non lo so, è un'idea che mi è venuta osservando il mondo dei database dove fai unione o intersezione di dati.
Ho pensato che chi si occupa di grafica, magari ha escogitato un qualche modo per intersecare aree in un qualche modo che non conosco e magari attraverso gli RB che trovo molto prestanti.
Il link su wikipedia li presenta come strutture dati adatte per il real time.
ciao
La misura di questi rettangoli è in interi o float ? Di quanti rettangoli si parla ? Hanno dei limiti di coordinate ? Quando ti servono i risultati ? Ogni volta che aggiungi un rettangolo o solo alla fine dell'elaborazione ?
La misura di questi rettangoli è in interi o float ? Di quanti rettangoli si parla ? Hanno dei limiti di coordinate ? Quando ti servono i risultati ? Ogni volta che aggiungi un rettangolo o solo alla fine dell'elaborazione ?
ciao,
dev'essere fatto in tempo reale
ciao,
dev'essere fatto in tempo reale
Il fatto che debba essere fatto in tempo reale ancora non mi dice niente ;)
Se deve essere fatto in tempo reale, quale dead line hai ? Quanti rettangoli possono essere aggiunti all'inizio di ogni periodo (uno, cento, mille, oppure vengono eliminati tutti e ricreati tutti).
All'inizio dell'elaborazione, quando ti si presentano i primi rettangoli hai un tempo di compensazione ?
Il fatto che debba essere fatto in tempo reale ancora non mi dice niente ;)
Se deve essere fatto in tempo reale, quale dead line hai ? Quanti rettangoli possono essere aggiunti all'inizio di ogni periodo (uno, cento, mille, oppure vengono eliminati tutti e ricreati tutti).
All'inizio dell'elaborazione, quando ti si presentano i primi rettangoli hai un tempo di compensazione ?
ciao,
forse sono andato un pò fuori strada, meglio se ci penso ancora un pochino.
Ho un'altra domanda: come duplico un albero RB ?
ciao
DanieleC88
04-06-2010, 15:47
Potresti fare una sorta di visita in cui replichi ogni informazione del nodo in questione in un nuovo nodo radice, associando poi al sottoalbero sinistro e destro la chiamata ricorsiva dell'algoritmo stesso. Al termine avresti un duplicato dell'albero su cui hai invocato la funzione, non dovrebbe essere difficile scriverla.
ciao e grazie
sto leggendo da stdin con
while((scanf("%d",&carattere)) != 0)
ma al termine vorrei rileggere una seconda volta la stringa passata come si riavvolge l'input ?
ciao
DanieleC88
04-06-2010, 18:53
È uno stream: le letture a buon fine lo svuotano di ciò che è stato letto, quindi non puoi fare ciò che vuoi. Leggi una riga per volta in un buffer dinamico e opera su quello. :)
ciao,
peccato, mi avrebbe forse semplificato un pò la vita.
grazie
È uno stream: le letture a buon fine lo svuotano di ciò che è stato letto, quindi non puoi fare ciò che vuoi. Leggi una riga per volta in un buffer dinamico e opera su quello. :)
e salvare lo stream in un buffer dinamico per poi farlo rileggere alla scanf a piacere ?
DanieleC88
04-06-2010, 20:48
Come ti ha detto cionci in precedenza: leggi riga per riga con fgets(), poi usi sscanf() per leggere i dati.
Come ti ha detto cionci in precedenza: leggi riga per riga con fgets(), poi usi sscanf() per leggere i dati.
ciao,
mi sa che non le ho mai usate a questo modo.
Io sto lavorando in "real time" se così si può dire e lo svantaggio è che l'output è incontrollabile a meno che prima di generarlo non si faccia per due volte la stessa cosa
while((scanf("%d",&cifra)) != 0)
tramite questa dallo standdard input:
- leggo una cifra e la successiva
- faccio la differenza
- uso la inorder per cercare nell'RB
- se il campo desiderato soddisfa i requisiti di cifra e dimensioni lo mando in display
- tutti gli altri dati dell'albero che soddisfano cifra ma presentano dimensioni minori vengono scartati
funziona bene tranne il caso in cui quando un solo dato soddisfa i requisiti di cifra ma di cifre ne ho testate n, allora dovrebbe visualizzare un messaggio ma, siccome sto mandando in dislpay il risultato in realtime tale output non è controllabile a meno che:
- faccio una inorder di test che mi verifica se il numero di dati contenuti nell'albero è pari al numero di cifre passate per il test
- se il test viene superato
- faccio la inorder come sopra
ciao
Fibrizio
07-06-2010, 10:39
La fai un po' troppo semplice, se ti avessi chiesto di cancellare la radice dell'albero nel mio esempio? (Che è uno particolarmente piccolo e ben ordinato, non è niente di complesso.)
Che differenza dovrebbe fare dall'eliminare un qualsiasi nodo? :asd:
Associ alla root i nodi successivi secondo la stessa logica del nodo intermedio. Inoltre se conoscessi il predecessore cosa ti cambierebbe mai nell'eliminazione della radice? Quel che è peggio dovresti cambiarla in tutti i nodi.
Comincio a pensare che non sai leggere. Dal momento il successore di un nodo lo puoi trovare o come il nodo di valore minimo nel sottoalbero destro oppure... come il primo nodo antenato nel quale sali "da sinistra"... risalendovi appunto attraverso dei puntatori ai genitori. Nel testo che mi hai citato non c'è assolutamente niente che sostenga la tua tesi, semmai il contrario. :)
Il testo ti sta appunto dicendo che nel caso peggiore possibile hai l'invocazione dell'algoritmo in un albero completo, sulla foglia che contiene il valore massimo nel sottoalbero sinistro della radice, e che dovrà quindi risalire lungo tutta l'altezza dell'albero fino a raggiungere la radice (che è il suo successore), è da lì che viene il tempo O(h) = O(log(n)) che mi hai addirittura citato (con h = altezza dell'albero, n = numero di nodi).
se tu avessi letto tutto il testo avresti capito e siccome hai il libro sottomano dubito avrai difficoltà a leggere l'ovvio.
Ricapitoliamo: ti ho chiesto da due pagine di trovare un algoritmo che mi restituisca il successore di un nodo in un albero binario di ricerca senza avere riferimenti ai nodi genitori
Per avere un successore ad un nodo a che ti servono mai i riferimenti genitori? :asd:
e tu mi stai semplicemente dicendo che è un'operazione senza senso.
Appunto. :asd:
Ti ho fatto l'esempio della cancellazione di un nodo in un albero binario di ricerca dove, guarda caso, un pezzo importante (e quindi sensato) è proprio la ricerca del nodo successore al nodo da cancellare, e continui a dirmi che non è così.
Ti ho detto che non è importante conoscere il nodo genitore, non il figlio. :asd: E l'ho detto anche alquanto chiaramente svariati post fa.
Temo che il C fai da te continui a fare di questi danni alla gente. :rolleyes:
DanieleC88
07-06-2010, 11:03
Vabbe'. Visto e considerato che ho provato a spiegarti come si fanno le cose nella pratica e perché nella teoria, che le motivazioni te le ha provate a spiegare anche cionci, che riesci a contraddire anche ciò che leggi tu stesso sul Cormen senza nemmeno capire di cosa si sta parlando, visto che ti chiedo degli esempi pratici e te la svigni con un "non ha senso" o "non ha differenza" (quando non è così) e soprattutto visto che sei così aperto al dialogo, sai che ti dico?
Continua a sghignazzare, noi facciamo lo stesso di te e del tuo comportamento (http://forum.gamesvillage.it/showthread.php?177664-1-L-Eterna-Guerra-Tra-Xbox-Pc-E-Ps2). :)
Dalle parti mie si dice saggiamente che "a lava' 'a capa 'u ciuccio se perde tempo, acqua e sapone", per cui non lo farò.
Continua così che sei sulla buona strada.
ciao ;)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.