[C++] Esercizio su Albero

[starsuper]

Sono alle prese con un esercizio sugli alberi, non binari. Qui in questo caso si implementa un generico albero e non un albero binario e si usa un vettore per rappresentare i figli o children. Vorrei una mano per comprendere meglio alcune funzioni e alcuni passaggi. Ecco il codice:

#include <stddef.h>
#include <vector>

typedef int T;
class tree; 

class node {
    T info;
    std::vector<node*> children;
    friend class tree;
public:
    typedef std::vector<node*>::iterator iterator;
    iterator begin() {
        return children.begin();
    }
    iterator end() {
        return children.end();
    }
    T get() {
        return info;
    }
};

class tree {
    node* r;
    void del(node* v) {
        if (v == NULL) return;
        for (node::iterator it = v->begin(); it != v->end(); ++it)    
            del(*it);
        delete v;
    }
public:
    tree() : r(NULL) { }
    node* add(T info, node* parent) {
        node* v = new node;
        v->info = info;
        if (parent != NULL) parent->children.push_back(v);
        else {
            if (r != NULL) del(r);
            r = v;
        }
        return v;
    }
    node* add(T info) {
        return add(info, NULL);
    }
    node* root() { return r; }
    void remove(node* v) {
        if (r == v) r = NULL;
        else { /* remove v from the list of children of its parent */ }
        del(v);
    }
};

Ecco il main

#include "tree.hpp"
#include <iostream>

static void preorder(node* r) {
    if (r == NULL) return;
    std::cout << r->get() << std::endl;
    for (node::iterator it = r->begin(); it != r->end(); ++it)    
        preorder(*it);
}

static void print(tree& t) {
    std::cout << "tree: " << std::endl;
    preorder(t.root());
}

int main() {
    tree t;
    node* n  = t.add(10);    // add root
    node* v1 = t.add(20,n);  // add child of root
    node* v2 = t.add(30,n);  // add child of root
    node* v3 = t.add(15,n);  // add child of root
    node* v4 = t.add(25,v2); // add child of v2
    print(t);
    t.remove(v2);
    print(t);
    return 0;
}

Ogni nodo è composto da info(valore del nodo) ed un vettore di puntatori ai nodi figli. La classe nasce con una root di tipo *node. Vorrei chiedervi, la funzione

void del(node* v) {
        if (v == NULL) return;
        for (node::iterator it = v->begin(); it != v->end(); ++it)    
            del(*it);
        delete v;
    }

1)Innanzitutto è private, quindi non può essere richiamata nel main, ma viene invocata tramite remove. Si passa un nodo da eliminare v, e automaticamente si cancellano tutti i nodi del vettore children di v, giusto? Ma il campo INFO del nodo v, rimane? perche uso delete v, se non ho istnanziato nessun puntatore con la new?

2)Se volessi modificare le remove, cancellando il nodo v dalla lista dei suoi parenti. Come posso fare? Io ho pensato di fare cosi. Modifico la add per fare in modo che tutti i nuovi nodi abbiano il puntatore a parent.

  node* add(T info, node* parent) {
        node* v = new node;
        v->info = info;
        if (parent != NULL) {
             parent->children.push_back(v);
             v->parent=parent; }
        else {
             if (r != NULL) del(r);
             r = v;
             r->parent=null;
              }
        return v;
    }

E la funzione remove la modificherei con:

 void remove(node* v) {
        if (r == v) r = NULL;
        else { 
         v->parent->children.pop_back(v);  //tramite puntatore accedo al valore precedente e tolgo v dal vettore dei children  del suo parent!
         }
        del(v);
    }

Quindi elimino v dal vettore del parent e poi chiamando del(v) elimino tutti i figli del nodo v.

La mia soluzione vi sembra sensata? Grazie e scusate per la lunghezza!

[apatriarca]

La particolare implementazione scelta non è particolarmente bella o efficiente. Sono senza dubbio possibili molte alternative. E' per esempio discutibile la scelta di non usare template (ma suppongo sia perché non ve li ha insegnati). Non è poi chiara la strategia usata per decidere come assegnare le funzioni. Mi sembrerebbe infatti più sensato se le funzioni relative ai singoli nodi (come aggiungere un figlio) fossero definite nel nodo e non in una classe separata tree (che necessità di diventare friend proprio per questa ragione).

Quando si programma è spesso opportuno definire un qualche tipo di gerarchia. E' cioè importante/utile che esista un ben definito "possessore" di una qualche variabile. Nel caso di un albero sono i padri che normalmente gestiscono i figli. Avere quindi una funzione del figlio che va a modificare il padre è una cattiva idea in quanto va ad invertire questa dipendenza. Non è tuttavia sbagliato fare come hai scritto (a patto di aggiungere un test per verificare che ci sia effettivamente un padre..).

I nodi vengono creati con new all'interno di add.. Quindi in del utilizzi delete per cancellarli. Quando chiami delete, chiami automaticamente il distruttore della classe che a sua volta chiamerà quello di info. Oltretutto info è semplicemente di tipo int..

[starsuper]

Grazie come sempre. Purtroppo hai ragione questa implementazione (ne ho trovate tante altre online spiegate davvero bene) è complessa da afferrare e troppo intrecciata ma probabilmente essendo un appello di esame è fatto apposta per metterci in difficoltà.
Se ho capito bene info è un int, perche rappresenta il key-value del nodo. Si il distruttore dellla classe node l'ho creato io tramite:

 ~tree()
    {
        cout<<"cancello albero"<<endl;
        for (node::iterator it = r->begin(); it != r->end(); ++it)
        {
            *it=NULL;
        }
        del(root());
        cout<<"albero cancellato"<<endl;
    }

