zuhaitzak

BST zuhaitzakAitor Gomez-Goiri

aitor.gomez@deusto.es

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.