[JAVA] problemi alberi binari

[Gin&&Tonic]

Ho risolto un'esercizio , ma non sono scuro che sia giusto.
Posto la traccia e la soluzione (sperando in qualche correzione):


Si consideri una classe AlberoB che rappresenta alberi binari in cui la parte
informativa di ogni nodo è un numero intero.
Si assuma che in tale classe siano implementati i seguenti metodi:

public interface AlberoB {
/* restituisce il sottoalbero destro dell’albero corrente/
public AlberoB destro( );

/* restituisce il sottoalbero sinistro dell’albero corrente*/
public AlberoB sinistro( );

/* restituisce il valore memorizzato nella radice dell’albero */
public int val( );
}



Si deve realizzare un metodo
public static boolean eRipetuto (AlberoB a, int x) {…}

che restituisce true se e solo se vi è almeno un nodo n nell’albero a tale che l’intero
x appare sia nel sottoalbero sinistro che nel sottoalbero destro di n.



soluzione:


public static boolean eRipetuto (AlberoB a, int x) {
if(a.val()==null)return false;

if(a.sinistro().val()==x && a.destro().val()==x) return true;

return eRipetuto (a.destro( ),x) || eRipetuto (a.sinistro( ),x);
}


:help: :help: :help:

[tuccio`]

mi sembra molto più semplice fare una visita iterativa dei due sottoalberi piuttosto che risolverlo ricorsivamente

[Gin&&Tonic]

devo farlo ricorsivo:O

[tuccio`]

non ha molto senso imho

[Gin&&Tonic]

che significa che non ha senso?:confused:

[fero86]

che significa che non ha senso?:confused: ha perfettamente senso invece: gli alberi binari sono strutture definite induttivamente, quindi é naturale che anche gli algoritmi su di essi siano definiti induttivamente (cioé che siano ricorsivi).

posto la mia soluzione non testata:

private boolean find(int x) {
if (val() == x) {
return true;
} else {
return destro().find(x) || sinistro().find(x);
}
}

public boolean eRipetuto(int x) {
if (destro().find(x)) {
if (sinistro().find(x)) {
return true;
} else {
return destro().eRipetuto(x);
}
} else {
if (sinistro().find(x)) {
return sinistro().eRipetuto(x);
} else {
return false;
}
}
}


PS: mi sembrava che avesse piu senso renderlo un metodo d'istanza: é inutile avere un metodo statico che vuole un'istanza della classe come parametro, é del tutto equivalente ad avere un metodo d'istanza.

[Giovanni Tavella]

.

[Gin&&Tonic]

fero86:
é inutile avere un metodo statico che vuole un'istanza della classe come parametro, é del tutto equivalente ad avere un metodo d'istanza.


hai ragione, ma siccome è un'esame, e mi è richiesto un metodo ricorsivo, devo obbligatoriamente fornire il metodo eRipetuto"ricorsivo"
:muro:

