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

[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

[morskott]

Un algotirmo scritto in 5 sec sarebbe

public 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
grazie a tutti

[wizard1993]

Originariamente inviato da 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.

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 sarebbe

public 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 meglio

private 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

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

[wizard1993]

Originariamente inviato da 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

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