[c++]Dubbio su costruzione dinamica di Alberi in>> da file di testo
Ora volevo iniziare a discutere su un dubbio che mi sta venendo e che sarà un mio problema prossimo....
Quando si parla di alberi che vanno costruiti in tempo "reale" ossia che la struttura viene immessa da tastiere o viene letta da file. Ho sempre visto alberi già formati dove "staticamente" si costruiva root figlio destro poi sinistro e compagnia bella (lavorando di puntatori)
Per costruirlo di volta in volta e sottoporre quindi alberi diversi ad un algoritmo come si fa? Forse è una domanda stupida, ma che consigli potete darmi?
Mi spiego con un esempio.. Una "interview" di google chiedeva il Lowest Common Ancestor (LCA Problem).
Problema classico, ad esempio:
http://www.geeksforgeeks.org/lowest-com ... ree-set-1/
Io vorrei sottoporre alberi diversi, magari scritti in file di testo, che il programma legge e forma di volta in volta.
Non voglio una cosa scritta così:
Node * root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
Vorrei una cosa flessibile che "capisca" come formare l'albero usando un ciclo al massimo.
Ossia se nel file.txt abbiamo
-------------------------------------------------------------
7
1 2
1 3
2 4
2 5
3 6
3 7
-------------------------------------------------------------
Possiamo pensare che la prima riga contiene n, ossia il numero di nodi totale.
Le successive n-1 contengono, ciascuna, una coppia padre / figlio.
Ecco, avere una 20 di file del genere, tutti diversi tra loro, generano 20 alberi diversi. Giusto?
Vorrei capire come scrivere del codice flessibile che legga e formi, in modo intelligente, queste strutture.
Risposte
Non l'ho provato.. funziona? Se fa quello per cui è stato pensato non ha importanza quanto sia bello o brutto. Ci sono ovviamente ragioni per preferire un qualche tipo di soluzione ad un altro, ma non credo che questa sia una di quelle situazioni.
Ti inviterei più che altro a porti alcune domande: è possibile, a tuo parere, fare la ricerca del LCA senza memorizzare l'intero percorso? Sapresti PROVARE la correttezza del codice? Una proprietà utile di un formato di file è quella di non poter rappresentare un input invalido. Se il file rispetta le specifiche del formato, allora rappresenta un input corretto. Nel tuo caso avresti un albero valido. Credi sia possibile avere un formato di questo tipo per il tuo tipo di input? Riesci a pensare ad alcuni miglioramenti nel tuo codice? Per esempio modi per velocizzarlo o usare meno memoria?
Ti inviterei più che altro a porti alcune domande: è possibile, a tuo parere, fare la ricerca del LCA senza memorizzare l'intero percorso? Sapresti PROVARE la correttezza del codice? Una proprietà utile di un formato di file è quella di non poter rappresentare un input invalido. Se il file rispetta le specifiche del formato, allora rappresenta un input corretto. Nel tuo caso avresti un albero valido. Credi sia possibile avere un formato di questo tipo per il tuo tipo di input? Riesci a pensare ad alcuni miglioramenti nel tuo codice? Per esempio modi per velocizzarlo o usare meno memoria?
Apa con quanta Saggezza e Nobiltà d''Animo porti a crescere la mia testolina dura!!! 
Dovrebbe funzionare benino ed in O(n) ma, di sicuro, si può migliorare... Ad esempio si potrebbe memorizzare il valore del proprio Patriarca (FAMMELA PASSARE CHE TE LA SEI CERCATA TE!) nel valore chiave dei nodi. Ogni nodo quindi ha memorizzato il padre e si risparmierebbe un po' di memoria
Si dovrebbe pure verificare se i nodi esistano o meno, migliorando almeno la logica
Dovrebbe funzionare benino ed in O(n) ma, di sicuro, si può migliorare... Ad esempio si potrebbe memorizzare il valore del proprio Patriarca (FAMMELA PASSARE CHE TE LA SEI CERCATA TE!) nel valore chiave dei nodi. Ogni nodo quindi ha memorizzato il padre e si risparmierebbe un po' di memoria
Si dovrebbe pure verificare se i nodi esistano o meno, migliorando almeno la logica
In che modo avere accesso al padre ridurrebbe la memoria? Per ogni nodo avresti in effetti un puntatore in più.. Intendi dire sostituire il percorso intero con solo il padre?
Durante la lettura conosci in anticipo i nodi che dovrai cercare.. ma questa informazione non la stai usando. Hai idea di un metodo per migliorare il codice utilizzando questo fatto? Sapresti valutare quanto vantaggio possa offrire questa nuova versione?
Durante la lettura conosci in anticipo i nodi che dovrai cercare.. ma questa informazione non la stai usando. Hai idea di un metodo per migliorare il codice utilizzando questo fatto? Sapresti valutare quanto vantaggio possa offrire questa nuova versione?
Infatti ho scritto una cagXXXtona!!!!Si può migliorare cercando di "cambiare stile" e non memorizzare la stringa del percorso ogni volta....
Comunque si può migliorare in termini di spazio e basta (se non sbaglio!) [size=50]SE NO CORREGGIMI MIO MENTORE!!!!!!!!!!![/size]
È possibile migliorarlo anche in termini di tempo. Il tuo codice deve infatti visitare tutti i nodi, ma è possibile cercare solo in un insieme ridotto di nodi. La soluzione è collegata ad una domanda che ti ho fatto nel mio precedente post.
Ma resta il caso pessimo O(n) o no?
Dici di ridurre eventuali ricerche inutili mettendo diverse condizioni? Soprattutto se ci sono più antenati comuni?
Dici di ridurre eventuali ricerche inutili mettendo diverse condizioni? Soprattutto se ci sono più antenati comuni?
Intendo dire che se sai quali nodi devi considerare puoi memorizzarli immediatamente senza doverli cercare e quindi partire dal basso invece che dall'alto. Il caso peggiore è comunque O(n), ma in media è messo meglio. A questo punto viene spontaneo chiedere quale sia, secondo te, questa complessità media.
NON SAPREI FARLO MA FORSE HO CAPITO!
Direi, ad occhio, la metà, quindi sui O(n/2)
Direi, ad occhio, la metà, quindi sui O(n/2)
No.. Non si tratta di un valore così facile da calcolare. Un valore da calcolare ad occhio. Anche ammettendo di percorrere sempre tutto il percorso dai due nodi alla radice, cosa non vera ma che ci semplifica un po' il calcolo, dovresti comunque calcolarti l'altezza media di un albero binario qualsiasi con \(n\) nodi. Questo valore è proporzionale a \( \sqrt{n}. \) Ma il problema originale è più complicato di così (anche se questo valore è comunque sufficiente per mostrare la superiorità di questo metodo rispetto a quello originale in termini di complessità temporale.
Apa il problema che trovo difficilissimo ora (dico prima di migliorare secondo quanto dici) è generare alberi binari casuali!!!
Voglio testare con tanti input... Anche per poi provare a migliorare la soluzione attuale.
Nodi non devono ripetersi mentre devo gestire le direzioni D, S, SS, SSD, DD, et etc
Oddio è da paura!!!! Che consigli?
Produre un milione di alberi che si chiudono, ciascuno, con ()
Ogni albero magari può, che ne so, arrivare a contenere mille nodi....
Voglio testare con tanti input... Anche per poi provare a migliorare la soluzione attuale.
Nodi non devono ripetersi mentre devo gestire le direzioni D, S, SS, SSD, DD, et etc
Oddio è da paura!!!! Che consigli?
Produre un milione di alberi che si chiudono, ciascuno, con ()
Ogni albero magari può, che ne so, arrivare a contenere mille nodi....
(9,) (4,D) (19,S) (10,SS) () (9,) (4,D) (19,S) (10,SD) etc () (9,) (4,D) (19,S) (10,DS) etc etc () (9,) (4,D) (19,S) (19,DD) etc etc etc ()
QUI MI SA CHE HO BISOGNO DI UNA GROSSA SPINTA APA 
Creare robe "CASUALI" del genere.. Ma tante
Con risultato:
Creare robe "CASUALI" del genere.. Ma tante
4 2 (3,D) (191,SS) (90,S) (2,DDS) (1272,) (4,SSD) (14,DD) () (,) () (11,SS) (7,SSS) (8,D) (5,) (4,S) (13,DS) (2,SSD) (1,DDD) (4,DD) () (3,S) (4,D) (2,) () (22,) (33,S) (44,SS) (2,D) (4,SD) () (22,) (44,S) (2,D) (4,SD) () (11,SS) (2,SSS) (8,D) (142,S) (4,SD) (390,) () (4,SDS) (22,SD) (2,SSS) (8,D) (6,S) (904,) (811,SS) () (11,SS) (7,SSS) (8,D) (5,) (4,S) (13,DS) (2,SSD) (1,DDD) (4,DD) () (2,S) (4,D) (420,) () (11,SS) (4,SSS) (8,D) (1085,) (42,S) (13,DS) (92,SSD) (1,DDDS) (14,DD) (2,DDD) () (5,) (4,S) (13,DS) (5,S) (6,D) () (2,) (4,S) () (3,) (2,D) (4,S) () (4,SS) (3,S) (2,) (6,D) () (2,S) (22,SD) (220,) (4,D) () (3,D) (191,SS) (90,S) (2,DDS) (122,) (4,SSD) (14,DD) ()
Con risultato:
1272 Albero non corretto 4 2 22 22 142 6 4 420 1085 Albero non corretto 2 3 2 220 122
Il consiglio te l'ho già dato qualche post fa. Ho in effetti praticamente descritto l'algoritmo.
Sono un frignone incapace!
Mi son messo e non riesco a stampare l'albero che voglio.
Genero i nodi a caso e poi vorrei avere l'albero completo ma non riesco con le variabili bool che dicono se è a sinistra o destra.
al livello 2^1 dovrei avere S=0 e D=1
al livello 2^2 quindi i rami 00, 01, 10, 11
al livello 2^3 avrò 000, 001, 010, 011, 100, 101, 110, 111 e così via.
Vedo un pattern che non riesco a programmare
In questo caso non voglio i rami casuali ma solo i nodi e poi strutturare l'albero completo. L'idea non mi sembra malaccio.
Mi son messo e non riesco a stampare l'albero che voglio.
Genero i nodi a caso e poi vorrei avere l'albero completo ma non riesco con le variabili bool che dicono se è a sinistra o destra.
al livello 2^1 dovrei avere S=0 e D=1
al livello 2^2 quindi i rami 00, 01, 10, 11
al livello 2^3 avrò 000, 001, 010, 011, 100, 101, 110, 111 e così via.
Vedo un pattern che non riesco a programmare
In questo caso non voglio i rami casuali ma solo i nodi e poi strutturare l'albero completo. L'idea non mi sembra malaccio.
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
int
main (void)
{
vector < int >v (15); //albero da 15 nodi
int r = rand () % 21 + 1;
ofstream out ("file.txt");
srand (time (NULL));
v[0] = r;
out << "(" << r << ",) "; //radice
bool ripeti = false;
for (int i = 0; i < 15; i++)
{
r = rand () % 21 + 1;
for (int c = 0; c < i; c++)
{
if (v[c] == r)
{
ripeti = true;
c = i;
}
}
if (ripeti == true)
i = i - 1;
else
{
v[i] = r;
}
ripeti = false;
}
string S = "S";
string D = "D";
int k = 1;
string s1 = "";
string d1 = "";
bool primo = true;
bool dividi = false;
for (int u = 0; u < 14; u++)
{
//qui devo stampare e dare sinistra o destra ai nodi ma mi incasino
}
out << "()" << endl;
return 0;
}
Vorrei fare questo:
http://www.researchgate.net/profile/Erk ... 000000.pdf
http://www.cs.otago.ac.nz/staffpriv/mik ... yTrees.pdf
Ma mi dovrò arrendere
http://www.researchgate.net/profile/Erk ... 000000.pdf
http://www.cs.otago.ac.nz/staffpriv/mik ... yTrees.pdf
Ma mi dovrò arrendere
Perché dovresti arrenderti? Io penso che tu ti stia in qualche modo complicando la vita. Ci sono tre problemi distinti nella generazione di un albero casuale:
1. Generazione della topologia dell'albero
2. Assegnazione casuale delle chiavi all'interno dell'albero
3. Scrittura del file nel formato desiderato
Ogni sottoproblema può essere risolto in totale autonomia rispetto agli altri e ti consiglio di affrontarli separatamente.
1. Generazione della topologia dell'albero
2. Assegnazione casuale delle chiavi all'interno dell'albero
3. Scrittura del file nel formato desiderato
Ogni sottoproblema può essere risolto in totale autonomia rispetto agli altri e ti consiglio di affrontarli separatamente.
Allora il problema non è più stampare l'albero e generarlo. Anche se non è banale (almeno per me)
Il problema che trovo è che voglio stamparlo con le direzioni di sinistra S e destra D.
Queste stringhe mi fanno uscire pazzo!
Se scegliessi di stamparlo così:
(10 ()( 1 ( 5 ()() ) ( 2 ( 3 ()() ) ( 8 ()() ) ) ) )
Avrei molti meno problemi
Il problema che trovo è che voglio stamparlo con le direzioni di sinistra S e destra D.
Queste stringhe mi fanno uscire pazzo!
Se scegliessi di stamparlo così:
(10 ()( 1 ( 5 ()() ) ( 2 ( 3 ()() ) ( 8 ()() ) ) ) )
Avrei molti meno problemi
E allora perché non lo stampi così? In ogni caso puoi sempre mantenere una stringa che tiene conto del percorso fatto per arrivare ad uno specifico nodo e stampare di volta in volta quella stringa.
"apatriarca":
E allora perché non lo stampi così? In ogni caso puoi sempre mantenere una stringa che tiene conto del percorso fatto per arrivare ad uno specifico nodo e stampare di volta in volta quella stringa.
Esatto!!! E' questo che non riesco!!!! Mi viene da picchiarmi sul capoccion!!!!! Poi faccio il frignone così --->
Apa Mio..
Ma è nella struct dell'albero (dove definisco i nodi) che mi consigli di tener traccia di una stringa che inizia come string "" e, man mano, poi si "allarga", ma in modo corretto, sommando le varie direzioni casuali ossia i cari caratteri "SDSSD" etc etc.
Supponendo di non andare a creare più di 100 nodi, per ciascun BT, la stringa dovrebbe essere fattibile. Lo so che è un po' da macellaio ma mi sono impuntato.... Il nodo radice sarà, ad esempio: (4,) quindi la stringa rimane "". Diciamo che, in questo esempio abbiamo due nodi figli: (4,) (10,S) (2,D) ()
In questo esempio la string del nodo 10 è cresciuta ""+"S"; la string del nodo 2 anche ""+"D"
Ma è nella struct dell'albero (dove definisco i nodi) che mi consigli di tener traccia di una stringa che inizia come string "" e, man mano, poi si "allarga", ma in modo corretto, sommando le varie direzioni casuali ossia i cari caratteri "SDSSD" etc etc.
Supponendo di non andare a creare più di 100 nodi, per ciascun BT, la stringa dovrebbe essere fattibile. Lo so che è un po' da macellaio ma mi sono impuntato.... Il nodo radice sarà, ad esempio: (4,) quindi la stringa rimane "". Diciamo che, in questo esempio abbiamo due nodi figli: (4,) (10,S) (2,D) ()
In questo esempio la string del nodo 10 è cresciuta ""+"S"; la string del nodo 2 anche ""+"D"
Immagino che per stampare l'albero tu segua un qualche tipo di visita dell'albero. Durante la visita dell'albero seguirai un qualche tipo di percorso. Ogni volta che scegli di visitare l'albero destro o sinistro dovresti aggiungere una lettera alla stringa. Ogni volta che torni da un nodo figlio a uno genitore dovresti invece eliminare tale lettera.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo