alberi binari

[misterx]

Originariamente inviato da recoil
hai ragione, grazie per avermelo fatto notare

riguardo al tuo albero non capisco con che logica sono inseriti gli elementi

è rappresentato così sul mio libro, ora a me interessa capire l'eventuale creazione e scansione; magari riordinandoli in ordine crescente

ho visto che con una ricorsione è possibile visitarlo tutto ma mi sfugge il meccanismo

[mjordan]

Originariamente inviato da /\/\@®¢Ø
Non per sembrare polemico (o si ? ) ma quello che ha fatto confusione sei stato tu , visto che non si parlava di ABR da nessuna parte prima del tuo intervento

No la questiona l'avete fatta voi perchè se si parla di visita si parla indiscutibilmente in ABR, visto che tali algoritmi ricorsivi funzionano correttamente solo se il valore delle chiavi è giustamente posizionato (proprietà ABR) altrimenti la visita procede senza alcun rigore logico

[/\/\@®¢Ø]

Originariamente inviato da mjordan
No la questiona l'avete fatta voi perchè se si parla di visita si parla indiscutibilmente in ABR, visto che tali algoritmi ricorsivi funzionano correttamente solo se il valore delle chiavi è giustamente posizionato (proprietà ABR) altrimenti la visita procede senza alcun rigore logico