I cout servono per vedere se tutte le operazioni sono andate a buon fine e per avere riscontro.

Purtroppo l'idea di cancellare un figlio dal padre è chiesta probabilmente per solo scopo didattico, visto che non risulta cosi immediato. Tant'è che l'implementazione espressa sopra mi genera errore perche

void remove(node* v) {
        if (r == v) r = NULL;
        else { 
         v->parent->children.pop_back(v);  //tramite puntatore accedo al valore precedente e tolgo v dal vettore dei children  del suo parent!
         }
        del(v);
    }

il metodo pop_back() della classe vector non vuole argomenti visto che cancella automaticamente l'ultimo elemento inserito. Non saprei quindi come fare per far eliminare il nodo passato v al vettore dei padri !
Se volessi usare un iteratore per leggere tutti i valori del vettore, potrei usare?

for(node::iterator it= v->parent->begin(); it!=v->parent->end(); ++it)
            
                if (*it==v)
                   *it=NULL;

Non ho ben chiaro su quali valori deve scorrere l'iteratore però....

[apatriarca]

Per cancellare un elemento da un array esiste la funzione erase. Tuttavia richiede un iteratore all'elemento e non il suo valore. Puoi fare qualcosa come

v->parent->children.erase(std::find(v->parent->children.begin(), v->parent->children.end(), v));

dove std::find si trova in algorithm. Il principale problema è che erase rende invalidi tutti gli iteratori al vettore sul quale viene chiamato. Questo significa in particolare che se venisse chiamata la funzione all'interno di un ciclo dal padre avresti seri problemi. Ma se non viene usata in questo modo allora non c'è problema.

Il distruttore che hai scritto non è corretto. Stai settando tutti i valori a NULL perdendo quindi il riferimento ai nodi figli (che invece andrebbero distrutti a loro volta). Il metodo corretto sarebbe quello di chiamare delete sui figli..

[starsuper]

for (node::iterator it = r->begin(); it != r->end(); ++it)

Ma questo iteratore non dovrebbe restituire children.begin() del nodo r? A questo modo cancello tutti i figli della root r, e poi invoco la del su root, in modo da cancellare la root. E se facessi cosi?

for (node::iterator it=children.begin(); it!=children.end();++it)
      del(*it);

[apatriarca]

Il ciclo è scritto nel modo corretto. Itera su tutti i nodi figli. Ma il corpo del ciclo non è corretto. Stai infatti semplicemente perdendo il puntatore al nodo, non lo stai distruggendo. del potrebbe anche andare bene, ma alla fine del e il distruttore fanno la stessa cosa.. Tanto vale chiamare: delete *it.

[starsuper]

La mia idea era richiamare la del su ogni elemento del vettore children. Ovvero scorrendo con il for il vettore children, ogni suo elemento è un nodo che avrà a sua volta un vettore children. Visto che la del prende in ingresso un oggetto nodo e visto che ogni elemento del vettore children è un nodo ogni ciclo for richiama la del su ogni nodo la quale a sua volta cancella tutti i figli. In testa la vedo cosi io, il problema è codificarla

for (node::iterator it=children.begin(); it!=children.end();++it)
      del(*it);
      delete(*it); 

E se usassi delete per deallocare la memoria riservata ad ogni nodo?

[apatriarca]

Non è corretto definire il distruttore della classe nodo usando del che è definita nell'albero..

[starsuper]

Attenzione però l'esercizio richiede di "Add a destructor function that deletes all the nodes of the tree", qui il distruttore è dell'albero non del singolo nodo...

[apatriarca]

Se è stato definito correttamente un distruttore sul nodo sarebbe sufficiente chiamare delete sulla radice (la variabile r).

[vict85]

Nota inoltre che erase di std::vector chiama il distruttore di ogni nodo, quindi una volta che implementi il distruttore del nodo nel modo corretto la standard library si occupa di metà del tuo lavoro. Nota inoltre che anche se l'albero ha il compito di distruggere "l'albero" (insomma l'insieme dei nodi) ma di fatto è sufficiente che usi delete su r e far fare tutto ai distruttori dei nodi. Questa implementazione rispetta la domanda ed è il modo migliore di implementare una cosa del genere.

P.S.: Come mai le domande dell'esame è in inglese?

[apatriarca]

Si tratta di un vector di puntatori a nodo, per cui nessun costruttore viene chiamato.

[starsuper]

Grazie a tutti, purtroppo questo esercizio continua a darmi rogne e problemi.
Sono ripartito da capo cercando di analizzarlo ancora una volta, partendo innnanzitutto dal distruttore del tree.
Sappiamo che il main richiama il distruttore della classe tree alla fine delle operazioni, quindi chiamerà il distruttore di default passando un oggetto di tipo tree all'incirca.

Se io dichiaro un

for(node::iterator it= children.begin(); it!= children.end(); ++it)

significa che automaticamente vado a prendere tutti i nodi, ma comprende anche la root?
Che cambierebbe se facessi

for(node::iterator it= r->children.begin(); it!= r->children.end(); ++it)

?
Questo secondo for itera solo sui figli della root?

Se cosi fosse potrei usare fare una cosa tipo:

 ~tree()
    {
        cout<<"entro nel distruttore"<<endl;
        for(node::iterator it=r->children.begin(); it!=r->children.end(); ++it){
            (*it)->info=NULL;
            node* tmp= new node;
            tmp=(*it);
            delete tmp;   
        }
        cout<<"albero cancellato"<<endl;
        cout<<"cancello la root"<<endl;
        r->info=NULL;
        delete r; //Dealloco la memoria riservata ad r
        cout<<"Root cancellata"<<endl;
       }

Cosi il programma gira, ma è corretto secondo voi?

P.S. il testo è in inglese perche il corso di laurea è in lingua inglese