[JAVA] Albero binario di ricerca

[xsatellitex]

Qualcuno puo' aiutarmi a capire come realizzare un algoritmo che verifichi se un albero binario è di ricerca?
Sembrava semplice ma sono stato mezza giornata senza arrivarci.
Cioè ci riesco pure ma viene trooooppo complicato.

Ho capito che la visita simmetrica di un ABR restituisce valori non decrescenti.magari questo puo' aiutare.
:help:
:mc:

[wizard1993]

definizione di albero di ricerca binario:
un albero di ricerca binario è una struttura dati speciale in cui ogni nodo padre ha de figli, quello di sinistra sempre minore del pdre e quello di destra sempre maggiore.

fino a qui ci sei?

[xsatellitex]

certooo so perfettamente com'e' fatto un albero binario di ricerca...
i problemi sorgono quando si scende dalla radice ai vari nodi... Ad esempio:
...........................(20)
......................../..........\
...................(15)..........(25)
................../......\........../.....\
..............(10).(18)...(22)...(30)
....................../....\..../
...................(x)...(y)(z)

in x ci deve essere un valore minore di 18 ma maggiore di 15
in y ci deve essere un valore maggiore di 18 ma minore di 20
in z ci deve essere un valore minore di 22 ma maggiore di 20

è qui che mi intoppo... mi viene troooopo complicato e penso ci sia sicuramente
una soluzione piu semplice :muro:

[morskott]

Un algotirmo scritto in 5 sec sarebbepublic static boolean isBST(Albero alb){
if (alb==null) return true; //Un albero vuoto è un albero di ricerca
if (alb.sx==null && alb.dx==null) return true; //Se sono foglia sono un albero di ricerca
if (alb.sx==null && alb.info.compareTo(alb.dx.info)<0) return true; //Se il sottoalbero sinistro è vuoto e sono piu piccolo del sottoalbero destro sono un BST
if (alb.sx==null && alb.info.compareTo(alb.dx.info)>0) return false; //Se il sottoalbero sinistro è vuoto e sono piu grande del sottoalbero destro non sono un BST
if (alb.dx==null && alb.info.compareTo(alb.sx.info)>0) return true; //Se il sottoalbero destro è vuoto e sono piu grande del sottoalbero sinistro sono un BST
if (alb.dx==null && alb.info.compareTo(alb.sx.info)<0) return true; //Se il sottoalbero destro è vuoto e sono piu piccolo del sottoalbero sinistro non sono un BST
if (alb.info.compareTo(alb.sx.info)<0 || alb.info.compareTo(alb.dx.info)>0) return false; //Se sono piu grande del sottoalbero destro o piu piccolo di quello sinistro non sono un BST
return isBSD(alb.sx) && isBST(alb.dx); //controllo se i miei figli sono bst
}non garantisco che sia giusto

[xsatellitex]

ciao anch'io inizialmente avevo scritto un codice molto simile al tuo pero' poi provandolo mi sono reso conto che non funziona per i problemi che ho citato prima..
cioè bisogna tener conto non solo se i figli sx e dx siano minori e maggiori rispettivamente del padre... ma che sia anche eventualmente minore o maggiore di un suo antenato(come da esempio che ho fatto sopra)

[wizard1993]

ma molto semplicemente:
se il valore da inserire è minore provi a inserire nel nodo di sinistra altrimenti a destra. se il nodo e già ocuppato usi un passo ricorsivo e metti come padre il nodo figlio precedentemente determinato, a me sembra tanto semplice...

[yorkeiser]

Basta implementare un normalissimo algoritmo di visita simmetrica (ne trovi a iosa se googli) e controlli (ad esempio mediante un flag) che l'output dell'algoritmo sia crescente.

[xsatellitex]

wizard tu stai parlando di inserimento... l'inserimento è semplice gia ho realizzato l'algoritmo.
Io parlavo di un algoritmo che verifica se un albero binario è di ricerca o no.
Ad esempio questo albero NON è di ricerca nonostante 1 sia figlio sx del padre e sia minore della chiave del padre:
...........................(20)
......................../..........\
...................(15)..........(25)
................../......\........../.....\
..............(10).(18)...(22)...(30)
....................../........./
...................(16)....(1)

[wizard1993]

scusa un secondo, ma se a destra ci stanno i più grandi e a sinistra i più piccoli, è matematicamente impossibile che uno sia fuoir posto, non credi?
poi,se vuoi essere veramente sicuro, la tua struttura, ritiri fuoir i dai e le meei in uarray e ci passi con un bubble sort, se gli scambi che questo algoritmo fa sono zero al primo passaggio l'array è in ordine.

