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

[Giova411]

Testo nascosto, fai click qui per vederlo

Son mancato qualche giorno e devo ancora chiudere qualche Topic passato dove sono stato aiutato molto da Apa e Vic.

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ì:

Codice:

    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.

[apatriarca]

Esistono diversi modi di implementare un albero. Un albero può essere rappresentato usando classi per i nodi e puntatori ai figli, ma anche essere semplicemente un array in cui la struttura ad albero sia implicita. Si possono avere alberi con implementazioni semplicissime e alberi la cui implementazione è incredibilmente complicata.

Nel tuo caso hai un numero di nodi fissato, per cui ha senso allocare tutti i nodi insieme in un array. Ogni nodo è identificato univocamente dalla sua posizione nell'array. In generale: se puoi usare un array per qualcosa di questo tipo allora fallo. Ci sono infatti diverse ragioni per cui farlo è conveniente. E' ad esempio probabilmente più efficiente ed è più facile fare il debug perché puoi visualizzare l'intero albero molto più facilmente. A questo punto puoi decidere se allocare un nodo in più oppure sottrarre uno agli identificativi del nodo. Credo sia in generale più semplice allocare un nodo in più (anche perché è molto piccolo).

A questo punto non rimane che pensare a come descrivere la relazione padre/figlio. Se gli alberi possono essere solo binari, allora potresti pensare di avere un nodo tipo il seguente:

Codice:

struct Node {
    unsigned parent; // opzionale..
    unsigned left, right;
};


Il valore zero è usato per indicare un valore vuoto, un numero diverso da zero rappresenta un nodo all'interno dell'albero. Un'altra regola abbastanza utile è quella di avere come valore di default quello corrispondente a tutti i byte uguali a zero. E' infatti in generale più semplice e veloce inizializzare a zero rispetto ad altri valori. E' un consiglio particolarmente valido in C, ma usando spesso tipi POD è valido anche in C++.

A questo punto direi che hai tutti gli ingredienti per fare quello che ti sei prefissato:
1. Leggi il primo valore e allochi l'array di nodi.
2. Leggi ogni riga successivi e setti il valore di left o right (a seconda di quale sia ancora non inizializzato) del nodo corrispondente.

Una volta riuscito a fare questo ti propongo un paio di possibili passaggi ulteriori:
1. Sapresti modificare la struttura in modo da avere un albero con nodi aventi un numero di figli arbitrario?
2. Sapresti scrivere un algoritmo che, dato in ingresso un numero di nodi, generi un albero casuale?

[Giova411]

Una volta riuscito a fare questo ti propongo un paio di possibili passaggi ulteriori:
1. Sapresti modificare la struttura in modo da avere un albero con nodi aventi un numero di figli arbitrario?
2. Sapresti scrivere un algoritmo che, dato in ingresso un numero di nodi, generi un albero casuale?

Apa fermooo che poi ti si ritorce contro

VEDO CHE HAI CAPITO AL VOLO!!!
Avevo pensato a qualcosa del genere ma ho il problema di definire i figli!!!

Codice:

struct nodo{
  vector<int> figli;
  int peso;
};
int N;
vector<nodo> albero;
vector<int>  S;

int get(int node){
  if(S[node]==-1){
    S[node]=albero[node].peso;
    for(int f:albero[node].figli)
      // fai qualcosa
  }
  return // qualcosa;
}
int main(void) {
  ifstream in("in.txt");
  ofstream out("out.txt");
  in>>N;
  albero.resize(N);
  S.resize(N,-1);
   for(int i=0;i<N;i++)
    in>>albero[i].peso; // come fo SX e DX?!
  for(int i=0;i<N-1;i++){
    int p,f;
    in>>p>>f;
    albero[p].figli.push_back(f); // e qui devo capire come fare
  }
  // fai qualcosa
  return 0;
}


AIUTOOOOO

Testo nascosto, fai click qui per vederlo

Poi hai beccato una cosa che vorrei ri-imparare a fare!

E' ad esempio probabilmente più efficiente ed è più facile fare il debug perché puoi visualizzare l'intero albero molto più facilmente.

Cavolo mi ammazzo di cout per simulare cosa succede ma non ricordo come fare un debug fatto bene!!! Ricordo tutte le puntate di Tata Francesca di 20 anni fa non ridere!!!!

Ma devo riuscire a leggere da file e lavorare con queste specifiche struct:

