Kurssiviikko 13

Itseopiskelu

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

Aiheiden opetusvideot ja kalvot:

Binäärihakupuut

Binäärihakupuiden tehokkuus, tasapainotetut binäärihakupuut

Binäärihakupuut

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.)
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?
Jos haluaa saada kaikki binäärihakupuun hakuavaimet nousevassa järjestyksessä, voidaan käyttää …
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?
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?

Binäärihakupuiden tehokkuus, tasapainotetut binäärihakupuut

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?
Oletetaan, että suoritetaan rotaatio binäärihakupuulla \(B1\) ja rotaation jälkeen tulos on binäärihakupuu \(B2\). Mikä seuraavista ei ole mahdollinen seuraus rotaatiosta?
Mikä seuraavista väitteistä AVL-binäärihakupuusta ei pidä paikkaansa?
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)?
Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.
Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?
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