poi quello non può esser definito un albero di ricerca perchè è totalmente sbagliato, se tu sfruttassi un algoritmo come quello che ti ho descritto l'uno andrebbe a sinistra, non a destra, poi di nuovo a sinistra e infine alla sinistra del 10. non mi sembra tanto complicato, credo sia la struttura di ricerca e ordinamento più semplice che esista

[xsatellitex]

x wizard:
si ma l'albero gia viene dato bello e pronto quindi non sono io a decidere dove va l'1.
io devo solo verificare che sia un albero binario di ricerca. :)
Per il bubble sort va bene ma vorrei evitare di usare altri algoritmi.

x yorkeiser:
si infatti stavo iniziando a ragionare in questo modo


faccio qualche prova :rolleyes:
grazie a tutti :)

[wizard1993]

x wizard:
si ma l'albero gia viene dato bello e pronto quindi non sono io a decidere dove va l'1.
io devo solo verificare che sia un albero binario di ricerca. :)


allora avevo capito male il problema, il metodo più semplice che mi viene in mente per vedere se è ordinato è il mio, se non lo è te ne accorgi subito

[morskott]

Un algoritmo corretto ma forse poco efficente sarebbepublic static boolean isBST2(Albero alb){
Info[] array=arrayzza(alb);
for (int i=1;i<array.length;i++){
if (array[i].compareTo(array[i-1])<0) return false;
}
return true;
}

private static Info[] arrayzza(Albero alb){
Info[] ret=new Info[numElem(alb)];
arrayzza(alb,ret,-1);
return ret;
}

private static int numElem(Albero alb){
if (alb==null) return 0;
return 1+numElem(alb.sx)+numElem(alb.dx);
}

private static int arrayzza(Albero alb,Info[] ret,int index){
if (alb==null) return index;
int ind=arrayzza(alb.sx,ret,index);
ind++;
ret[ind]=alb.info;
ind=arrayzza(alb.dx,ret,ind);
return ind;
}(non sono sicuro sulla funzione arrayzza, forse verrebbe meglioprivate static Info[] arrayzza(Albero alb){
List<Info> lista=new ArrayList<Info>();
arrayzza(alb,lista);
return lista.toArray();
}

private static void arrayzza(Albero alb,List<Info> lista){
if (alb==null) return;
arrayzza(alb.sx,lista);
lista.add(alb.info);
arrayzza(alb.dx,lista);
})

[wizard1993]

io pensavo esattamente il tuo primo esempio, difatto richiede n passaggi per verificare che sia tutto in ordine, altro caso potrebbe essere usre un altro albero binario, che usi come padre il presunto più piccolo, se così fosse il sotto albero di sinistra non dovrebbe mai essere usato, se così fosse, ritorni falso

[morskott]

Tecnicamente anche il secondo esempio ha costo O(n) (non peggiore del primo) anche se è un po farraginoso (fa diventare l'abero un array ordinato e al primo conflitto ritorna falso):il costo per far diventare l'albero un array è O(n), quello per controllare che l'array risultante sia ordinato è O(n), in totale la complessità è O(n)+O(n)=O(n)

[wizard1993]

mentre rimetterlo in un altro albero binario costerebbe n log n. alla fine credo ti servirà il bubble

[xsatellitex]

il metodo arrayzza è perfetto... solo che poi bisogna usare un altro algoritmo per verificare che nella lista ci siano tutti elementi ordinati.
io stavo pensando di farlo senza usare un array o liste ma viene un po complicatuzzo :rolleyes:

anzi mi sa che si puo' fare solo come dite voi

[wizard1993]

il metodo arrayzza è perfetto... solo che poi bisogna usare un altro algoritmo per verificare che nella lista ci siano tutti elementi ordinati.
io stavo pensando di farlo senza usare un array o liste ma viene un po complicatuzzo :rolleyes:

anzi mi sa che si puo' fare solo come dite voi

se sfrutti un array lineare devi poi sfruttare un algoritmo che per le sue cose non muova comunque i dati come un merge o un quick sort, qui viene in aiuto il bubble sort che se non sfrutta il pradigma divide et impera ne altre cose, semplicemente fai si che controlli come nel bubble se l'array è nel giusto ordine, in caso contrario in vece di ordinarlo ritorna che è errato.

[xsatellitex]

Forse ho trovato la soluzione... la sto analizzando ancora un altro po pero':

int Verifica(vertice v,boolean b) // boolean viene passato true
{
if(v.left==null)||(v.right==null) return v.info;
if(Verifica(v.left)>v.chiave)||Verifica(v.right)<v.chiave) b=false;
if(v.right==null) return v.chiave;
else return v.right.chiave;
}

