[Algoritmi] Dubbi su algoritmi di alberi binari

[Sectioaurea]

Salve a tutti, ho bisogno di un aiuto nella risoluzione di questo esercizio sugli alberi binari.
La traccia è la seguente:

Dato un albero T i cui nodi sono etichettati con uno dei due possibili colori verde e giallo, progettare un algoritmo che stabilisca se esiste un cammino monocromatico radice-foglia. Scrivi uno pseudo codice ed analizza la sua complessità.

Allora io ovviamente ho utilizzato la tecnica del Divide et impera però ho qualche dubbio sull'ultima restituzione. Il mio pseudo codice è il seguente:

Sia n la radice dell'albero:

Alg(n)
If(n==NULL)
 Return true;

Else {
           If(n.dato.ch!=n.sx.dato.ch)
            { if(n.dato.ch!=n!dx.dato.ch)
               Return false;
               Else Return Alg(n.dx);
              }
            Else {
              If(n.dato.ch!=n.dx.dato.ch)
               Return Alg(n.sx);
     
               Else return Alg(n.sx) && Alg(n.dx);      (?????)
                }
           }

Mi rendo conto che la penultima riga di comando è scritta male ma non saprei come altro risolvere il problema.
Quando entrambi i figli hanno lo stesso colore cosa dovrebbe restituire il codice?
Grazie a chi risponderà!!

[apatriarca]

L'ultima condizione dovrebbe essere un OR, non un AND. Hai infatti che la condizione è verificata se lo è in almeno uno dei due sottoalberi.

EDIT: Rimosso codice in quanto errato.

[Sectioaurea]

"apatriarca":L'ultima condizione dovrebbe essere un OR, non un AND.

Ma se ad esempio restituisse il sottoalbero "sbagliato"? Faccio un esempio: restituisce alg(n.dx) che avrà un nodo di colore diverso dagli altri, quindi result= false; mentre se avesse restituito alg(n.sx), che presenta un cammino monocromatico radice-foglia, il risultato finale sarebbe stato true. (Scusa per la pessima spiegazione ma non saprei in quale altro modo scriverlo).


Edit: Ho riguardato il significato degli operatori booleani ed ora mi è tutto chiaro! Quindi nel caso in cui uno dei due fosse true allora l'algoritmo restituirà true altrimenti il risultato sarà false.

[apatriarca]

Mi sono reso conto che ci sono molti casi che non sono stati considerati. Per prima cosa un figlio può essere NULL. Per comodità definisco quindi una funzione di supporto (uso python):

def alg(node):
    return (not node) or alg_c(node.colour, node.left) or alg_c(node.colour, node.right)

def alg_c(colour, child):
    return (not child) or (child and child.colour == colour and alg(child))

In altre parole. Un figlio è parte di un percorso monocromatico se è una foglia (NULL) oppure se ha lo stesso colore del padre ed esiste un percorso monocromatico da esso. Percorso monocromatico il cui colore sarà necessariamente quello del padre. Esiste un percorso monocromatico se un nodo è una foglia o se almeno uno dei suoi due figli è parte di un percorso monocromatico come definito in precedenza.Ovviamente si poteva anche scrivere tutto come una singola espressione (o attraverso if annidati o meno).

[Sectioaurea]

"apatriarca":Mi sono reso conto che ci sono molti casi che non sono stati considerati. Per prima cosa un figlio può essere NULL. Per comodità definisco quindi una funzione di supporto (uso python)

Phyton non lo ricordo molto bene purtroppo..

Do uno sguardo al linguaggio e poi mi rileggo il tuo codice.


Ma quello che ho proposto io inizialmente ,anche se contorto (e cambiando quell'and con l'or), è corretto?

[apatriarca]

Manca il test per verificare se il nodo ha effettivamente dei figli destro o sinistro, ma per il resto l'idea è corretta.

[Sectioaurea]

"apatriarca":Manca il test per verificare se il nodo ha effettivamente dei figli destro o sinistro, ma per il resto l'idea è corretta.

Quindi al primo rigo potrei scrivere:

If (n==NULL) || (n.sx==NULL && n.dx==NULL)
Return true;

Così è completo?

[apatriarca]

No, devi testare ogni ramo separatamente prima di cercare di accedere al suo colore. Un ramo può infatti avere anche solo uno dei due figli uguale a NULL..

