[c++]Dubbio su costruzione dinamica di Alberi in>> da file di testo

[Giova411]

Codice:

#include <fstream>
#include <sstream>
#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;
struct nodo
{
  int value;
  string percors;
  nodo *left;
  nodo *right;
};
bool verificatree (vector < nodo > &inp)
{
  nodo *root = NULL, *cur = NULL, *prev = NULL;
  for (vector < nodo >::iterator it = inp.begin (); it != inp.end (); it++)
    {
      nodo n = *it;
      if (n.percors.size () == 0)
   {
     if (root != NULL)
       {
         return false;
       }
     else
       {
         root = &(*it);
       }
   }
      else
   {
     cur = root;
     for (string::iterator pit = n.percors.begin ();  pit != n.percors.end (); pit++)
       {
         if (cur == NULL)
      return false;
         prev = cur;
         if (*pit == 'S')
      cur = cur->left;
         else if (*pit == 'D')
      cur = cur->right;
       }

     if (cur != NULL)
       return false;
     if (n.percors[n.percors.size () - 1] == 'S')
       prev->left = &(*it);
     else if (n.percors[n.percors.size () - 1] == 'D')
       prev->right = &(*it);
   }
    }
  return true;
}
bool findpercors(nodo *root, vector<int> &percors, int k)
{   
    if (root == NULL) return false;
    percors.push_back(root->value);
    if (root->value == k)
        return true;
    if ( (root->left && findpercors(root->left, percors, k)) ||
         (root->right && findpercors(root->right, percors, k)) )
        return true;
    percors.pop_back();
    return false;
}
int findLCA(nodo *root, int n1, int n2)
{   
    vector<int> percors1, percors2;
    if ( !findpercors(root, percors1, n1) || !findpercors(root, percors2, n2))
          return -1;
    int i;
    for (i = 0; i < percors1.size() && i < percors2.size() ; i++)
        if (percors1[i] != percors2[i])
            break;
    return percors1[i-1];
}
int main (void)
{
 ifstream in("in.txt");
 ofstream out("out.txt");
 int pr1, pr2;
 in >> pr1>>pr2;
  char nodo_data[1000];
  char temp[100];
  vector < nodo > inp;
  while (in >> nodo_data)
    {
      if (nodo_data[0] == '(' && nodo_data[1] == ')')
   {
     if (verificatree (inp))
       {
         vector < nodo >::iterator it = inp.begin ();
              out  << findLCA( &(*(inp.begin ())) , pr1, pr2);
       }
     else
            out << "Albero non valido";
     out << endl;
     inp.clear ();
     continue;
   }
      nodo n;
      sscanf (nodo_data, "(%d,%s)", &n.value, temp);
      temp[strlen (temp) - 1] = '\0';
      n.percors = temp;
      n.left = n.right = NULL;
      vector < nodo >::iterator it;
      for (it = inp.begin (); inp.size () > 0 && it != inp.end (); it++)
   {
     if ((*it).percors.length () > n.percors.length ()  || ((*it).percors.length () == n.percors.length () && (*it).percors > n.percors))
       {
         inp.insert (it, n);
         break;
       }
   }
      if (inp.size () == 0 || it == inp.end ())
   inp.push_back (n);   
    }
  return 0;
}


Codice:

3 4
(2,S) (4,SS) (6,DS) (7,DD) (3,D) (5,SD) (1,) ()
(1,S) (4,SS) (6,DS) (7,DD) (3,D) (5,SD) (2,) ()
(3,L) (4,R) ()
(2,S) (4,SS) (6,DS) (7,DD) (3,D) (5,SD) (1,) ()
(2,S) (4,SS) (6,DS) (3,D) (1,) ()


Codice:

1
2
Albero non valido
1
1


[apatriarca]

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?

[Giova411]

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

[apatriarca]

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?

[Giova411]

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!) SE NO CORREGGIMI MIO MENTORE!!!!!!!!!!!

[apatriarca]

È 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.

[Giova411]

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?

[apatriarca]

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.

[Giova411]

NON SAPREI FARLO MA FORSE HO CAPITO!
Direi, ad occhio, la metà, quindi sui O(n/2)

[apatriarca]

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.