Kurssiviikko 13¶

Itseopiskelu¶

Viikon aiheet: (i) Binäärihakupuut, (ii) Tasapainotetut binäärihakupuut

Aiheiden opetusvideot ja kalvot:

Binäärihakupuut¶

Kysymys 1

Oletetaan, että kaikki binäärihakupuun hakuavaimet ovat yksikäsitteisiä. Oletetaan, että \(x\) ja \(y\) ovat binäärihakupuun kaksi solmua, joiden hakuavaimet ovat \(x.key\) ja \(y.key\). Mitkä seuraavista väittämistä ovat aina totta? (Useampi kuin 1 väite voi olla totta.)

Jos \(y.key < x.key\), niin solmu \(y\) on solmun \(x\) vasen lapsi.

Jos \(y.key < x.key\), niin solmu \(y\) on solmun \(x\) vasemmassa alipuussa.

Jos solmu \(y\) on solmun \(x\) vasemmassa alipuussa, niin \(y.key < x.key\).

Jos solmu \(y\) on solmun \(x\) vasemmassa alipuussa, niin \(y.key > x.key\).

Jos solmun \(y\) etäisyys juuresta on suurempi kuin solmun \(x\) etäisyys juuresta, niin solmu \(y\) on yhdessä solmun \(x\) alipuissa.

Jos \(y.key < x.key\) ja solmu \(x\) on binäärihakupuun juuri, niin solmu \(y\) on solmun \(x\) vasemmassa alipuussa.

Kysymys 2

Oletetaan, että kaikki binäärihakupuun hakuavaimet ovat yksikäsitteisiä. Kun etsitään tiettyä hakuavainta \(k\) tavallisella binäärihakupuun hakualgoritmilla (search), algoritmi saavuttaa lehden \(x\). Mikä seuraavista pitää paikkansa?

Lehden \(x\) hakuavain on yhtä suuri kuin \(k\).

Ei ole olemassa solmua, jonka hakuavain on yhtä suuri kuin \(k\).

Jos binäärihakupuussa on solmu, jonka hakuavain on \(k\), niin se on solmu \(x\).

Jos solmun \(x\) hakuavain ei ole yhtä suuri kuin \(k\), hakua on jatkettava aloittamalla binäärihakupuun juuresta ja etsimällä alipuusta, joka ei sisällä solmua \(x\)

Kysymys 3

Jos haluaa saada kaikki binäärihakupuun hakuavaimet nousevassa järjestyksessä, voidaan käyttää …

… leveys ensin hakua (BFS).

… Dijkstran algoritmia.

… välijärjestyksen läpikäyntiä.

… jälkijärjestyksen läpikäyntiä.

Kysymys 4

Oletetaan, että kaikki binäärihakupuun hakuavaimet ovat yksikäsitteisiä ja halutaan lisätä binäärihakupuuhun uusi solmu, jonka hakuavain on \(k\) . Kun käytät tavallista lisäysalgoritmia (insert), mitä voidaan sanoa uuden solmun sijainnista?

Jos \(k\) on pienempi kuin juuren hakuavain, niin uusi solmu tulee olemaan aina vasen lapsi.

Jos \(k\) on pienempi kuin jonkin lehden hakuavain, niin uusi solmu tulee olemaan aina vasen lapsi.

Jos alkuperäisessä binäärihakupuussa on vähintään 2 solmua ja \(x\) on uuden solmun vanhempi, niin uuden solmun lisäämisen jälkeen solmulla \(x\) on täsmälleen 2 lasta.

Uusi solmu aina tulee olemaan lehti.

Kysymys 5

Oletetaan, että kaikki binäärihakupuun hakuavaimet ovat yksikäsitteisiä ja sen solmujen lukumäärä on ainakin 1000. Oletetaan myös, että on olemassa lehti \(x\), jonka hakuavain on \(x.key\). Kun lisätään binäärihakupuuhun uusi solmu \(y\), jonka hakuavain on \(y.key\), mikä seuraavista väitteistä pitää paikkansa?

Jos \(y.key < x.key\), kun uusi solmu \(y\) lisätään lehden \(x\) vasempana lapsena, tulos on aina kelvollinen binäärihakupuu.

Jos \(y.key < x.key\), kun uusi solmu \(y\) lisätään lehden \(x\) oikeana lapsena, tulos on aina kelvollinen binäärihakupuu..

Jos \(y.key < x.key\), kun uusi solmu \(y\) lisätään lehden \(x\) oikeana lapsena, tulos ei ikinä ole kelvollinen binäärihakupuu.

Jos \(y.key < x.key\) ja \(x.key\) alkuperäisen binäärihakupuun pienin hakuavain, kun lisätään \(y\) lehden \(x\) vasempana lapsena, tulos ei ikinä ole kelvollinen binäärihakupuu.

