Alberi Liste e complessità

[SalvoX]

Salve ragazzi
all'univ per un esame dovevo fare questo programma
Definire una classe Java TreeList per una lista linkata semplice in modo che i singoli nodi possano contenere radici di alberi binari.
Scrivere un metodo Java per la classe TreeList che ordini la lista conl'algoritmo dell'Insertion Sort in base alle altezze degli alberi.



che ho così implementato
class Treenodo
{
IntBSTNode info;//contiene le root degli alberi binari
Treenodo next;//contiene il successivo nodo

public Treenodo(IntBSTNode a)
{
this(a,null);
}

public Treenodo(IntBSTNode a, Treenodo n)
{info=a; next=n;}

class Treelist//---------------------------------------------
{
Treenodo head,tail;

public Treelist()
{head=tail=null;}

public Treenodo index(int index)//torna il nodo index 0=head ,1=head.next...
{
Treenodo tmp=head;
for(int i=0; i<index; tmp=tmp.next,i++);
return tmp;
}

public int length()//torna il numero di nodi della lista
{ int cont=0;
Treenodo tmp=head;
while(tmp!=null)
{ cont++;
tmp=tmp.next;
}
return cont;
}

public int altezza(IntBSTNode p)//altezza rispetto al nodo
{
if (p==null) {return -1;}//non esiste
int s=(p.left==null ? -1 : altezza(p.left));//parte sinistra
int d=(p.right==null ? -1 : altezza(p.right));//parte destra
return 1+(s<d ? d : s);//somma a 1 la parte più alta
}//un nodo h=0 ,due nodi h=1
//Dato che ogni nodo della Treelist contiene una radice calcolando l'altezza del nodo si
//calcola l'altezza dello stesso albero

public int hnodo(int i)//torna l'altezza del BST la cui radice sta al nodo i della Treelist
{return altezza(index(i).info);}

public void ListSort()//ordina la lista attiva
{ int i,j,tmp;
IntBSTNode tmp2;

for(i=1; i<length();i++)
{ tmp=hnodo(i);//tengo l'altezza del nodo con indice i
tmp2=index(i).info;//tengo anche il suo campo info

for(j=i; j>0 && tmp<hnodo(j-1); j--)//comparo le altezze

index(j).info=index(j-1).info;//cambio i campi info

index(j).info=tmp2;
}
}//ListSort

Tuttavia come potete vedere la complessità è molto alta(dovrebbe essere O(n^3 )anche se vorrei essere sicuro
magari voi sapete dirmi dove trovare informazioni/link sulla rete su come calcolarla )

Mi è venuta qualche idea su come diminuirla (esempio mettere un array di oggetti che tenga gli indirizzi di mem in modo da non chiamare sempre il metodo index) ma gradirei tanto il vostro aiuto
Tenete presente che prima della call ListSort e dopo gli indirizzi di mem non devono cambiare(solo i riferimenti)


datemi una mano
grazie anticipate

[mjordan]

Gli alberi binari nella lista come devono essere costruiti? Cioè, devi considerarli già nella lista o devi fornire anche dei metodi per costruire gli alberi??

[SalvoX]

no devono essere già nella lista quindi non si deve badare alla loro costruzione (se non nel main ma solo come test)

Qualche link su come documentarmi su puntatori e oggetti in java?

[mjordan]

Originally posted by "SalvoX"

no devono essere già nella lista quindi non si deve badare alla loro costruzione (se non nel main ma solo come test)

Qualche link su come documentarmi su puntatori e oggetti in java?

Ti ho chiesto questo perchè allora potresti fare delle assunzioni su come gli alberi sono stati costruiti. Supponiamo che mantieni un campo nella radice che si incrementa ad ogni nodo inserito nell'albero, e si decrementa per ogni nodo cancellato. Ottieni un campo che ti dice quanti nodi ha un albero. Così, aumentando l'inserimento e la cancellazione di un fattore costante, puoi continuare ad effettuare una insertion sort sulla lista mantenendo complessità asintotica O(n^2).

Per Java ti consiglio Thinking in Java, Bruce Eckel, Apogeo Editore. Questo libro, seppur pubblicato da Apogeo, è stato pubblicato sotto OPL, quindi dovrebbe essere liberamente distribuibile in rete. Ne trovai una copia in rete in formato PDF. Se aspetti un attimo ti faccio pure una ricerca.

[mjordan]

Originally posted by "SalvoX"

no devono essere già nella lista quindi non si deve badare alla loro costruzione (se non nel main ma solo come test)

Qualche link su come documentarmi su puntatori e oggetti in java?

Ecco quà. Qui ci sono i mirror per scaricare il libro:

http://www.mindview.net/Books/TIJ/

E' uno dei migliori testi per quanto riguarda Java. Highly recommended. Inoltre ha il vantaggio che oltre a essere ottimo, è anche in PDF, così non ti cechi a leggere (magari stampalo o acquistalo, questo è uno di quei testi che un giorno non userai per accendere camini)

[/\/\@®¢Ø]

Una soluzione un po' spartana ma efficace e' quella di aggiungre uncampo "height" ai nodi della lista (non degli alberi !). Visto che non ti e' chiesto di aggiungre/togliere/modificare gli alberi, puoi trovarti tutte le altezze con un primo passaggio ( O(n) sul numer complessivo di nodi ) e infine esegui un normale insertion sort (o qualsiasi altro) utilizzando le altezze precalcolate.

Marco

P.S. : un'altra volta cerca di utilizzare i tag [ code ] per il cdice !

[mjordan]

Originally posted by "/\/\@®¢Ø"

Una soluzione un po' spartana ma efficace e' quella di aggiungre uncampo "height" ai nodi della lista (non degli alberi !). Visto che non ti e' chiesto di aggiungre/togliere/modificare gli alberi, puoi trovarti tutte le altezze con un primo passaggio ( O(n) sul numer complessivo di nodi ) e infine esegui un normale insertion sort (o qualsiasi altro) utilizzando le altezze precalcolate.

Marco

P.S. : un'altra volta cerca di utilizzare i tag [ code ] per il cdice !

Ma con insertion sort non serve fare una scansione preliminare della lista. Ha un tempo asintotico di O(n^2) appunto perchè l'algoritmo scandisce direttamente la lista alla ricerca del nodo + piccolo/+ grande ad ogni passaggio per poi "inserirlo" nella posizione corretta.
Inoltre la tua soluzione non aggiunge nulla alla mia, il risultato è praticamente lo stesso, visto che sapere il numero di nodi sia nella tua soluzione che nella mia consiste al più in una dereferenziazione di un puntatore. Solo che il numero di nodi, se sono di un albero, non ha senso metterli nel nodo di una lista!

[/\/\@®¢Ø]

La scansione preliminare mi serve per calcolarmi le altezze all'inizio per non dovere ricalocarmi le altezze degli alberi gia' inseriti dopo, tutto li'
Comunque hai ragione che sostanzialmente la soluzione mia e tua non sono differenti. Pero' faccio un paio di osservazioni: non e' bella cosa aggiungere un campo ad ogni nodo quando le informazioni ti servono solo per la radice. Inoltre non e' detto che tu abbia la possibilita' di modificare il codice degli alberi.

[SalvoX]

Allora ragazzi ho modificato un po il codice ecco il fulcro

class Treenodo
{
	IntBSTNode info;//contiene le root degli alberi binari
	Treenodo next;//contiene il successivo nodo
	int h;//contiene l'altezza del relativo albero

public Treenodo(IntBSTNode a)
{
	this(a,null);
}

public Treenodo(IntBSTNode a, Treenodo n)
{info=a; next=n; h=IntBST.altezza(a);}

public IntBSTNode visit()
{return info;}

}//class Treenodo

class Treelist//---------------------------------------------
{
	Treenodo head,tail;
	Treenodo[] index;//Array di obj treenodo dove tengo gli ind i mem
	int ind=0;//indice per sapere totale treenodi

public Treelist()
{head=tail=null;index=new Treenodo[10];}

public boolean isEmpty()
{return head==null;}


public void ListSort()//ordina la lista attiva
{ int i,j,tmp;
  IntBSTNode tmp2;

	for(i=1; i<ind;i++)
		{ tmp=index[i].h;//tengo l'altezza del nodo con indice i
		  tmp2=index[i].info;//tengo anche il suo campo info

		  for(j=i; j>0 && tmp<index[j-1].h; j--)//comparo le altezze

		  		index[j].info=index[j-1].info;//cambio i campi info

		  index[j].info=tmp2;
		}
}//ListSort

//-----------------------------------------------------------------------------
public void printAll()//stampa tutte le radici
	{
		System.out.println("\n lista=");
		for(Treenodo tmp=head; tmp !=null; tmp=tmp.next)
		System.out.println("rad"+tmp.info.key + " ");
	}

public void printH()//stampa tutte le altezze
	{
		System.out.println("\n lista=");
		for(Treenodo tmp=head; tmp !=null; tmp=tmp.next)
		System.out.println("H="+tmp.h + " ");
	}



public void addToTail(IntBSTNode el)//aggiunge in coda
	{
		if(!isEmpty())//se la lista non è vuota
		 {tail.next=index[ind++]=new Treenodo(el);//nuovo obj
		  tail=tail.next;}//fa puntare il vecchio tail al nuovo obj
		else
			head=tail=index[ind++]=new Treenodo(el);//se la lista è vuota
	}



}//class Treelist

Quindi in ogni nodo ho messo h in modo da averla già pronta e non doverla calcolare ogni volta (notate che altezza è un metodo static di IntBST quindi si può richiamare da fuori senza obj attivo)

In TreeList ho pensato di mettere Treenodo[] index dove tengo i puntatori ad ogni singolo oggetto ma potendo accedere attraverso index[i]
inoltre ho aggiunto
int ind=0;//indice per sapere totale treenodi che evita il metodo length

La complessità cosi scende di molto ma adesso il prog non funza +
Il problema sta in ListSort e dipende dal modo in cui java usa i puntatori credo...in pratica non agisco sulla lista ma solo sull'array

Avete qualche idea ? mi serve davvero il vostro aiuto ragazzi se no non continuavo a rompere

Il problema di base è accedere ai nodi della lista in modo diretto(come su un array appunto) senza scandire (e quindi COMPLEXare il prog) tutta la lista

Sono nelle vostre mani
il codice allegato è quello nuovo
Se non potete farmi il metodo mi spieghereste (magari graficamente) cosa avviene nella mem con sti puntatori java?

Tnx sempre e comunque
ciao

[SalvoX]

ragazzi nel frattempo che ci siamo potreste consigliarmi un Debugger visuale facile per java?
ho usato jdb ma non è il massimo essendo da console..potrebbe essermi d'aiuto

molte grazie

[mjordan]

Originally posted by "SalvoX"

ragazzi nel frattempo che ci siamo potreste consigliarmi un Debugger visuale facile per java?
ho usato jdb ma non è il massimo essendo da console..potrebbe essermi d'aiuto

molte grazie

Tanto anche i debugger visuali per essere usati ad un buon livello richiedono l'immissione dei comandi dell'inferior debugger, tanto vale impratichirti col JDB. Tanto che differenza fa vedere l'output a console o in una finestra? Io + che altro direi che JDB fa schifo proprio come debugger, almeno fino a quando non vedi GDB. Purtroppo il supporto a Java di GDB è ancora arrangiato e sperimentale. Quindi, a parte i debugger integrati negli ambienti di sviluppo, non so cosa consigliarti.

[mjordan]

Originally posted by "/\/\@®¢Ø"

La scansione preliminare mi serve per calcolarmi le altezze all'inizio per non dovere ricalocarmi le altezze degli alberi gia' inseriti dopo, tutto li'

Non avevo capito. Io ho detto ciò perchè i docenti di Algoritmi e Strutture di Dati sono i + pignoli del mondo e trovano una minima scusa per dire "torna la prossima volta"

[SalvoX]

ehehe è proprio vero

[SalvoX]

we ragazzi ho trovato un debugger davvero fantastico per java
http://www.karmira.com/ trovate bugseeker (versione evaluation 30 giorni ma vi dovete lasciare la mail per avere il codice
di 30 giorni)
tutto visuale permette di fare debug davvero precisi tramite print delle var/stack/ ecc ecc
Se qualcuno riesce a "ranarlo" mi mandi un pvt
ciao

[M86]

Originally posted by "SalvoX"

Salve ragazzi
all'univ per un esame dovevo fare questo programma
Definire una classe Java TreeList per una lista linkata semplice in modo che i singoli nodi possano contenere radici di alberi binari.
Scrivere un metodo Java per la classe TreeList che ordini la lista conl'algoritmo dell'Insertion Sort in base alle altezze degli alberi.



che ho così implementato
class Treenodo
{
IntBSTNode info;//contiene le root degli alberi binari
Treenodo next;//contiene il successivo nodo

public Treenodo(IntBSTNode a)
{
this(a,null);
}

public Treenodo(IntBSTNode a, Treenodo n)
{info=a; next=n;}

class Treelist//---------------------------------------------
{
Treenodo head,tail;

public Treelist()
{head=tail=null;}

public Treenodo index(int index)//torna il nodo index 0=head ,1=head.next...
{
Treenodo tmp=head;
for(int i=0; i<index; tmp=tmp.next,i++);
return tmp;
}

public int length()//torna il numero di nodi della lista
{ int cont=0;
Treenodo tmp=head;
while(tmp!=null)
{ cont++;
tmp=tmp.next;
}
return cont;
}

public int altezza(IntBSTNode p)//altezza rispetto al nodo
{
if (p==null) {return -1;}//non esiste
int s=(p.left==null ? -1 : altezza(p.left));//parte sinistra
int d=(p.right==null ? -1 : altezza(p.right));//parte destra
return 1+(s<d ? d : s);//somma a 1 la parte più alta
}//un nodo h=0 ,due nodi h=1
//Dato che ogni nodo della Treelist contiene una radice calcolando l'altezza del nodo si
//calcola l'altezza dello stesso albero

public int hnodo(int i)//torna l'altezza del BST la cui radice sta al nodo i della Treelist
{return altezza(index(i).info);}

public void ListSort()//ordina la lista attiva
{ int i,j,tmp;
IntBSTNode tmp2;

for(i=1; i<length();i++)
{ tmp=hnodo(i);//tengo l'altezza del nodo con indice i
tmp2=index(i).info;//tengo anche il suo campo info

for(j=i; j>0 && tmp<hnodo(j-1); j--)//comparo le altezze

index(j).info=index(j-1).info;//cambio i campi info

index(j).info=tmp2;
}
}//ListSort

Tuttavia come potete vedere la complessità è molto alta(dovrebbe essere O(n^3 )anche se vorrei essere sicuro
magari voi sapete dirmi dove trovare informazioni/link sulla rete su come calcolarla )

Mi è venuta qualche idea su come diminuirla (esempio mettere un array di oggetti che tenga gli indirizzi di mem in modo da non chiamare sempre il metodo index) ma gradirei tanto il vostro aiuto
Tenete presente che prima della call ListSort e dopo gli indirizzi di mem non devono cambiare(solo i riferimenti)


datemi una mano
grazie anticipate

scusa l'intromissione ma tu all'università sai prima dell'esame quello che dovrai fare?

[SalvoX]

magari

questo è un precedente compito di un vecchio appello e quindi devo risolverlo per farmi "le ossa" diciamo

Cmq ho risolto in parte il prob ..posto la soluzione presto cosi vediamo come va

[mjordan]

Originally posted by "SalvoX"

we ragazzi ho trovato un debugger davvero fantastico per java
http://www.karmira.com/ trovate bugseeker (versione evaluation 30 giorni ma vi dovete lasciare la mail per avere il codice
di 30 giorni)
tutto visuale permette di fare debug davvero precisi tramite print delle var/stack/ ecc ecc
Se qualcuno riesce a "ranarlo" mi mandi un pvt
ciao

Oggi per fantastico si intende "visivamente appagante", vero?

[SalvoX]

x mjordan
beh io non sono affatto tra quelli che sceglie un programma per l'aspetto visivo anzi tutto il contrario
con questo debug faccio in pochi istanti quello che prima dovevo fare con una sfilzadi comandi dos e inoltre ho la visione sinottica della memoria e dello stack...ho aumentato la produttività del 80%...se poi te sei uno di quelli che preferisce un bello sfondo nero e e grafica ascii beh io sono per la più totale libertà )) io se trovo qualcosa che mi aiuta graficamente la preferisco(purchè abbia un senso usarla)

Tornando al programma ecco la nuova versione

class Treenodo
{
	IntBSTNode info;//contiene le root degli alberi binari
	Treenodo next;//contiene il successivo nodo
	int h;//contiene l'altezza del relativo albero

public Treenodo(IntBSTNode a)
{
	this(a,null);
}

public Treenodo(IntBSTNode a, Treenodo n)
{info=a; next=n; h=IntBST.altezza(a);}//altezza è un metodo statico

public IntBSTNode visit()
{return info;}

}//class Treenodo

class Treelist//---------------------------------------------
{
	Treenodo head,tail;
	Treenodo[] index;//Array di obj treenodo dove tengo gli ind i mem
	int ind=0;//indice per sapere totale treenodi

public Treelist()
{head=tail=null;index=new Treenodo[10];}//array fisso a 10..si potrebbe usare vector

public boolean isEmpty()
{return head==null;}


public void ListSort()//ordina la lista attiva
{ int i,j,tmp;
  Treenodo tmp2;

	for(i=1; i<ind;i++)
		{ tmp=index[i].h;//tengo l'altezza del nodo con indice i
		  tmp2=index[i];//tengo obj

		  for(j=i; j>0 && tmp<index[j-1].h; j--)//comparo le altezze
			{
		  		index[j]=index[j-1];//sistemo l'array

			}
		  index[j]=tmp2;

		}
	for(int k=0;k<ind-1;k++)//cicla n-1 volte
		if(index[k].next != index[k+1])//mi assicuro che il campo next sia giusto
		 	index[k].next=index[k+1];//se non lo è lo assegno

	head=index[0];//collego la testa
	tail=index[ind-1];//collego la coda

}//ListSort

//-----------------------------------------------------------------------------
public void printAll()//stampa tutte le radici
	{
		System.out.println("\n lista=");
		for(Treenodo tmp=head; tmp !=null; tmp=tmp.next)
		System.out.println("rad"+tmp.info.key + " ");
	}

public void printH()//stampa tutte le altezze
	{
		System.out.println("\n lista=");
		for(Treenodo tmp=head; tmp !=null; tmp=tmp.next)
		System.out.println("H="+tmp.h + " ");
	}



public void addToTail(IntBSTNode el)//aggiunge in coda e aggiorna index
	{
		if(!isEmpty())//se la lista non è vuota
		 {tail.next=index[ind++]=new Treenodo(el);//nuovo obj
		  tail=tail.next;}//fa puntare il vecchio tail al nuovo obj
		else
			head=tail=index[ind++]=new Treenodo(el);//se la lista è vuota
	}



}//class Treelist

