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.