zuhaitzak
DESCRIPTION
Programazioa II (2012): 6. gaiaTRANSCRIPT
BST zuhaitzakAitor Gomez-Goiri
Deustuko UnibertsitateaIngeniaritza fakultateahttp://www.deusto.es
2012/04/24
Aurkezpena
1 Zuhaitzak informatikan
2 BST zuhaitzen inplementazioa
3 Comparable
4 BST klaseko metodoak
5 Ibilbideak
Aurkezpena
1 Zuhaitzak informatikan
2 BST zuhaitzen inplementazioa
3 Comparable
4 BST klaseko metodoak
5 Ibilbideak
Zuhaitzak informatikan
Egitura mota bat da.Izena, noski, naturako zuhaitzetatik hartzen du,amankomunean honako ezaugarriak baititu:
Adarrak == nodo batetik hurrengorako loturakErroa == lehenengo nodoaHostoak == loturarik gabeko nodoak
BST zuhaitzak
Binary Search Tree (BST).Klasean ikusiko dugun zuhaitz mota da.
Ezaugarriak:Elementuak ordenean gordetzen ditu (txikienetikhandienera)Nodo bakoitza bi nodoetara lotuta dago:
Ezkerraldea: elementu txikiago bat duen nodo batekin.Eskuinaldea: elementu handiago bat duen nodo batekin.
Zertarako behar ditugu?
Askotan elementuak gako baten arabera gorde/bilatubehar dira:
NaN-aEskaera baten erreferentzia zenbakiaProduktu baten barra-kodea
Laburbilduz, honetarako behar ditugu zuhaitzak:Datuak gordetzeko beste egitura bat da (zerrendak bezala)Berezitasuna: datuak irizpide baten arabera ordenatzendiraIrizpide horren arabera berreskuratzerakoan, zerrenda batbaino arinago bueltatzen ditu
Aurkezpena
1 Zuhaitzak informatikan
2 BST zuhaitzen inplementazioa
3 Comparable
4 BST klaseko metodoak
5 Ibilbideak
BST inplementazioa
Nodo bakoitzak honako elementuak ditu:Beste elementuekin alderatu ahal dugun elementuaEzkerraldeko nodoa: elementu txikiagoa duenaEskuinaldeko nodoa: elementu handiagoa duena
public class NodoA{
private Comparable elementua;
private NodoA ezkerraldekoa;
private NodoA eskuinaldekoa;
...
}
BST adibidea
Adibidez, Integer motako elementuak gordetzen baditugu...
Aurkezpena
1 Zuhaitzak informatikan
2 BST zuhaitzen inplementazioa
3 Comparable
4 BST klaseko metodoak
5 Ibilbideak
Zer da Comparable?
Nola alderatu ditzakegu elementuak?Comparable interfazea erabiliz.
Zer da interfaze bat?Atributurik gabeko eta metodo abstraktuak baino ez dituenklase bat bezalakoa da
Zertan datza Comparable interfazea?
Zer egin behar dugu klase bat Comparable bihurtzeko?Metodo bat gainidatzi.
int compareTo(Object o)
Zer egiten du?this<o bada
0 baino txikiagoa den zenbakia bueltatuthis==o bada
0 bueltatuthis>o bada
0 baino handiagoa den zenbakia bueltatu
Javako Comparableak
Integer, Double, String eta hainbat klase betetzen duteComparable interfazea.
Horrexegatik era horretako objektuak sartu ahal izangoditugu gure BSTan
Zenbakiekin errez ulertu ahal da:
(new Integer(1)).compareTo( new Integer(2) ) // < 0
(new Integer(1)).compareTo( new Integer(1) ) // == 0
(new Integer(4)).compareTo( new Integer(3) ) // > 0
String klaseak alfabetikoki ordenatzen ditu hitzak
"bizkaia".compareTo("bizkaia") // == 0
"araba".compareTo("bizkaia") // < 0
"gipuzkoa".compareTo("bizkaia") // >0
Comparable klase bat programatzeko
Eta gure klaseak Comparable bihurtzeko?Adibidez, ikasleak NaN-aren arabera ordenatzen badira...
public class Ikaslea implements Comparable {
private int nan;
private String izena;
...
public int compareTo(Object o) {
Ikaslea ik = (Ikaslea) o;
if( this.nan==ik.nan ) return 0;
if( this.nan<ik.nan ) return -1;
// if( this.nan>ik.nan )
return 1;
}
}
Aurkezpena
1 Zuhaitzak informatikan
2 BST zuhaitzen inplementazioa
3 Comparable
4 BST klaseko metodoak
5 Ibilbideak
BST klaseko metodoak
public Comparable bilatu(Comparable bilatuNahiDenElem);
public boolean sartu(Comparable sartuNahiDenElem);
public Comparable ezabatu(Comparable obj);
Aurkezpena
1 Zuhaitzak informatikan
2 BST zuhaitzen inplementazioa
3 Comparable
4 BST klaseko metodoak
5 Ibilbideak
Ibilbideak
Zuhaitzeko elementuekin zeozer egiteko, nodoz nodo ibilibehar dugu.
Elementu bat gakoa ez den irizpide baten araberabilatzerakoan.Elementu guztiekin zeozer egiterakoan (adibidez, atributubat aldatzeko).
Hori egiteko era desberdinak daude:Pre-orderIn-orderPost-order
Lizentzia
Irudien guztien jabetza intelektuala bere egileena* da,gainontzeko edukiak Creative Commons by-sa 3.0
lizentziapean daude.
* Ian Britton.