[tuccio`]

ha perfettamente senso invece: gli alberi binari sono strutture definite induttivamente, quindi é naturale che anche gli algoritmi su di essi siano definiti induttivamente (cioé che siano ricorsivi).

posto la mia soluzione non testata:

private boolean find(int x) {
if (val() == x) {
return true;
} else {
return destro().find(x) || sinistro().find(x);
}
}

public boolean eRipetuto(int x) {
if (destro().find(x)) {
if (sinistro().find(x)) {
return true;
} else {
return destro().eRipetuto(x);
}
} else {
if (sinistro().find(x)) {
sinistro().eRipetuto(x);
} else {
return false;
}
}
}


PS: mi sembrava che avesse piu senso renderlo un metodo d'istanza: é inutile avere un metodo statico che vuole un'istanza della classe come parametro, é del tutto equivalente ad avere un metodo d'istanza.boh non so cosa ho letto oggi, è chiaramente molto semplice la soluzione ricorsiva, la tua è corretta ovviamente

[malocchio]

ha perfettamente senso invece: gli alberi binari sono strutture definite induttivamente, quindi é naturale che anche gli algoritmi su di essi siano definiti induttivamente (cioé che siano ricorsivi).

posto la mia soluzione non testata:

private boolean find(int x) {
if (val() == x) {
return true;
} else {
return destro().find(x) || sinistro().find(x);
}
}

public boolean eRipetuto(int x) {
if (destro().find(x)) {
if (sinistro().find(x)) {
return true;
} else {
return destro().eRipetuto(x);
}
} else {
if (sinistro().find(x)) {
return sinistro().eRipetuto(x);
} else {
return false;
}
}
}


PS: mi sembrava che avesse piu senso renderlo un metodo d'istanza: é inutile avere un metodo statico che vuole un'istanza della classe come parametro, é del tutto equivalente ad avere un metodo d'istanza.

Quoto tutto, però nel codice manca un return, nel terzo branch, in rosso. Comunque il compilatore l'avrebbe segnalato.

Metodi iterativi su alberi? :mbe: che scherziamo?

Mia congettura pronta per essere smontata: possiamo dire che andando a contare i nodi all'interno dell'albero a che hanno il valore x, se ne troviamo almeno due, eRipetuto(a, x) deve restituire true?
Ho pensato che se in uno stesso albero esistono (almeno) due nodi con il valore x, possiamo trovare il genitore comune a quei due nodi. Dato il genitore comune, sappiamo che nel suo sottoalbero di destra e in quello di sinistra ci sono due nodi con lo stesso valore, quindi "vi è almeno un nodo n nell’albero a tale che l’intero x appare sia nel sottoalbero sinistro che nel sottoalbero destro di n"
Per "genitore comune tra due nodi" intendo il nodo radice del sottoalbero più piccolo che contiene i due nodi.

[fero86]

hai ragione, ma siccome è un'esame, e mi è richiesto un metodo ricorsivo, devo obbligatoriamente fornire il metodo eRipetuto"ricorsivo"
:muro: la mia soluzione é ricorsiva, non va bene?



Quoto tutto, però nel codice manca un return, nel terzo branch, in rosso. Comunque il compilatore l'avrebbe segnalato. giusto, grazie, ho corretto il mio post :)

[fero86]

possiamo dire che andando a contare i nodi all'interno dell'albero a che hanno il valore x, se ne troviamo almeno due, eRipetuto(a, x) deve restituire true? no, non possiamo: uno dei due nodi di valore x potrebbe essere il padre diretto dell'altro nodo, nel qual caso, se la mia interpretazione della traccia é corretta, il metodo deve restituire false.

[malocchio]

no, non possiamo: uno dei due nodi di valore x potrebbe essere il padre diretto dell'altro nodo, nel qual caso, se la mia interpretazione della traccia é corretta, il metodo deve restituire false.

:doh: ccc'hai ragggione

[Gin&&Tonic]

la mia soluzione é ricorsiva, non va bene?



si va bene :) , volevo capire se andava bene anche la mia.:rolleyes: :



public static boolean eRipetuto (AlberoB a, int x) {
if(a.val()==null)return false;

if(a.sinistro().val()==x && a.destro().val()==x) return true;

return eRipetuto (a.destro( ),x) || eRipetuto (a.sinistro( ),x);
}

[tuccio`]

no perché la condizione "a.sinistro().val()==x && a.destro().val()==x" non vuol dire "x è nel sottoalbero sinistro e nel destro", ma vuol dire "il nodo ha due figli che hanno valore x", dovresti visitare i due sottoalberi e vedere se c'è x, così sarebbe corretto (però sarebbe comunque meno efficiente della soluzione di fero, che effettua la chiamata ricorsiva solo nel sottoalbero in cui c'è almeno un nodo x)

[fero86]

si va bene :) , volevo capire se andava bene anche la mia.:rolleyes: :



public static boolean eRipetuto (AlberoB a, int x) {
if(a.val()==null)return false;

if(a.sinistro().val()==x && a.destro().val()==x) return true;

return eRipetuto (a.destro( ),x) || eRipetuto (a.sinistro( ),x);
}
no, non va bene perché, oltre al motivo spiegato da tuccio, al primo if cerchi di confrontare null con un valore nativo.

comunque, volendo mettere i puntini sulle i, anche la mia soluzione é sbagliata in quel caso base perché non ho fatto alcun controllo per vedere se i sottoalberi esistono o meno, di conseguenza immagino che la mia soluzione lanci una NullPointerException :stordita: :D

posto di seguito una versione piu completa:


interface AlberoB {
AlberoB destro();
AlberoB sinistro();
int val();
boolean eRipetuto(int x);
}

abstract class AlberoBImpl implements AlberoB {
public boolean find(int x);
}

final class AlberoVuoto extends AlberoBImpl {
AlberoB destro() {
throw IllegalStateException();
}

AlberoB sinistro() {
throw IllegalStateException();
}

public int val() {
throw IllegalStateException();
}

public boolean find(int x) {
return false;
}

public boolean eRipetuto(int x) {
return false;
}
}

final class AlberoNonVuoto extends AlberoBImpl {
private final AlberoBImpl destro;
private final AlberoBImpl sinistro;
private final int valore;

public AlberoNonVuoto() {
...
}

AlberoB destro() {
return destro;
}

AlberoB sinistro() {
return sinistro;
}

public int val() {
return valore;
}

public boolean find(int x) {
if (val() == x) {
return true;
} else {
return destro().find(x) || sinistro().find(x);
}
}

public boolean eRipetuto(int x) {
if (destro().find(x)) {
if (sinistro().find(x)) {
return true;
} else {
return destro().eRipetuto(x);
}
} else {
if (sinistro().find(x)) {
return sinistro().eRipetuto(x);
} else {
return false;
}
}
}
}


