[Algoritmi] Algoritmo su Albero rosso-nero
Sto facendo un esercizio che mi chiede: sia T un albero rosso-nero contenente n valori.Progettare un algoritmo che calcoli il numero minimo di nodi rossi su un cammino radice-foglia.Si analizzino correttezza e complessità dell'algoritmo proposto.
L'idea che mi era venuta in partenza era quella di scorrere ogni singolo ramo incrementando un contatore ogni qualvolta incontrassi un nodo rosso per poi ritornare questo contatore alla fine di ogni ramo,ovvero quando le foglie dell'ultimo nodo risultassero NIL.Per mettere in pratica questa idea mi sono accorto che non è poi così semplice,infatti per scorrere i vari rami,algoritmi già conosciuti fanno uso della ricorsione,e proprio per questo motivo,se applicassi lo stesso metodo,come potrei distinguere ogni singolo ramo? In alternativa,come potrei scorrere ogni singolo ramo dell'albero usando il metodo iterativo?
L'idea che mi era venuta in partenza era quella di scorrere ogni singolo ramo incrementando un contatore ogni qualvolta incontrassi un nodo rosso per poi ritornare questo contatore alla fine di ogni ramo,ovvero quando le foglie dell'ultimo nodo risultassero NIL.Per mettere in pratica questa idea mi sono accorto che non è poi così semplice,infatti per scorrere i vari rami,algoritmi già conosciuti fanno uso della ricorsione,e proprio per questo motivo,se applicassi lo stesso metodo,come potrei distinguere ogni singolo ramo? In alternativa,come potrei scorrere ogni singolo ramo dell'albero usando il metodo iterativo?
Risposte
Non sono sicuro di aver capito bene il tuo problema. Sia \(reds(T, leaf)\) la funzione che restituisce il numero di nodi rossi nel cammino tra la radice dell'albero T e la foglia leaf di T. Una possibile interpretazione è che lui ti stia chiendendo di calcolare
\[ g(T) = \min_{x \in leafs(T)} reds(T, x) \]
Anche la tua descrizione dell'algoritmo sembra rispettare questa descrizione. Una possibile intepretazione alternativa è di calcolare
\[ \min_{\text{albero $T$ con $n$ nodi}} g(T) \]
che però credo meno probabile e forse è sempre uguale a zero.
Supponendo che sia la prima allora direi che lo puoi definire in modo ricorsivo come segue:
1. Se il nodo corrente è una foglia restituisci zero
2. Se il nodo corrente è nero allora restituisci il minimo tra i valori che ottieni chiamando la funzione sui nodi figli.
3. Se il nodo corrente è rosso restituisci 1 più il minimo valore calcolato chiamando la funzione sui nodi figli.
Il seguente è un esempio in Erlang dell'algoritmo di cui ho scritto sopra per provarlo. Dovrebbe essere abbastanza chiaro..
\[ g(T) = \min_{x \in leafs(T)} reds(T, x) \]
Anche la tua descrizione dell'algoritmo sembra rispettare questa descrizione. Una possibile intepretazione alternativa è di calcolare
\[ \min_{\text{albero $T$ con $n$ nodi}} g(T) \]
che però credo meno probabile e forse è sempre uguale a zero.
Supponendo che sia la prima allora direi che lo puoi definire in modo ricorsivo come segue:
1. Se il nodo corrente è una foglia restituisci zero
2. Se il nodo corrente è nero allora restituisci il minimo tra i valori che ottieni chiamando la funzione sui nodi figli.
3. Se il nodo corrente è rosso restituisci 1 più il minimo valore calcolato chiamando la funzione sui nodi figli.
Il seguente è un esempio in Erlang dell'algoritmo di cui ho scritto sopra per provarlo. Dovrebbe essere abbastanza chiaro..
count_min_reds(leaf) -> 0;
count_min_reds({red, Left, Right}) -> min(count_min_reds(Left), count_min_reds(Right)) + 1;
count_min_reds({black, Left, Right}) -> min(count_min_reds(Left), count_min_reds(Right)).
Io ho provato a modificare l'algoritmo della visita preorder,in questo modo:
assumendo che cont e min siano due variabili int puntate da un puntatore
preorder_minreds(nodo,cont,min){
if(nodo==nil){
if(cont<min || min==0){
min=cont;
}
return;
}
if(color[nodo]==red) cont++;
preorder_minreds(left[nodo]);
preorder_minreds(right[nodo]);
}
assumendo che cont e min siano due variabili int puntate da un puntatore
Prima di tutto, in che linguaggio stai lavorando? Quello che hai scritto è un abbozzo un po' troppo poco preciso. La tua funzione non sembra restituire niente, piuttosto modifica gli argomenti ad essa passati che spero siano passati per riferimento e non per valore. La logica con cui assegni i valori alle variabili min e cont non è del tutto chiaro e neanche in che modo stai passando tale valore alle funzioni in modo ricorsivo (le chiamate ricorsive vengono chiamate con un solo argomento invece che tre..).
In ogni caso il metodo che ti ho descritto funziona ed è molto più semplice. La sola ragione per cui ti ho scritto l'esempio in Erlang è che lo sto imparando e non volevo scriverti la soluzione. Comunque la logica credo sia abbastanza chiara. Devi seguire una struttura del tipo (questo è C++ ma è incompleto):
In ogni caso il metodo che ti ho descritto funziona ed è molto più semplice. La sola ragione per cui ti ho scritto l'esempio in Erlang è che lo sto imparando e non volevo scriverti la soluzione. Comunque la logica credo sia abbastanza chiara. Devi seguire una struttura del tipo (questo è C++ ma è incompleto):
int minreds(Node * node)
{
if (node == NULL) {
return 0;
}
int mrl = minreds(node->left);
int mrr = minreds(node->right);
if (node->color == RED) {
return /* ... */;
} else {
return /* ... */;
}
}
"apatriarca":Non sto lavorando in nessun linguaggio,quello era una sorta di pseudocodice/C che usa la mia prof e il mio libro di testo,comunque non sono d'accordo sul return,non deve mica ritornare a tutti i costi qualcosa,fai conto che sia una funzione void,inoltre visto che è ricorsiva mi è più facile gestire il contatore e il numero minimo di nodi rossi usando dei puntatori interi,altrimenti dovrei sempre ritornarli
Prima di tutto, in che linguaggio stai lavorando? Quello che hai scritto è un abbozzo un po' troppo poco preciso. La tua funzione non sembra restituire niente, piuttosto modifica gli argomenti ad essa passati che spero siano passati per riferimento e non per valore. La logica con cui assegni i valori alle variabili min e cont non è del tutto chiaro e neanche in che modo stai passando tale valore alle funzioni in modo ricorsivo (le chiamate ricorsive vengono chiamate con un solo argomento invece che tre..).
In ogni caso il metodo che ti ho descritto funziona ed è molto più semplice. La sola ragione per cui ti ho scritto l'esempio in Erlang è che lo sto imparando e non volevo scriverti la soluzione. Comunque la logica credo sia abbastanza chiara. Devi seguire una struttura del tipo (questo è C++ ma è incompleto):
int minreds(Node * node) { if (node == NULL) { return 0; } int mrl = minreds(node->left); int mrr = minreds(node->right); if (node->color == RED) { return /* ... */; } else { return /* ... */; } }
Se usi il valore di ritorno che ti ho scritto non c'è alcuni bisogno di memorizzare contatori o minimi in giro.. Leggi il numero minimo di nodi rossi nei sottoalberi figli e scegli quello che ne ha di meno, eventualmente aggiungendo uno se il nodo corrente è rosso. Non ci vedo niente di complicato. Di fatto non c'è comunque alcuna differenza tra usare il valore di ritorno o un argomento, la differenza sostanziale sta nel calcolare il valore dopo la chiamata ricorsiva o nella discesa.. Avrei infatti potuto passare un argomento in più corrispondente al valore minimo di nodi rossi trovato nella discesa, ma mi sembra più intuitivo così. Il tuo metodo può probabilmente essere programmato solo così (il massimo che sono riuscito a fare in un linguaggio - erlang - in cui non è possibile passare variabili per riferimento è mostrato nel codice alla fine del post).
Il principale problema del tuo codice che vedo è che è necessario scegliere opportunamente il valore min (in C probabilmente qualcosa come INT_MAX). Il numero di confronti è però probabilmente inferiore in quanto effetti confronti soltanto alle foglie. Il consumo di memoria mi sembra più o meno lo stesso. La versione che ho presentato io è più adatta ad essere parallelizzata e implementata in linguaggi funzionali, ma la tua è probabilmente più adatta ad essere eseguita in modo iterativo. Insomma.. ogni metodo ha i suoi vantaggi è svantaggi. Non mi è però chiaro se hai ancora dubbi.. Direi che hai praticamente due versioni di questo algoritmo ormai.
Il principale problema del tuo codice che vedo è che è necessario scegliere opportunamente il valore min (in C probabilmente qualcosa come INT_MAX). Il numero di confronti è però probabilmente inferiore in quanto effetti confronti soltanto alle foglie. Il consumo di memoria mi sembra più o meno lo stesso. La versione che ho presentato io è più adatta ad essere parallelizzata e implementata in linguaggi funzionali, ma la tua è probabilmente più adatta ad essere eseguita in modo iterativo. Insomma.. ogni metodo ha i suoi vantaggi è svantaggi. Non mi è però chiaro se hai ancora dubbi.. Direi che hai praticamente due versioni di questo algoritmo ormai.
minreds(leaf, {Count, Min}) -> {Count, min(Count, Min)};
minreds({red, Left, Right}, {Count, Min}) -> minreds(Right, minreds(Left, {Count+1, Min}));
minreds({black, Left, Right}, {Count, Min}) -> minreds(Right, minreds(Left, {Count, Min})).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo