[Algoritmi] Dubbi su algoritmi di alberi binari

[Fra27]

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.

[Fra27]

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

Va bene, grazie mille!

[Fra27]

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)

[Fra27]

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

Codice:

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.

[Fra27]

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

Codice:

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

Codice:

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;
       }


[Fra27]

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.