[xsatellitex]

nono è sbagliato...
vabeh mi sono rotto usero' l'array :D
grazie mille per l'aiuto

[gugoXX]

Boh, io un'idea da valutare ce l'avrei, e se non sbaglio e' O(n), nel senso che si effettuano al massimo tanti passi quanti sono i nodi dell-albero.
Direi quindi che dovrebbe essere equivalente all'ottimo.

Una funzione ricorsiva alla quale si passa il nodo da valutare, e 2 valori, ovvero il range di validita' di quel nodo, chiamiamoli min e max.
Se il valore del nodo (value) non e' compreso nell'intervallo, allora male, ritornosubito false.
A qusto punto si valuta ricorsivamente sul sottoalbero di sinistra e su quello di destra.
Il range di validita' del sottoalbero di sinistra e' min - value
il rande di validita' del sottoalbero di destra e' value - max



private bool Verify(Node center, int min, int max)
{
if ((center.Value < min) || (center.Value > max)) return false;
if ((center.left!=null) && (Verify(center.left, min, center.Value) == false)) return false;
if ((center.right!=null) && (Verify(center.right, center.Value, max) == false)) return false;
return true;
}


La prima chiamata sara'
return Verify (Radice,0,infinito);

[wizard1993]

non necessariamente un nodo può essere più grande nel minimo e essere al solito poso, un sistema bubble rihiede 2 n(estrazione e bubble di un solo ciclo per vedere se tutto torna), volendo se uno ci sa fare fa un controllo direttamente in place con complessità n.

[gugoXX]

non necessariamente un nodo può essere più grande nel minimo e essere al solito poso

Non ho capito cosa vuoi dire.

un sistema bubble rihiede 2 n(estrazione e bubble di un solo ciclo per vedere se tutto torna), volendo se uno ci sa fare fa un controllo direttamente in place con complessità n.

a cosa ti servirebbe il bubble?

[wizard1993]

Non ho capito cosa vuoi dire.


forse mi sono spiegato male io, o molto più probabilemente non ci ho capito bene cosa intendi te

a cosa ti servirebbe il bubble?

il bubble sort ha la peculiaretà di non spostare i valori già ordinati per fare i sui comodi, per questo se i valori vengono estratti in una lista e poi gli si fa una passata di bubble per un solo e semplice ciclo, e se l'algoritmo non effetta scambi allora la lista è in ordine, e vuol dire che l'albero è di ricerca

[gugoXX]

forse mi sono spiegato male io, o molto più probabilemente non ci ho capito bene cosa intendi te

Nono, e' proprio che non ho capito la frase:
non necessariamente un nodo può essere più grande nel minimo e essere al solito poso
Non ho capito proprio cosa vuole dire, ne ho capito se era riferita alla mia soluzione.


il bubble sort ha la peculiaretà di non spostare i valori già ordinati per fare i sui comodi, per questo se i valori vengono estratti in una lista e poi gli si fa una passata di bubble per un solo e semplice ciclo, e se l'algoritmo non effetta scambi allora la lista è in ordine, e vuol dire che l'albero è di ricerca

Comunque per verificare se un array e' ordinato non occorre scrivere un algoritmo con 2 cicli annidati (il bubble). E' sufficiente un ciclo che verifichi che l'elemento successivo sia sempre maggiore dell'elemento corrente, senza fare scambi, solo confronti.

[xsatellitex]

gugo quel codice che hai scritto l'avevo scritto anche io come possibile soluzione... ma purtroppo è sbagliato perche ad esempio:
quando fai la chiamata ricorsiva e gli passi come parametro il nodo con chiave 18 ( vedi il mio albero che ho disegnato :D ) il suo figlio destro deve avere come chiave un valore maggiore di 18 ma minore di 20
invece tu dici che deve essere maggiore di 18 ma minore di infinito

è un casino ragionare in questo modo... anche io l ho fatto

wizard parlava di un bubble sort modificato dove alla prima "passata" verificava se c'erano stati scambi... se è cosi ritorna false altrimenti true... quindi un solo ciclo

:)

[gugoXX]