sempre non testata, potrebbe contenere una quantitá invereconda di errori.

[banryu79]

[OT]

Metodi iterativi su alberi? :mbe: che scherziamo?

Perchè, non si possono avere metodi iterativi sugli alberi?
In genere, una funzione ricorsiva può essere tradotta in una equivalente ma in forma iterativa. E a volte ci possono essere buone ragioni per farlo (basti considerare che i metodi di tree traversal ricorsivi richedono spazio sullo stack proporzionale alla profondità dell'albero...)
Mi sono perso qualcosa, o mi sto confondendo con qualcos'altro?

[fero86]

(basti considerare che i metodi di tree traversal ricorsivi richedono spazio sullo stack proporzionale alla profondità dell'albero...) 1) no se il linguaggio é tail-call optimized
2) early optimization is the root of all evil

[malocchio]

[OT]

Perchè, non si possono avere metodi iterativi sugli alberi?
In genere, una funzione ricorsiva può essere tradotta in una equivalente ma in forma iterativa. E a volte ci possono essere buone ragioni per farlo (basti considerare che i metodi di tree traversal ricorsivi richedono spazio sullo stack proporzionale alla profondità dell'albero...)
Mi sono perso qualcosa, o mi sto confondendo con qualcos'altro?

Concettualmente un albero è definito induttivamente, quale struttura migliore per esercitarsi nella scrittura di funzioni ricorsive?
Comunque la vedo ostica trasformare una DFS da ricorsiva a iterativa :asd:
Inoltre, statisticamente parlando penso possiamo dire che la profondità di un albero cresce logaritmicamente rispetto al numero dei nodi...

[DanieleC88]

Comunque la vedo ostica trasformare una DFS da ricorsiva a iterativa :asd:

Basta appoggiarsi alla struttura dati più appropriata: nel caso di una DFS (visita in-order, nel caso degli alberi) basta usare uno stack. Anzi, concettualmente bastano anche un paio di puntatori (però è macchinoso :D).
Vedo più problematica la BFS (visita per livelli, nel caso degli alberi), ma anche là non è difficilissimo: basta usare una coda invece di uno stack.

[fero86]

Concettualmente un albero è definito induttivamente, quale struttura migliore per esercitarsi nella scrittura di funzioni ricorsive? non é solo un esercizio di stile, é anche questione di semplicitá del codice.



Comunque la vedo ostica trasformare una DFS da ricorsiva a iterativa :asd: molto piu semplice di quanto pensi (vedi post di DanieleC88), anche se comunque piu complicato di un algoritmo ricorsivo.



Inoltre, statisticamente parlando penso possiamo dire che la profondità di un albero cresce logaritmicamente rispetto al numero dei nodi... "statisticamente" non vuol dire niente: l'altezza di un albero é logaritmica nel numero di nodi se l'albero gode di una certa proprietá di bilanciamento come quella degli alberi AVL o quella degli alberi RB.

[banryu79]

1) no se il linguaggio é tail-call optimized
2) early optimization is the root of all evil
1) Ok, ma il titolo del thread riporta [JAVA] e, a meno che non mi sia perso per strada qualcosa, questa ottimizzazione in Java non c'è.

2) Su questo sono d'accordo anche io, :) ma non intendevo sottointendere che è sempre meglio implementare i metodi di tree traversal in modo iterativo che ricorsivo, anche perchè non lo penso.

[oNaSsIs]

In generale si parla di ricorsione in coda (o tail recursive) quando una funzione f chiama al suo interno una funzione g (la quale può anche essere f stessa, come nel nostro caso) e il valore che restituisce è proprio quello restituito dalla funzione g, senza alcuna ulteriore computazione. Non è necessario quindi utilizzare un nuovo Record di Attivazione per g dato che f non deve mantenere alcun risultato intermedio, di conseguenza viene proprio utilizzato l'RdA di f per g. Quindi lo spazio utilizzato sullo stack è costante.

[banryu79]

In generale si parla di ricorsione in coda (o tail recursive) quando una funzione f chiama al suo interno una funzione g (la quale può anche essere f stessa, come nel nostro caso) e il valore che restituisce è proprio quello restituito dalla funzione g, senza alcuna ulteriore computazione. Non è necessario quindi utilizzare un nuovo Record di Attivazione per g dato che f non deve mantenere alcun risultato intermedio, di conseguenza viene proprio utilizzato l'RdA di f per g. Quindi lo spazio utilizzato sullo stack è costante.
Grazie delle spiegazioni.
In ogni caso, qui si sta parlando di Java, e bisogna tenere in considerazione le implementazioni esistenti delle specifiche della Java Virtual Machine e del Bytecode.