Binäärihakupuiden tehokkuus, tasapainotetut binäärihakupuut¶

Kysymys 1

Oletetaan, että binäärihakupuu on muodostettu lisäämällä \(n\) solmua tyhjään binäärihakupuuhun ja \(n > 1000\). Oletetaan lisäksi, että haetaan avainta, jota ei esiinny binäärihakupuussa. Pahimmassa tapauksessa haku-operaation tehokkuus on lineaarinen solmujen lukumäärän \(n\) suhteen. Mikä seuraavista ominaisuuksista ei vastaa binäärihakupuuta, jolla on tämä pahin mahdollinen tehokkuus?

Binäärihakupuu, jossa kahden lapsen omaavien solmujen lukumäärä on mahdollisimman suuri.

Binäärihakupuu, jonka korkeus on mahdollisimman suuri.

Binäärihakupuu, jossa jokaisella solumlla on korkeintaan 1 lapsi.

Binäärihakupuu, jolla on vain 1 lehti.

Kysymys 2

Oletetaan, että suoritetaan rotaatio binäärihakupuulla \(B1\) ja rotaation jälkeen tulos on binäärihakupuu \(B2\). Mikä seuraavista ei ole mahdollinen seuraus rotaatiosta?

Jonkin solmun oikeasta alipuusta binäärihakupuussa \(B1\) tulee jonkin muun solmun vasen alipuu binäärihakupuussa \(B2\).

Kun solmun \(v\) vanhempi oli solmu \(u\) binäärihakupuussa \(B1\), niin solmun \(u\) vanhempi on solmu \(v\) binäärihakupuussa \(B2\).

Jokaiselle solmulle \(u\) pätee, että solmun \(u\) etäisyys juuresta binäärihakupuussa \(B2\) on pienempi kuin saman solmun etäisyys juuresta binäärihakupuussa \(B1\).

Binäärihakupuun \(B2\) korkeus on pienempi kuin binäärihakupuun \(B1\) korkeus.

Kysymys 3

Mikä seuraavista väitteistä AVL-binäärihakupuusta ei pidä paikkaansa?

Yhtä tai useampaa rotaatiota voidaan käyttää, kun uusi solmu lisätään AVL-binäärihakupuuhun.

Olkoon \(x\) jonkin AVL-binäärihakupuun solmu. Solmun \(x\) vasemman ja oikean alipuun korkeusero on enintään 1.

Olkoon \(x\) jonkin AVL-binäärihakupuun solmu ja \(y\) jokin lehti jossain solmun \(x\) alipuussa. Minkä tahansa lehden \(y\) etäisyys solmusta \(x\) on aina sama arvo.

Olkoon \(x\) jonkin AVL-binäärihakupuun solmu Solmussa \(x\) on tallennettava jotain arvoja, joista voidaan saada eron vasemman ja oikean alipuun korkeuksissa.

Kysymys 4

Oletetaan, että binäärihakupuu on muodostetaan lisäämällä \(n\) solmua tyhjään binäärihakupuuhun ja \(n > 1000\). Tarkastellaan kahta vaihtoehtoa: (I) binäärihakupuun muodostamisessa ei tehdä mitään erityistä sen tasapainottamiseksi, (II) binäärihakupuu muodostetaan joko AVL-binäärihakupuuna tai puna-musta-binäärihakupuuna. Mitä hyötyä saadaan käyttämällä vaihtoehtoa (II)?

Mahdollisuus, että haku-operaation (search) tehokkuus on lineaarinen solmujen lukumäärän \(n\) suhteen, vältetään.

Varmistetaan, että kahden lehden syvyyden välinen ero on enintään 1.

Varmistetaan, että binäärihakupuun korkeus on mahdollisimman pieni.

Varmistetaan, että binäärihakupuussa on olemassa korkeintaan yksi solmu, jolla on täsmälleen yksi lapsi.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

Mikä on binäärihakupuu

Rotaatiot, jotka suoritetaan binäärihakupuussa

AVL-binäärihakupuu

Puna-musta-binäärihakupuu

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Lisäinformaatiota aiheesta:

Weppisivut, joissa voidaan nähdä mm miten binäärihakupuun operaatiot toimivat

Viikko13 - Sanasto

Viikkoharjoitusten palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

Kurssiviikko 13¶

Itseopiskelu¶

Binäärihakupuut¶

Binäärihakupuiden tehokkuus, tasapainotetut binäärihakupuut¶

Esimerkkejä binäärihakupuista¶

Binäärihakupuut¶

Binäärihakupuiden tehokkuus, tasapainotetut binäärihakupuut¶

Viikkoharjoitusten palautettavat kotitehtävät¶