praticamente adesso la complessità dovrebbe essere O(n^2) + n ma non ne sono sicuro....l'array fisso a 10 o costante che sia non è il massimo....per il resto non mi viene in mente nulla

fatemi sapere che ne pensate

ciao e grazie

[mjordan]

Hey non ti inkazzare, stavo scherzando.

La tua implementazione mi sembra discreta, ma considera delle cose, solo a livello di riflessione:
1) L'assunzione che abbiamo fatto nel mantenere le altezze degli alberi sarebbe stata accettata dal tuo prof?
2) Il miglioramento del tempo di esecuzione è solo teorico. Nella pratica ciò che guadagni evitando di effettuare una scansione degli alberi per vedere quanti nodi contiene, lo perdi nell'effettivo inserimento del nodo (per ogni nodo inserito/cancellato devi effettuare un incremento/decremento).

Avevo fatto altre osservazioni che ora non ricordo Te le posto + tardi.

[SalvoX]

figurati ...non mi sono mica ikazzato per cosi poco...dicevo solo la mia

per la 1) sono sicuro di si
per la 2) beh credo che si guadagni qualcosa di +(se vedicoem era il metodo lenght beh ci sono molti + confronti di un semplice assegnamento quindi credo che il guadagno ci sia..cmq tu credi di saper calcolare la complessità in questa ultima versione?
approssimativamente .....

cmq tanto per dirti ho provato a fare un metodo per fare lo swap di due oggetti tipo Nodo (doppio o semplicemente linkato) e viene davvero difficile e lungo quindi credo che userò sempre questo sistema per gestire la struttura dati in questione come fosse un array..che ne dici?
grazie dele tue risposte