Una cosa del genere:

public class TailCall
{
private static int tailCallRecursion (int i, int times) {
if (times <= 0) return i;
return tailCallRecursion(i, times-1);
}

public static void main (String... argv) {
int result = tailCallRecursion(0, 10000);
System.out.println(result);
}
}

se compilata e mandata in esecuzione provoca una java.lang.StackOverflowError.

[fero86]

1) Ok, ma il titolo del thread riporta [JAVA] e, a meno che non mi sia perso per strada qualcosa, questa ottimizzazione in Java non c'è. be', il discorso stava prendendo un respiro piu generale.



In generale si parla di ricorsione in coda (o tail recursive) quando una funzione f chiama al suo interno una funzione g (la quale può anche essere f stessa, come nel nostro caso) e il valore che restituisce è proprio quello restituito dalla funzione g, senza alcuna ulteriore computazione. Non è necessario quindi utilizzare un nuovo Record di Attivazione per g dato che f non deve mantenere alcun risultato intermedio, di conseguenza viene proprio utilizzato l'RdA di f per g. Quindi lo spazio utilizzato sullo stack è costante. grazie per le delucidazioni :mbe:

[malocchio]

Concettualmente un albero è definito induttivamente, quale struttura migliore per esercitarsi nella scrittura di funzioni ricorsive?
Comunque la vedo ostica trasformare una DFS da ricorsiva a iterativa :asd:
Inoltre, statisticamente parlando penso possiamo dire che la profondità di un albero cresce logaritmicamente rispetto al numero dei nodi...

Basta appoggiarsi alla struttura dati più appropriata: nel caso di una DFS (visita in-order, nel caso degli alberi) basta usare uno stack. Anzi, concettualmente bastano anche un paio di puntatori (però è macchinoso :D).
Vedo più problematica la BFS (visita per livelli, nel caso degli alberi), ma anche là non è difficilissimo: basta usare una coda invece di uno stack.

non é solo un esercizio di stile, é anche questione di semplicitá del codice.
molto piu semplice di quanto pensi (vedi post di DanieleC88), anche se comunque piu complicato di un algoritmo ricorsivo.
"statisticamente" non vuol dire niente: l'altezza di un albero é logaritmica nel numero di nodi se l'albero gode di una certa proprietá di bilanciamento come quella degli alberi AVL o quella degli alberi RB.

Da quello che ho capito l'autore del post si sta esercitando a lavorare su alberi con la ricorsione...

"statisticamente"... ho usato la parola sbagliata!

[oNaSsIs]

In ogni caso, qui si sta parlando di Java, e bisogna tenere in considerazione le implementazioni esistenti delle specifiche della Java Virtual Machine e del Bytecode.

Hai ragione, il codice da te scritto rispetta la definizione ma restituisce un eccezione di tipo stack overflow. Questa cosa incuriosisce anche me, non ho mai usato la ricorsione in coda con Java e mi sembra una grossa pecca la sua mancata implementazione. Cercherò di documentarmi, per ora ho trovato questo (http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm).

[fero86]

Hai ragione, il codice da te scritto rispetta la definizione ma restituisce un eccezione di tipo stack overflow. la solleva, non la restituisce, ed inoltre é un errore, non un'eccezione.


Questa cosa incuriosisce anche me, non ho mai usato la ricorsione in coda con Java e mi sembra una grossa pecca la sua mancata implementazione. Cercherò di documentarmi, per ora ho trovato questo (http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm). piu che una grossa pecca é un trend: solitamente solo i linguaggi funzionali implementano questa ottimizzazione.

[oNaSsIs]

Chiedo venia per il mio linguaggio inappropriato...:D

[malocchio]

la solleva, non la restituisce, ed inoltre é un errore, non un'eccezione.

Come siamo pignoli! :rotfl:

[banryu79]

la solleva, non la restituisce, ed inoltre é un errore, non un'eccezione.
.
In Java le eccezioni non si "sollevano" (raise) ma si... lanciano! (throw) :D


Come siamo pignoli!

Non "pignoli", ma precisi.
E con questa ho vinto il premio rompicoglioni della domanica :Prrr:

[DanieleC88]

[...] della domanica :Prrr:

Si dice domenica. :O
Fregato il premio! :asd:

[banryu79]

Si dice domenica. :O
Fregato il premio! :asd:
:doh:
...
Ma lol :D

[fero86]

D'OH :rotfl: