Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Un parere tecnico
Forum - C/C++ - Un parere tecnico

Avatar
MagoAntò (Normal User)
Rookie


Messaggi: 42
Iscritto: 07/02/2009

Segnala al moderatore
Postato alle 12:02
Martedì, 22/05/2012
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:

Codice sorgente - presumibilmente C#

  1. /* Metodo della classe "albero_RB" per l'inserimento di un nodo. Utilizzeremo il metodo per l'inserimento della classe padre
  2.     evitando, così, di doverlo riscrivere. Il problema è che tale metodo è basato sui puntatori a NULL dei nodi foglia, assenti
  3.     in un albero red-black grazie al nodo sentinella. A questo proposito, invocheremo un secondo metodo, "converti_albero", atto
  4.     a "trasformare" temporaneamente un albero red-black in un albero binario di ricerca e viceversa. */
  5.     void albero_RB::inserisci_nodo(string chiave)
  6.     {
  7.        nodo_RB* nodo_nuovo;
  8.        nodo_nuovo = new nodo_RB(); // allocazione dinamica del nuovo nodo RB da inserire nell'albero
  9.  
  10.        if (radice->get_chiave()!="NIL") // se nell'albero c'è almeno un nodo...
  11.           RB_a_BST = true; // ...andrà convertito da red-black in binario di ricerca
  12.  
  13.        /* se l'albero è vuoto, basta soltanto far puntare il puntatore alla radice a NULL. In presenza di almeno un nodo, invece
  14.        questo va "sganciato" dal nodo sentinella per trasformare l'albero red-black in binario di ricerca. L'operazione va ripetuta
  15.        per tutti i nodi dell'albero connessi col nodo sentinella. */
  16.  
  17.        if (RB_a_BST == true)
  18.        {
  19.           converti_albero (get_radice(), RB_a_BST);
  20.           radice->set_padre(NULL); // stacco la radice dal nodo sentinella
  21.        }
  22.        else // l'albero è vuoto, la radice deve puntare a NULL
  23.        {
  24.           radice = NULL;
  25.        }
  26.        
  27.        // invocazione del metodo della classe padre per l'inserimento
  28.        albero_BST::inserisci_nodo(static_cast <nodo_BST*> (nodo_nuovo), chiave);
  29.  
  30.        /* Inserito il nuovo nodo, dobbiamo ritrasformare l'albero binario di ricerca in un red-black. Bisogna riagganciare tutti
  31.        i nodi esaminati in precedenza con il nodo sentinella. */
  32.        
  33.        RB_a_BST = false; // l'albero binario di ricerca deve essere riconvertito in red-black
  34.        converti_albero (get_radice(), RB_a_BST);
  35.        radice->set_padre(NIL);
  36.  
  37.        bilancia_albero(nodo_nuovo); // invocazione del metodo per bilanciare l'albero red-black
  38.     }


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

Questo è il codice del metodo per la conversione:

Codice sorgente - presumibilmente C++

  1. void albero_RB::converti_albero(nodo_RB* nodo, bool RB_a_BST)
  2.     {
  3.        if (RB_a_BST == false) // converti da BST a RB
  4.        {
  5.           if (nodo!=NULL)
  6.           {
  7.              if (nodo->get_sx() == NULL) // controllo il figlio sinistro
  8.              {
  9.                 nodo->set_sx(NIL); // se non c'è, collego quel lato del nodo al nodo sentinella
  10.              }
  11.              else // c'è il figlio
  12.              {
  13.                 converti_albero (nodo->get_sx(), RB_a_BST); // scendo a sinistra
  14.              }
  15.              
  16.              if (nodo->get_dx() == NULL)
  17.              {
  18.                 nodo->set_dx(NIL);
  19.              }
  20.  
  21.              else // c'è il figlio
  22.              {
  23.                 converti_albero (nodo->get_dx(), RB_a_BST); // scendo a destra
  24.              }
  25.           }
  26.        }
  27.        
  28.        else if (RB_a_BST == true) // converti da RB a BST
  29.        {
  30.           if (nodo!=NIL)
  31.           {
  32.              if (nodo->get_sx() == NIL) // controllo il figlio sinistro
  33.              {
  34.                 nodo->set_sx(NULL); // se è il nodo sentinella, sgancio quel lato del nodo  
  35.              }
  36.              else // c'è il figlio
  37.              {
  38.                 converti_albero (nodo->get_sx(), RB_a_BST); // scendo a sinistra
  39.              }
  40.              
  41.              if (nodo->get_dx() == NIL)
  42.              {
  43.                 nodo->set_dx(NULL);
  44.              }
  45.  
  46.              else // c'è il figlio
  47.              {
  48.                 converti_albero (nodo->get_dx(), RB_a_BST); // scendo a destra
  49.              }
  50.           }
  51.        }
  52.     }



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.

PM Quote
Avatar
MagoAntò (Normal User)
Rookie


Messaggi: 42
Iscritto: 07/02/2009

Segnala al moderatore
Postato alle 20:13
Martedì, 22/05/2012
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. :)

PM Quote