Codice:

// Albero binario
struct nodo
{
    int chiave;
    struct nodo *left, *right;
};
 
nodo * newNodo(int k)
{
    nodo *temp = new nodo;
    temp->chiave = k;
    temp->left = temp->right = NULL;
    return temp;
}



[apatriarca]

Perché stai usando un vector se vuoi un albero binario? Il metodo più semplice per gestire i figli è quello di scegliere che il primo figlio che compare sia sempre quello di sinistra. Il secondo quello di destra. Se vuoi maggiore controllo potresti sempre decidere che se inserisci il valore 0 nel file corrisponde ad un figlio nullo..

Usare quella funzione significa complicarti la vita. Ci sono infatti due alternative: avere un array di appoggio che contiene puntatori ai nodi corrispondenti oppure cercare ogni volta la chiave all'interno dell'albero. La seconda alternativa è la più complicata perché durante la costruzione potresti avere più alberi che devi poi unire.. La soluzione più semplice è invece quella di allocare tutti i nodi all'inizio usando quella funzione e inserire i loro indirizzi in un array che poi userai per andarli a recuperare. Si tratta però di una complicazione rispetto alla più semplice soluzione di lavorare direttamente con chiavi e indici. Nota che puoi invece lavorare tranquillamente con quella struttura per il nodo. Non ha importanza se usi gli indici o i puntatori per accedere a i nodi figli. L'unico reale vantaggio dell'uso di indici è quello di essere più facilmente scrivibile e leggibile da file (puoi infatti leggere e scrivere la struttura direttamente da file senza alcun problema di correzione dei puntatori).

Testo nascosto, fai click qui per vederlo

Un'alternativa ad avere un vector per contenere i figli è quello di usare una lista concatenata per i figli. Quindi qualcosa come segue:

Codice:

struct Node {
    unsigned next_sibling;
    unsigned first_child, last_child;
};


