Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ -  alberi binari di ricerca
Forum - C/C++ - alberi binari di ricerca

Avatar
Bonny (Member)
Expert


Messaggi: 435
Iscritto: 24/04/2009

Segnala al moderatore
Postato alle 20:28
Martedì, 08/03/2011
Salve ragazzi non mi è chiara una cosa sui alberi di ricerca.....
cosa si intende per albero Ordinato ???
esempio in un file di testo sono salvati dei record strutturati in questo modo:
nome cognome numeroMatricola.

ecco se io voglio creare un albero ordinato per numeroMatricola...non capisco ilo criterio che devo adoperare per inserire i nodi...

datemi una delucidazione please:)


Bonny
PM
Avatar
VB.NET_Program_91 (Member)
Pro


Messaggi: 93
Iscritto: 10/02/2008

Up
0
Down
V
Segnala al moderatore
Postato alle 21:13
Martedì, 08/03/2011
Allora ti spiego la ricerca binaria con un esempio...

Supponiamo ke KEY sia la variabile che contenga il record da ricercare (sicuramente contenuto nel vettore)
Allora supponiamo di avere un array record contenente la sequenza:

3 7 9 28 23 43 54 65
0 1 2 3   4    5   6  7 (indice)

Creiamo due variabili una di nome PRIMO e una di nome ULTIMO, indichiamo rispettivamente il primo e ultimo indice dell' array, per cui PRIMO = 0 e ULTIMO = 7, creiamo un ulteriore variabile MEZZO che sarà uguale a (PRIMO+ULTIMO)/2 ovvero la posizione centrale della sequenza.
Ora se confrontiamo il vettore contenente i record es. record[MEZZO]  con KEY  otteniamo uno dei seguenti risultati:
__
KEY < record[MEZZO]  quindi KEY si troverà sicuramente nella posizione compresa tra 0 e MEZZO -1
Per tanto la Variabile ULTIMO va impostata a MEZZO-1.
__
KEY = record[MEZZO] quindi la funzione restituisce l' indice.
__
KEY > record[MEZZO]  quindi KEY si troverà sicuramente nella posizione compresa tra MEZZO +1 e n -1
Per tanto la Variabile PRIMO va impostata a MEZZO+1.
__

L' algero di decisione serve solo a dimostrare l' efficienza dell' algoritmo.

Ora passiamo alla parte pratica:
RICERCA BINARIA RICORSIVA
Codice sorgente - presumibilmente C++

  1. int confronta(int x, int y){
  2. if(x<y)
  3. return -1;
  4. else if(x==y)
  5. return 0;
  6. else
  7. return 1;
  8. }
  9.  
  10. int ricercabinaria(int record(),int key.int primo,int ultimo)
  11. {
  12.  int mezzo;
  13. if(primo <= ultimo){
  14. mezzo = (primo+ultimo)/2;
  15. switch(confronta(record[mezzo],key)){
  16. case -1: return
  17. ricercabinaria(record,key,mezzo+1,ultimo);
  18. case 0: return mezzo;
  19. case 1: return
  20. ricercabianria(record,key,primo.ultimo-1);
  21. }
  22. }
  23. return -1;
  24. }



Spero di esserti stato di aiuto :)



I Bravi Programmatori Risolvono i Problemi,
Le Grandi Squadre Fanno la Storia.
--
Non si può prendere colui che non si vede.
PM
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6105
Iscritto: 04/12/2003

Up
0
Down
V
Segnala al moderatore
Postato alle 22:28
Martedì, 08/03/2011
Consiglierei di leggere questa pagina: http://en.wikipedia.org/wiki/Binary_search_tree


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM