View Full Version : Alberi Liste e complessità
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
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??
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?
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.
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. :D :D :D 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) :D :D
/\/\@®¢Ø
12-02-2003, 09:29
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 ! ;)
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!
/\/\@®¢Ø
12-02-2003, 18:49
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.
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
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
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? :D 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.
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" :D :D :D :D
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
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?
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
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? :D :D :D
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
Hey non ti inkazzare, stavo scherzando. :rolleyes:
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 :D Te le posto + tardi.
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
Originally posted by "SalvoX"
figurati ...non mi sono mica ikazzato per cosi poco...dicevo solo la mia
Ok :p
Originally posted by "SalvoX"
per la 1) sono sicuro di si
Benissimo! :D
Originally posted by "SalvoX"
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 .....
Magari ci si può pure guadagnare qualcosa ma classicamente l'analisi della complessità va fatta a meno di una costante moltiplicativa, quindi una complessità O(100n) e O(50n), per quanto sia + veloce la seconda, a livello formale sono del tutto equivalenti. Questa considerazione va fatta anche durante l'analisi vera e propria, quindi non ti conviene considerare i termini costanti, bensi solamente i fattori predominanti. Questo è importante per 2 motivi: uno riduce la difficoltà dell'analisi, secondo uniforma ipotetici algoritmi in base al loro limite asintotico.
Originally posted by "SalvoX"
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
Non ho capito bene cosa intendi quando dici di usare la struttura dati come se fosse un array. Considera comunque che questa "composizione di strutture", in questo caso una lista di alberi, è solo un bell'esercizio di programmazione. Nella pratica ha ben poca utilità (scusa, nessuna utilità) nonchè poco senso utilizzare una lista di alberi binari. :)
Ciao.
mi riferivo al fatto di poter accedere ad un qualsiasi oggetto della lista in tempo lineare O(n) come avviene per un array
solo mettendo i puntatori su un array di oggetti posso fare ciò e quindi uso questo metodo per gli esercizi dove mi serve
Sulla poca utilità di quello che faccio tramite sta meteria non avevo alcun dubbio :)
cmq serve per fare pratica col linguaggio questo si
Grazie delle info
a presto
Se è per questo un albero binario (soprattutto se completo) si può memorizzare tranquillamente in un vettore ;)
Originally posted by "SalvoX"
mi riferivo al fatto di poter accedere ad un qualsiasi oggetto della lista in tempo lineare O(n) come avviene per un array
solo mettendo i puntatori su un array di oggetti posso fare ciò e quindi uso questo metodo per gli esercizi dove mi serve
Stai attento ad usare questa soluzione. Moli professori se gli cambi la struttura dati ti bocciano senza riserva, anche se quello che hai scritto merita il premio Turing.
Originally posted by "SalvoX"
Sulla poca utilità di quello che faccio tramite sta meteria non avevo alcun dubbio :)
cmq serve per fare pratica col linguaggio questo si
Aspetta la materia è fondamentale, è la lista di alberi che non serve a una mazza :D :D
Originally posted by "SalvoX"
Grazie delle info
a presto
Figurati.
P.S.:Ho provato BugSeeker 2. Funziona bene, ma dopo che l'ho usato e lo chiudo, mi pianta l'intero computer, mouse compreso. Con Linux invece funziona bene. Succede anche a te? :confused:
no a me non capita
cmq tornando al discorso dell'array di oggetti cosa altro potrei fare per raggiungere l'obbiettiovo?
Originally posted by "SalvoX"
no a me non capita
cmq tornando al discorso dell'array di oggetti cosa altro potrei fare per raggiungere l'obbiettiovo?
Attenerti scrupolosamente a quello che richiede il testo :)
Non che non vada bene usare l'array, ma se il prof. vuole che utilizzi una lista concatenata non ti conviene usare qualcosa di diverso...
si ma il insertion sort parla chiaro..devo accedere a un oggetto j-1 senza poter neanche avere un campo prev per tornare indietro (lista semplice ha solo next) ...non vedo molte alternative...la prima versione aveva metodo index ma la complessità veniva n^3 ...e non gli andava bene :)
mah che so a sto punto boh non so cosa inventarmi
Originally posted by "SalvoX"
si ma il insertion sort parla chiaro..devo accedere a un oggetto j-1 senza poter neanche avere un campo prev per tornare indietro (lista semplice ha solo next) ...non vedo molte alternative...la prima versione aveva metodo index ma la complessità veniva n^3 ...e non gli andava bene :)
mah che so a sto punto boh non so cosa inventarmi
Ma quindi non è richiesto di usare esplicitamente una lista...
"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"
:)
Allora non va bene nemmeno il vettore che contiene le radici...
quindi questo programma è infattibile?
(da notare che cmq avevo publicato la prima soluzione senza array di oggetti e funzionava ..ma ripeto una complessità cubica è troppo alta)
Fino a quando sei obbligato ad usare un lista per l'albero ed una lista per per le teste di albero credo che sia impossibile avere una complessita inferiore a O(N^3)...
/\/\@®¢Ø
22-02-2003, 00:35
Scusate... forse non ho capito io il problema, ma la soluzione che avevo proposto io non andava bene ?
:confused:
Facendo prima una scansione degli alberi per trovare le dimensioni, poi fare l'ordinamento e' come
fare un insertion sort su normali interi, o no ?
Qualcosa del tipo
class TreeList
{
public TreeList next;
public int height;
public Tree root;
public static void sort( TreeList begin )
{
TreeList x = begin;
while( x != null )
{
x.height = x.root.height();
x = x.next;
}
insertionSort( begin );
}
ed insertion sort opera normalmente usando il campo height per il confronto.
O e' proprio implementare quest'ultimo con liste che ti da problemi ?
Una possibile implementazione e' la seguente:
void insertionSort( TreeList begin )
{
if ( begin == null )
return;
// prima ordiniamo il resto della lista
insertionSort( begin.next );
// ora inseriamo il nuovo elemento
while( begin.next != null )
{
if ( begin.height > begin.next.height )
{ // swap altezza
int tmp = begin.height
begin.height = begin.next.height;
begin.next.height = tmp;
// swap radice
Tree tmp2 = begin.root;
begin.root = begin.next.root;
begin.next.root = tmp2;
begin=begin.next;
}
}
}
Tieni presente che e' un po' che non scrivo Java e quindi e' possibile che somigli piu' a codice C++ :D.
L'idea comunque e' che dovendo operare su liste e nmon su di un array, la cosa piu' semplice e'
operare per ricorsione. L'algoritmo di solito parte partendo con due elementi, ordinandoli e
aggiungendo poi man mano gli altri. In questo caso e' lo stesso, solo che l'array e' ordinato
a partire dal fondo invece che dall'inizio: la chiamata ricorsiva scorre la lista fino agli ultimi due elementi,
li ordina e poi torna; ritorna all'elemento precedente, lo inserisce e ritorna, e cosi' via finche'
alla fine non fa che inserire l'ultimo elemento (ovvero il primo della lista).
Non e' un algoritmo da manuale, ma e' insertion sort al 100%.
Edit: ovviamente non potevo non fare errori :D. Corretti (quelli che ho visto )
Ri-Edit: corretto un piccolo bug ( non scambiavo le radici... :D )
vBulletin® v3.6.4, Copyright ©2000-2026, Jelsoft Enterprises Ltd.