Volendo last_child è opzionale e puoi anche solo usare next_sibling e first_child.. In quel caso i figli verranno aggiunti da destra verso sinistra (dall'ultimo al primo..). Ovviamente puoi anche aggiungere un collegamento al padre e la chiave.

[Giova411]

Apa ho un caos in capoccia!!!

Il metodo più semplice per gestire i figli è quello di scegliere che il primo figlio che compare sia sempre quello di sinistra. Il secondo quello di destra

OK andrebbe bene mettere questo vincolo.

Però poi vorrei usare semplici puntatori:

Codice:

Node * root = newNode(1);
  root->left = newNode(2);
 //etc etc


Ed avere una struttura che si formi da sola da un semplice file come nell'esempio del primo mio post.
Se ho codice che si esprime così "root->right->right" è il massimo!
Solo che il problema è proprio caricarlo da file... E' fattibile per aberi con 300000 mila nodi da caricare da file? Come la formo/carico la struttura? Non è banale da capire
Sopra ho scritto quello che avevo pensato ieri... Ma sono fuori strada difatti....

[Giova411]

Se avessi un Albero Binario di Ricerca forse avrei meno difficoltà
In questo caso si regola da solo dove mettere tra DX e SX. Mi allontano da quello che volevo nel primo post.
Ossia leggendo da file:
---------------------------------------
7
7 3 4 6 5 1 2
---------------------------------------

Non avrei lo stesso albero.. A parte che non so se è manco giusto scrivere così:

Codice:

struct nodo {
 int valore;
 nodo *left_nodo;
 nodo *right_nodo;
};
 
void insert_nodo(nodo *tree, nodo *new_nodo){

 if (new_nodo->valore > tree->valore){
   if (tree->right_nodo == NULL) tree->right_nodo = new_nodo;
    else insert_nodo(tree->right_nodo, new_nodo);
   }
 else {
   if (tree->left_nodo == NULL) tree->left_nodo = new_nodo;
    else insert_nodo(tree->left_nodo, new_nodo);
 }
}
int main(void){
  ifstream in("in.txt");
  ofstream out("out.txt");

 int c, i, val;
 
 cin >> c;
 cin >> val;
 
 nodo *tree = (nodo *)malloc(sizeof(nodo));;
 tree->valore = val;
 tree->left_nodo = NULL;
 tree->right_nodo = NULL;
 
 for (i = 0; i < c - 1; i++){
 cin >> val;
 
 nodo *new_nodo = (nodo *)malloc(sizeof(nodo));
 new_nodo->valore = val;
 new_nodo->left_nodo = NULL;
 new_nodo->right_nodo = NULL;
 
 insert_nodo(tree, new_nodo);
  }
 
// altro da fare
 
 return 0;
}


Apa mettiti una mano sul cuore

Testo nascosto, fai click qui per vederlo

sono vietatissimi Python, Haskell, C, Java etc etc

[apatriarca]

Nel mio codice ho usato gli indici semplicemente perché sono più facili da leggere e comprendere. In un certo senso c'è un maggiore parallelismo con quello che c'è scritto nel file. È tuttavia abbastanza ininfluente il loro utilizzo. Usando puntatori avrai un codice del tutto equivalente.

Il problema più grosso sta nella funzione newNode. Questa funziona alloca dinamicamente e in modo indipendente tutti i nodi, ma questo significa che non hai un modo automatico e veloce per trovare un particolare nodo come nel caso di un semplice array di nodi.

All'interno del file hai però una relazione tra nodi in base alle loro chiavi. Hai quindi bisogno di un metodo veloce per accedere al nodo con una particolare chiave, senza dover cercare la chiave in una struttura complessa come potrebbe essere la foresta (un insieme di alberi) che hai all'inizio. La soluzione più semplice è quindi quella di allocare subito tutti i nodi memorizzando il loro indirizzo in un array. Ogni volta che cerchi una chiave andrai quindi a cercarla in questo array, invece che nella foresta. Ha però l'aria di una inutile forzatura.

Codice:

std::vector<Node *> nodes;

// lettura dimensione N..

nodes.resize(N+1);

for (int i = 1; i <= N; ++i) {
    nodes[i] = newNodo(i);
}

// per settare relazione padre P - figlio F
if (nodes[P]->left) {
    if (nodes[P]->right) { /* .. errore .. */ }
    else { nodes[P]->right = nodes[F]; }
} else {
    nodes[P]->left = nodes[F];
}


Ma non vedo comunque il motivo di allocare a questo punto tutto dinamicamente. Si poteva anche fare qualcosa come segue:

Codice:

std::vector<Node> nodes;

// lettura dimensione N..

nodes.resize(N+1);

for (int i = 1; i <= N; ++i) {
    nodes[i].chiave = i;
}

// per settare relazione padre P - figlio F
if (nodes[P].left) {
    if (nodes[P].right) { /* .. errore .. */ }
    else { nodes[P].right = &nodes[F]; }
} else {
    nodes[P].left = &nodes[F];
}


Questa seconda versione è potenzialmente più veloce. Rimane comunque ancora un problema da risolvere: qual'è la radice del tuo albero? Come fai a stabilire se quello che hai ottenuto è effettivamente un albero e non un grafo generico? Come fai a dire se l'albero è connesso invece di essere un insieme disgiunto di alberi?

[Giova411]

Rimanendo sul tipo di esercizi che vorrei fare io
Come esempio perfetto (ma leggendo però da file i vari alberi):
http://www.geeksforgeeks.org/lowest-com ... ree-set-1/
Per ora non mi preoccupo di esser veloce ma di avere una struttura di puntatori corretta.
Possiamo fare che il primo nodo indicato sia la radice e supporre che non siano ammesse foreste?
Quindi albero binario tutto connesso in input. Primo intero sarà il numero di nodi totali.
Poi il primo nodo è la root?
Il problema rimane nel costruirlo bene. Forse mi stai facendo avvicinare alla soluzione, devo pensarci bene.

L'esempio del link dici che è un po' forzato nell'utilizzare puntatori?
Come lo cambieresti poi? Per trovare il LCA con array semplici mi tiro la zappa nei cosidetti

[apatriarca]

Nel suo caso può avere senso.. Nel tuo, considerando come è definito il file di testo, un po' meno. Il problema del formato da te scelto è che devi accedere in modo causale ai diversi nodi. Se avessi un formato diverso, come il seguente, non ci sarebbero problemi a fare esattamente come scrive il testo:

Codice:

7
1 (2 4 5) (3 6 7)


[Giova411]

Non servono altre parentesi interne a quelle messe? Capito il consiglio e spero di metterlo in pratica.
Il file che "immaginavo" potrebbe essere messo in pratica con
Alberi Binari di Ricerca o, ancor più semplice, con Alberi qualsiasi (senza limitazioni su figli). Giusto Maestro?