gugo quel codice che hai scritto l'avevo scritto anche io come possibile soluzione... ma purtroppo è sbagliato perche ad esempio:
quando fai la chiamata ricorsiva e gli passi come parametro il nodo con chiave 18 ( vedi il mio albero che ho disegnato :D ) il suo figlio destro deve avere come chiave un valore maggiore di 18 ma minore di 20
invece tu dici che deve essere maggiore di 18 ma minore di infinito


Non l'ho detto.
Se applichi il mio algoritmo, il figlio di destra dovra' essere maggiore di 18 e minore di 20.

20 dovra' essere compreso tra 0 e +inf
15 dovra' essere compreso tra 0 e 20
25 dovra' essere compreso tra 20 e +inf
10 dovra' essere compreso tra 0 e 15
18 dovra' essere compreso tra 15 e 20
16 dovra' essere compreso tra 15 e 18
...
1 dovra' essere compreso tra 20 e 22 --> BREEEG!

0 e infinito non ci sono sempre. Dipende dai valori min e max del nodo chiamante.


wizard parlava di un bubble sort modificato dove alla prima "passata" verificava se c'erano stati scambi... se è cosi ritorna false altrimenti true... quindi un solo ciclo

:)

Non si chiama bubble sort, perche' non deve ordinare.
E' semmplicemente un ciclo che controlla che ogni elemento sia maggiore del precedente.

[xsatellitex]

cavoli rivedendolo mi sa che funziona... e pensare che l'avevo scritto anche io e poi l'avevo scartato :muro:

grazie ;)

[xsatellitex]

solo che infinito come lo rappresento ?

[gugoXX]

solo che infinito come lo rappresento ?

in C# e'
int.maxvalue (magari c'e' un analogo in Java)

Altrimenti proverei con (1<<31) supponendo che gli interi siano a 32bit.

[||ElChE||88]

(magari c'e' un analogo in Java)
Integer.MAX_VALUE

[xsatellitex]

thanks :)

[morskott]

se il problema è dato un albero riconoscere se è BST o no un terzo metodo che non utilizza altre strutture dati ma di complessità (ad occhio) O(n*log(n)) dovrebbe esserepublic static boolean isBST3(Albero alb){
if (alb==null) return true;
if (alb.info.compareTo(max(alb.sx))<0) return false;
if (alb.info.compareTo(min(alb.dx))>0) return false;
return isBST3(alb.sx)&&isBST3(alb.dx);
}

private static Info max(Albero alb){
if (alb==null) return null;
if (alb.sx==null && alb.dx==null) return alb.info;
Info maxSX=max(alb.sx);
Info maxDX=max(alb.dx);
//Devo ritornare il massimo tra maxDX, maxSX e alb.info
if (maxSX==null){
if (maxDX==null){
return alb.info;
}else{
if (maxDX.compareTo(alb.info)>0){
return maxDX;
}else{
return alb.info;
}
}
}else{
if (maxDX==null){
if (maxSX.compareTo(alb.info)>0){
return maxSX;
}else{
return alb.info;
}
}else{
if (maxSX.compareTo(maxDX)>0){
if (maxSX.compareTo(alb.info)>0){
return maxSX;
}else{
return alb.info;
}
}else{
if (maxDX.compareTo(alb.info)>0){
return maxDX;
}else{
return alb.info;
}
}
}
}
}

private static Info min(Albero alb){
if (alb==null) return null;
if (alb.sx==null && alb.dx==null) return alb.info;
Info minSX=min(alb.sx);
Info minDX=min(alb.dx);
//Devo ritornare il minimo tra minDX, minSX e alb.info
if (minSX==null){
if (minDX==null){
return alb.info;
}else{
if (minDX.compareTo(alb.info)<0){
return minDX;
}else{
return alb.info;
}
}
}else{
if (minDX==null){
if (minSX.compareTo(alb.info)<0){
return minSX;
}else{
return alb.info;
}
}else{
if (minSX.compareTo(minDX)<0){
if (minSX.compareTo(alb.info)<0){
return minSX;
}else{
return alb.info;
}
}else{
if (minDX.compareTo(alb.info)<0){
return minDX;
}else{
return alb.info;
}
}
}
}
}

[gugoXX]

Ce l'abbiamo in 5 righe con complessita O(N), sempre senza altre strutture dati...

[morskott]

Ce l'abbiamo in 5 righe con complessita O(N), sempre senza altre strutture dati...

visto ora, sorry, ottimo algoritmo!!!!

[gugoXX]

visto ora, sorry, ottimo algoritmo!!!!

Che fra l'altro e' identico al tuo, solo tiene conto dei valori min e max man mano che si entra nell'albero.