[Sectioaurea]

"apatriarca":No, devi testare ogni ramo separatamente prima di cercare di accedere al suo colore. Un ramo può infatti avere anche solo uno dei due figli uguale a NULL..

Quindi dovrei aggiungere parecchi if.. Mmmmm

E per quanto riguarda la complessità? Oltre a dire che è lineare potrei aggiungere qualcosa?

[apatriarca]

Non c'è nulla da aggiungere, a meno che non voglia anche la complessità della memoria utilizzata.

[Sectioaurea]

"apatriarca":Non c'è nulla da aggiungere, a meno che non voglia anche la complessità della memoria utilizzata.

Dovrebbe essere $O(nc)$ dove $n$ è la dimensione dell'albero e $c$ la complessità della ricombinazione (passo finale del divide et impera)?

[apatriarca]

Ma in questo caso il costo è costante.. essendo una semplice operazione booleana tra due valori.

[Sectioaurea]

"apatriarca":Ma in questo caso il costo è costante.. essendo una semplice operazione booleana tra due valori.

Va bene, grazie mille!

[Sectioaurea]

Ho un'altra domanda, nel caso in cui viene richiesto un algoritmo che restituisce ad esempio la foglia avente peso massimo (somma dei valori memorizzati in tutti i nodi appartenenti al cammino radice-foglia), come dovrei impostare lo stesso? In questo caso sono bloccata dal fatto che bisogna confrontare più valori ,ed in particolare di foglie.

(Non apro un altro topic per evitare di tempestare il forum di miei quesiti)

[Sectioaurea]

Algoritmo simile, obiettivo: foglia con chiave massima. Io l'ho scritto in questo modo , non sono sicura che sia valido però.

alg(n)
if(n==Null) return null;

else {if(n.sx!=null)
             alg(n.sx);
        if(n.dx!=null)
             alg(n.dx);
         if(foglia(n.sx) && foglia(n.dx))
             { if(n.sx.dato.ch>n.dx.dato.ch)
                 return n.sx;
                 else return n.dx;}
foglia(n)
{ return (n.sx==null)&&(n.dx==null)};

E' giusto? In tal caso è evidente che ci sono troppi if, come potrei migliorarlo?
Per quanto riguarda la complessità, dovrebbe essere sempre lineare.

[apatriarca]

1. Supponiamo di stare nella radice e chiamare la funzione sui due alberi figli. Ogni chiamata ci dirà La foglia con il peso massimo nel sottoalbero. Per sapere quindi qual'è quella nel sottoalbero completo dobbiamo semplicemente confrontare questi due lavori e restituire quello con il valore massimo. La complessità sarà quindi sempre la stessa.

2. Il tuo codice non è corretto (la funzione restituisce qualcosa solo nel caso in cui entrambi i figli siano foglie). Ma l'algoritmo corretto è simile al precedente. L'idea è la seguente:
* Se il nodo è nullo restituisci null.
* Se il nodo è una foglia restituisci se stesso.
* Se il nodo ha figli allora confrontali e prendi il massimo.

[Sectioaurea]

Infatti per il secondo mi ero resa conto che era sbagliato ma non sapevo come correggerlo.
Allora questi dovrebbero essere i due codici:
1. Foglia con peso massimo

alg1(n)
if(n==NULL) return NULL;
if((n.sx==NULL) && (n.dx==NULL) )
          return n;
else{ t=alg1(n.sx);
       s=alg1(n.dx);
        if(peso(t)>peso(s))
             return t;
          else return s;
       }
peso(n)
if(n.padre==NULL) return 0;
else return 1+peso(n.padre);

2. Foglia con chiave massima

alg2(n)
if(n==NULL) return NULL;
if((n.sx==NULL) && (n.dx==NULL) )
          return n;
else{ t=alg2(n.sx);
        s=alg2(n.dx);
        if(t.data.ch>s.data.ch)
             return t;
          else return s;
       }

[Sectioaurea]

Nessuno può aiutarmi?

[apatriarca]

Nel primo, in peso, n può essere null. Per il resto mi sembra corretto.

Nel secondo t o s potrebbero essere null.

Il mio consiglio è di provare questi algoritmi implementandoli in qualche linguaggio.