C/C++ - Un parere tecnico

Ciao a tutti,

avrei bisogno di un parere: ho realizzato un progetto che implementa la gestione di un albero rosso nero che, per specifiche di progetto, è sottoclasse di albero binario di ricerca.

Da un punto di vista teorico, un albero rosso nero ha a disposizione un nodo sentinella, indicato con NIL, per gestire più facilmente alcuni controlli nel corso degli algoritmi (per esempio, tutti i NULL dei metodi di un albero binario sono sostituiti con NIL). La radice ha come padre il nodo sentinella, e tutte le foglie sono rimpiazzate da un unico nodo NIL, collegato con tutti i nodi posti al livello immediatamente superiore.

Nel mio programma, per gestire la presenza del nodo sentinella, ho seguito questo ragionamento: era inutile riscrivere il codice dei metodi della superclasse, dovendo sfruttare l'ereditarietà. Il mio problema, però, nasceva dal fatto che i metodi dell'albero binario non tengono conto del nodo sentinella (si veda tutti i vari NULL al posto di NIL), né del tipo di ritorno. Ho pensato, quindi, di aggiungere alla classe albero rosso nero un metodo privato, converti_albero(), che "trasforma” temporaneamente un albero rosso nero in un albero binario e viceversa. La conversione viene effettuata subito prima e subito dopo l’invocazione di uno dei metodi della superclasse, nello specifico quello per l'inserimento di un nuovo nodo e quello per la ricerca di un nodo. Tutti i nodi dell’albero collegati con il nodo sentinella vengono momentaneamente “sganciati” settando i campi puntatore a NULL (o “agganciati” settando i campi puntatore a NIL, nel caso di un albero binario), trasformando l’albero rosso nero in un binario di ricerca (o in un rosso nero, nel caso contrario). A questo punto, viene invocato il metodo della superclasse che potrà funzionare senza problemi eseguendo le operazioni necessarie.

Questo è il codice del metodo per l'inserimento:

    /* Metodo della classe "albero_RB" per l'inserimento di un nodo. Utilizzeremo il metodo per l'inserimento della classe padre
    evitando, così, di doverlo riscrivere. Il problema è che tale metodo è basato sui puntatori a NULL dei nodi foglia, assenti
    in un albero red-black grazie al nodo sentinella. A questo proposito, invocheremo un secondo metodo, "converti_albero", atto
    a "trasformare" temporaneamente un albero red-black in un albero binario di ricerca e viceversa. */
    void albero_RB::inserisci_nodo(string chiave)
    {
       nodo_RB* nodo_nuovo;
       nodo_nuovo = new nodo_RB(); // allocazione dinamica del nuovo nodo RB da inserire nell'albero

       if (radice->get_chiave()!="NIL") // se nell'albero c'è almeno un nodo...
          RB_a_BST = true; // ...andrà convertito da red-black in binario di ricerca

       /* se l'albero è vuoto, basta soltanto far puntare il puntatore alla radice a NULL. In presenza di almeno un nodo, invece
       questo va "sganciato" dal nodo sentinella per trasformare l'albero red-black in binario di ricerca. L'operazione va ripetuta
       per tutti i nodi dell'albero connessi col nodo sentinella. */

       if (RB_a_BST == true)
       {
          converti_albero (get_radice(), RB_a_BST);
          radice->set_padre(NULL); // stacco la radice dal nodo sentinella
       }
       else // l'albero è vuoto, la radice deve puntare a NULL
       {
          radice = NULL;
       }
       
       // invocazione del metodo della classe padre per l'inserimento
       albero_BST::inserisci_nodo(static_cast <nodo_BST*> (nodo_nuovo), chiave);

       /* Inserito il nuovo nodo, dobbiamo ritrasformare l'albero binario di ricerca in un red-black. Bisogna riagganciare tutti
       i nodi esaminati in precedenza con il nodo sentinella. */
       
       RB_a_BST = false; // l'albero binario di ricerca deve essere riconvertito in red-black
       converti_albero (get_radice(), RB_a_BST);
       radice->set_padre(NIL);

       bilancia_albero(nodo_nuovo); // invocazione del metodo per bilanciare l'albero red-black
    }

La sua complessità di tempo è pari a O(logn).

Questo è il codice del metodo per la conversione:

    void albero_RB::converti_albero(nodo_RB* nodo, bool RB_a_BST)
    {
       if (RB_a_BST == false) // converti da BST a RB
       {
          if (nodo!=NULL)
          {
             if (nodo->get_sx() == NULL) // controllo il figlio sinistro
             {
                nodo->set_sx(NIL); // se non c'è, collego quel lato del nodo al nodo sentinella
             }
             else // c'è il figlio
             {
                converti_albero (nodo->get_sx(), RB_a_BST); // scendo a sinistra
             }
             
             if (nodo->get_dx() == NULL)
             {
                nodo->set_dx(NIL);
             }

             else // c'è il figlio
             {
                converti_albero (nodo->get_dx(), RB_a_BST); // scendo a destra
             }
          }
       }
       
       else if (RB_a_BST == true) // converti da RB a BST
       {
          if (nodo!=NIL)
          {
             if (nodo->get_sx() == NIL) // controllo il figlio sinistro
             {
                nodo->set_sx(NULL); // se è il nodo sentinella, sgancio quel lato del nodo   
             }
             else // c'è il figlio
             {
                converti_albero (nodo->get_sx(), RB_a_BST); // scendo a sinistra
             }
             
             if (nodo->get_dx() == NIL)
             {
                nodo->set_dx(NULL);
             }

             else // c'è il figlio
             {
                converti_albero (nodo->get_dx(), RB_a_BST); // scendo a destra
             }
          }
       }
    }

La sua complessità dovrebbe essere pari a theta(n), in quanto andranno visitati tutti i nodi dell'albero.

In totale, quindi, la complessità dovrebbe essere pari a:

theta(n) (conversione red-black->binario) + O(logn) (inserimento) + theta(n) (conversione binario->red-black)

Purtroppo, la complessità è un po' "pesantuccia", so che l'approccio non è dei migliori: un'altra soluzione, per esempio, sarebbe potuta essere quella di inserire il nodo NIL come attributo della classe padre. Diciamo che io ho preferito seguire la strada della "correttezza teorica": un albero binario NON ha un nodo sentinella per definizione.

Vorrei sapere che ne pensate di questa cosa ed, eventualmente, come si potrebbe migliorare.

Grazie in anticipo per le risposte.

Ho risolto con il supporto di un amico: si possono utilizzare dei metodi virtuali nelle due classi che restituiscono NULL o NIL in base alle necessità ed effettuare tutti i controlli nei metodi invocandoli (cioè, invece di "if nodo == NULL", scrivere "if isNull(nodo)".

Potete chiudere.