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

[tuccio`]

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

[Gin&&Tonic]

devo farlo ricorsivo

[tuccio`]

non ha molto senso imho

[Gin&&Tonic]

che significa che non ha senso?

[fero86]

Originariamente inviato da Gin&&Tonic

che significa che non ha senso?

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"

[tuccio`]

Originariamente inviato da fero86

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]

Originariamente inviato da fero86

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? 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]

Originariamente inviato da Gin&&Tonic

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

la mia soluzione é ricorsiva, non va bene?

Originariamente inviato da malocchio

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]

Originariamente inviato da malocchio

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]

Originariamente inviato da fero86

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.

ccc'hai ragggione

[Gin&&Tonic]

Originariamente inviato da fero86

la mia soluzione é ricorsiva, non va bene?

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

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]

Originariamente inviato da Gin&&Tonic

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

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

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]

Originariamente inviato da malocchio

Metodi iterativi su alberi? 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]

Originariamente inviato da banryu79

(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]

Originariamente inviato da banryu79

[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
Inoltre, statisticamente parlando penso possiamo dire che la profondità di un albero cresce logaritmicamente rispetto al numero dei nodi...

[DanieleC88]

Originariamente inviato da malocchio

Comunque la vedo ostica trasformare una DFS da ricorsiva a iterativa

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 ).
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.