A questo punto bisogna mettersi cosa si intende per visita.
Ad esempio se ho un albero di parsing di una espressione matematica (che in generale e' un albero binario), si calcola il valore dell'espressione facendo una visita postfissa dello stesso (esempio in "pseudolinguaggio")

parse( tree )= 
	if tree.type == value
		return value
	else
		// visita postfissa
		x = parse( tree.left )
		y = parse( tree.right )
		op = tree.op
		return op( x , y )

Ad esempio con l'espressione "20/4 - 7*2"
ottengo l'albero

       "-"
      /   \
   "/"    "*"
  /  \     / \
20  4  7  2

in cui la visita postfissa elabora nell'ordine
20 -> 4 -> "/" -> 7 -> 2 -> "*" -> "-"

[/\/\@®¢Ø]

Originariamente inviato da misterx
è rappresentato così sul mio libro, ora a me interessa capire l'eventuale creazione e scansione; magari riordinandoli in ordine crescente

ho visto che con una ricorsione è possibile visitarlo tutto ma mi sfugge il meccanismo

In generale non si riordina un albero "in loco". Si preferisce tenerlo ordinato man mano che lo si costruisce. Non sono sicuro, ma penso pure che prendere gli elementi del tuo albero e farne uno nuovo ordinato non sia piu' costoso che non cercare di ordinarlo.

[mjordan]

Originariamente inviato da /\/\@®¢Ø
A questo punto bisogna mettersi cosa si intende per visita.
Ad esempio se ho un albero di parsing di una espressione matematica (che in generale e' un albero binario), si calcola il valore dell'espressione facendo una visita postfissa dello stesso (esempio in "pseudolinguaggio")

parse( tree )= 
	if tree.type == value
		return value
	else
		// visita postfissa
		x = parse( tree.left )
		y = parse( tree.right )
		op = tree.op
		return op( x , y )

Ad esempio con l'espressione "20/4 - 7*2"
ottengo l'albero

       "-"
      /   \
   "/"    "*"
  /  \     / \
20  4  7  2

in cui la visita postfissa elabora nell'ordine
20 -> 4 -> "/" -> 7 -> 2 -> "*" -> "-"

Ok. E dove dovrebbe stare l'analogia con una visita in postordine? Scusami ma non la vedo... Cioè nel senso che la differenza è assai sottile. L'output di quella visita è lo stesso di una visita in postordine su un ABR. Tuttavia l'algoritmo è differente.

[/\/\@®¢Ø]

uff che pignolo !
Il senso e' che una visita (prefissa, infissa o postfissa che si voglia) non e' affatto legata agli ABR, visto che puo' essere fatta con un un generico albero binario. Che io sappia una visita in un albero non ha il solo scopo di stampare il valore, in generale serve a compiere una operazione su ogni elemento in un dato ordine. Se le operazioni che ho utilizzato non vanno bene, sostituisci loro una stampa postfissa del valore ed avrai un programma che dall'albero di parsing "prepara" l'input per una calcolatrice RPN. E' una visita postfissa, ma l'albero non e' un ABR.

[misterx]

ragazzi, stiamo in tema e non perdiamoci in chiecchiere da mercato

quello che desideravo conoscere ordine o non ordine, specifiche rispettate o meno, era come si visitano ed eventualmente si creano alberi binari

vogliamo aggiungerci di ricerca per buona pace di mjordan ?

fai finta che io lo abbia scritto e chiedo venia; così la finiamo lì

dunque, per entrare nel vivo dell'argomento ed essendo impossibilitato a postare codice non mio scrivo:


"ho" costruito una classe di un bellissimo albero binario con al suo interno un'altra classe che crea nodi e relativi sottoalberi sx e dx

problema
io istanzio un solo oggetto di tipo albero ma creo più volte nodi(oggetti) sx e dx, in funzione ad esempio del numero di stringhe che desidero popolino il mio bell'alberello

domanda
ogni volta che uso l'operatore new istanzio un nuovo oggetto (nodo sx/dx) all'interno della classe albero ma; come cavolo fanno a rimanere suddivisi e richiamabili una volta create le stringhe ?

azz, posso capire se avessi implementato all'interno della classe albero un array di stringhe ma istanziando oggetti mica l'ho capito

[/\/\@®¢Ø]

Originariamente inviato da misterx
ragazzi, stiamo in tema e non perdiamoci in chiecchiere da mercato

Chiedo perdono, ho divagato io.

quello che desideravo conoscere ordine o non ordine, specifiche rispettate o meno, era come si visitano ed eventualmente si creano alberi binari

Eh, ma intendi gli ABR o gli alberi binari normali ?
In generale si possono creare in molti modi, e dipende tipicamente da "dove arrivano" i dati. Considerando gli ABR comunque generalmente si parte dall'albero vuoto e si inseriscono man mano gli elementi.

Ti faro' un esempio con codice Java, ma visto che e' un bel po' che non lo uso, do il permesso a mjordan di cazziarmi a suo piacimento nell'eventualita' di strafalcioni .

Questo e' il classico esempio in cui non si puo' fare la distinzione tra chiave e valore, visto che non esiste un modo per associare un numero ad una stringa in modo univoco (cioe', esiste ma la rappresentazione e' la stringa stessa ).
Tra l'altro per questo motivo, non avra' senso "cercare una stringa per chiave", ma semplicemente controllare se l'abbiamo gia' inserita (oltre ovviamente ad inserirla e toglierla)

problema
io istanzio un solo oggetto di tipo albero ma creo più volte nodi(oggetti) sx e dx, in funzione ad esempio del numero di stringhe che desidero popolino il mio bell'alberello

Esatto un nodo per ogni elemento

domanda
ogni volta che uso l'operatore new istanzio un nuovo oggetto (nodo sx/dx) all'interno della classe albero ma; come cavolo fanno a rimanere suddivisi e richiamabili una volta create le stringhe ?

All'interno della classe Albero salvi un riferimento alla radice dell'albero. Da qulla radice puoi raggiungere tutti i nodi.

[recoil]

Originariamente inviato da misterx
io istanzio un solo oggetto di tipo albero ma creo più volte nodi(oggetti) sx e dx, in funzione ad esempio del numero di stringhe che desidero popolino il mio bell'alberello

domanda
ogni volta che uso l'operatore new istanzio un nuovo oggetto (nodo sx/dx) all'interno della classe albero ma; come cavolo fanno a rimanere suddivisi e richiamabili una volta create le stringhe ?

azz, posso capire se avessi implementato all'interno della classe albero un array di stringhe ma istanziando oggetti mica l'ho capito

non ho ben chiaro qual è il tuo dubbio a riguardo
la classe albero non la utilizzi da sola ma all'interno di un'altra classe nella quale creerai l'elemento radice. a quel punto, richiamando i metodi su quell'oggetto (la radice) potrai inserire elementi e cercarli

tieni conto che il new ti restituisce un nuovo oggetto che in pratica è un puntatore. insomma non sei in un caso molto diverso dalla malloc, solo che l'oggettino ha pure i propri metodi e non è una comune struct (ti faccio sti esempi presumendo che tu abbia familiarità con il c, mi pare di ricordare che ne hai).

[/\/\@®¢Ø]

Supponendo di avere la seguente classe
dichiarata all'interno della classe Albero

	private class Nodo
	{
		public Nodo( String s )
		{
			left = null;
			right = null;
			data = s;
		}

		public Nodo left;
		public Nodo right;
		public String data;

	}

puoi implementare le funzionalita' di inserimento/ricerca dell'albero nel
modo seguente:

	private Nodo root;

	public Albero()
	{
		root = null;
	};

	public void add( String s )
	{
		Nodo n = new Nodo(s);
		root = insert(root,n);
	}

	public boolean search( String s )
	{
		return recSearch( root , s );
	}

	private boolean recSearch( Nodo t , String s )
	{
		if ( t == null )
			return false;
		int n = t.data.compareTo(s);
		if ( n == 0 )
			return true;
		if ( n >= 0 )
			return recSearch( t.right , s );
		return recSearch( t.left , s );
	}


	private Nodo insert( Nodo t , Nodo n )
	{
		if ( t == null )
			return n;
		if ( t.data.compareTo( n.data ) >= 0 )
			t.right = insert( t.right , n );
		else
			t.left = insert( t.left, n );
		return t;
	}

Visti i miei ricordi di Java potrei aver scambiato il <= con il >= nel confronto tra stringhe ma la sostanza e' quella.
L'implementazione e' tra le piu' semplici (non molto OO ad esempio) ma la piu' chiare possibili.

[misterx]

Originariamente inviato da recoil
non ho ben chiaro qual è il tuo dubbio a riguardo
la classe albero non la utilizzi da sola ma all'interno di un'altra classe nella quale creerai l'elemento radice. a quel punto, richiamando i metodi su quell'oggetto (la radice) potrai inserire elementi e cercarli

tieni conto che il new ti restituisce un nuovo oggetto che in pratica è un puntatore. insomma non sei in un caso molto diverso dalla malloc, solo che l'oggettino ha pure i propri metodi e non è una comune struct (ti faccio sti esempi presumendo che tu abbia familiarità con il c, mi pare di ricordare che ne hai).

stai dicendo che costruisco una sorta di rete di puntatori ?

[cionci]

Guarda che non era richiesta una visita in postordine...ma una visita posticipata...simmetrica ed anticipata...

//Anticipata
void visita(nodo *n)
{
   if(!n) return;
   elabora(n->info);
   visita(n->sx);
   visita(n->dx);
}

//Posticipata
void visita(nodo *n)
{
   if(!n) return;
   visita(n->sx);
   visita(n->dx);
   elabora(n->info);
}

//Simmetrica
void visita(nodo *n)
{
   if(!n) return;
   visita(n->sx);
   elabora(n->info);
   visita(n->dx);
}

Non c'è una sola visita...basta invertire il ramo che si visita per primo e cambia l'ordine di visita...
Quindi ci sono due possibili sequenze diverse per ogni albero...

[recoil]

Originariamente inviato da misterx
stai dicendo che costruisco una sorta di rete di puntatori ?

beh chiamiamola così
il fatto che Java nasconde i puntatori non significa che non ci sono, in effetti tu costruisci una struttura che si basa sui puntatori.

cmq puoi rappresentare un albero anche con una tabella, anche se non è forse il massimo dell'efficenza.
per un albero generico (intento non necessariamente binario) potresti avere una tabella che associa a ogni elemento il proprio padre (la radice avrebbe un valore nullo per quel campo).
per un albero binario potresti costruire una tabella in cui ad ogni elemento sono associati figlio destro e sinistro.
in alternativa ci sono implementazioni che prevedono il concetto di fratelli...

insomma te ne ho enumerate un po' tanto per dirti che non è necessario focalizzarsi su una sola implementazione anche se quella con i puntatori (che fa uso di memoria dinamica) è nella maggior parte dei casi la più efficente per rappresentare gli alberi.

in ogni caso mi pare che sia più semplice capire questo genere di implementazione in un linguaggio che fa uso esplicito di puntatori. in effetti uno dei primi dubbi che hanno i programmatori c quando passano a Java è: "come faccio a utilizzare le strutture dati dinamiche?"

[verloc]

voi che avete studiato gli alberi, perchè non spiegate i vari tipi di albero che esistono e sopratutto per ciascuno di essi il loro uso tipico?

Così anche i "dilettanti" possono capire

Molto graditi link a tutorials sul web

[recoil]

Originariamente inviato da verloc
voi che avete studiato gli alberi, perchè non spiegate i vari tipi di albero che esistono e sopratutto per ciascuno di essi il loro uso tipico?

Così anche i "dilettanti" possono capire

Molto graditi link a tutorials sul web

ci vorrebbe una bella guida sulle strutture dati, magari divisa in parti teoriche e applicazioni pratiche in modo da coinvolgere più linguaggi.

io al momento non ho molto tempo ma tra un paio di settimane dovrei riuscire a fare qualcosa se siete interessati

[verloc]

si siamo interessati grazie

[misterx]

e qual'è la regola per scrivere un'espressione in notazione postfissa ?

cioè in notazione polacca se non dico cavolate



3 * 5 + (12 - 9) : 8 * 42 - (3 + 25)


grazie 1000

[verloc]

prima i 2 operandi e poi l'operatore

2+5:
2 Enter
5 Enter
+ Enter

ps.Sperem che non aggio detto na' str...

[/\/\@®¢Ø]

Originariamente inviato da misterx
e qual'è la regola per scrivere un'espressione in notazione postfissa ?

cioè in notazione polacca se non dico cavolate



3 * 5 + (12 - 9) : 8 * 42 - (3 + 25)


grazie 1000

Quella di cui parli dovrebbe essere la polacca inverna
(RPN: Reverse Polish Notation), quella diretta dovrebbe avere l'operatore per primo
L'espressione che hai scritto diventa

3 5 * 12 9 - 8 : 42 * + 3 25 + -

Il metodo piu' semplice per trovarla e' scriversi l'albero dalla notazione infissa e poi fare una visita in postordine

[misterx]

Originariamente inviato da /\/\@®¢Ø
Quella di cui parli dovrebbe essere la polacca inverna
(RPN: Reverse Polish Notation), quella diretta dovrebbe avere l'operatore per primo
L'espressione che hai scritto diventa

3 5 * 12 9 - 8 : 42 * + 3 25 + -

Il metodo piu' semplice per trovarla e' scriversi l'albero dalla notazione infissa e poi fare una visita in postordine

infatti è la costruzione dell'albero con una espressione il problema; so che ai nodi vanno gli operatori matematici, meglio aritmetici ( + - * : ) e la distribuzione del calcolo tra semialbero destro o sinistro avviene in funzione della priorità di calcolo dell'espressione; ne caso sotto abbiamo ben due priorità

ma è vero che se scrivo 3 * 5 + (12 - 9) : 8 * 42 - (3 + 25) il compilatore la trasforma in notazione postfissa prima di elaborarne il risultato ?