Kurssiaihe 12¶

Itseopiskelu¶

Viikon aihe: Hajautustaulut

Aiheiden opetusvideot ja kalvot:

Hajautustaulut¶

Kysymys 1

Miten hakuavainta käytetään hajautustaulun yhteydessä?

Hajautustaulun oletustila on, että se on lukittu, toisin sanoen hajautustaulun alkioita ei voi käyttää. Hakuavaimella voimme avata hajautustaulun lukituksen.

Hajautustaulu on käytännössä vain vektori ja kuhunkin paikkaan (tai indeksiin) voidaan tallentaa tietueen. Hakuavain on vain mahtipontinen synonyymi vektorin indeksille.

Tyypillisesti hajautustaulu sisältää useita hakuavaimia, joista jokainen toistetaan. Siksi hajautustaulussa on kaksi paikkaa (tai ämpäriä), jotka sisältävät saman hakuavaimen. Hajautustaulun käyttämiseksi on etsittävä kaksi paikkaa, jotka sisältävät saman hakuavaimen.

Yksikäsitteinen hakuavain liittyy jokaiseen alkioon, joka on tallennettu jonnekin hajautustauluun. Hakuavaimen avulla voidaan löytää alkion sijainnin ja siten käyttää alkion sisältöä.

Kysymys 2

Oletetaan, että halutaan tallentaa hajautustauluun kaksi hakuavainta \(k1\) ja \(k2\) ja niihin liittyvät tietueet. Oletetaan, että \(k1\) tallennetaan ennen hakuavainta \(k2\). Jos \(k1\) ja \(k2\) osoittavat samaan ämpäriin, miten tämä tilanne hoidetaan ketjutetussa hajautuksessa?

Jokaiseen ämpäriin on liitetty tietorakenne, yleensä linkitetty lista. Hakuavaimet \(k1\) ja \(k2\) ja niihin liittyvät tietueet tallennetaan molemmat jonnekin tähän tietorakenteeseen.

Kun hakuavain \(k2\) ja siihen liittyvä tietue on tarkoitus tallentaa, luodaan kokonaan uusi tyhjä hajautustaulu, johon tallennetaan vain hakuavain \(k2\). Hakuavain \(k1\) pysyy tallennettuna vanhaan hajautustauluun.

Ketjutetussa hajautuksessa käytetty hajautusfunktio muuttaa toistuvasti hakuavaimen \(k2\) uudeksi arvoksi, kunnes se löytää tyhjän ämpärin. Sitten se tallentaa uuden hakuavaimen \(k2\) ja sen tietueen ja palauttaa uuden \(k2\) käyttäjälle.

Koska ämpäri, johon \(k2\) osoittaa ei ole tyhjä, hajautustaulusta etsitään tyhjää ämpäriä, johon voidaan tallentaa \(k2\).

Kysymys 3

Jokaiseen ämpäriin on liitetty tietorakenne, yleensä linkitetty lista. Hakuavaimet \(k1\) ja \(k2\) ja niihin liittyvät tietueet tallennetaan molemmat jonnekin tähän tietorakenteeseen.

Suljetussa hajautuksessa käytetty hajautusfunktio muuttaa toistuvasti hakuavaimen \(k2\) uudeksi arvoksi, kunnes se löytää tyhjän ämpärin. Sitten se tallentaa uuden hakuavaimen \(k2\) ja sen tietueen ja palauttaa uuden \(k2\) käyttäjälle.

Koska ämpäri, johon \(k2\) osoittaa ei ole tyhjä, hajautustaulusta etsitään tyhjää ämpäriä, johon voidaan tallentaa \(k2\).

Kysymys 4

Mitkä seuraavista ovat hyvän hajautusfunktion ominaisuuksia? (Enemmän kuin 1 ominaisuus voi olla oikea.)

Se jakaa hakuavaimet tasaisesti kaikkien ämpäreiden kesken.

Se tarjoaa täsmälleen kaksi erilaista ämpäriehdokasta kullekin hakuavaimelle.

Se käyttää kaikkia hakuavaimessa annettuja tietoja.

Se osoittaa aina kaikki samanpituiset hakuavaimet samaan ämpäriin.

Sen käyttö johtaa aina siihen, että vähintään yksi ämpäri on tyhjä.

Se voidaan laskea nopeasti, joten sen laskenta pitäisi olla vakioaikainen (\(O(1)\)).

Kysymys 5

Oletetaan, että käytetään STL:n std:unordered_map-säiliötä. Missä seuraavista tilanteista on muodostettava oma hajautusfunktio?

Kun hakuavaimet, joita käytetään, ovat kaikki std:string -tyyppiä.

Kun ämpäreiden lukumäärä on pariton.

Kun käytettävät hakuavaimet ovat kaikki jotain struct-tyyppiä, jonka käyttäjä on itse määritellyt.

Kun ollaan varma, että uudelleenhajautus on tehtävä jossain vaiheessa.

Kysymys 6

Uudelleenhajautus on välttämätöntä, kun …

vähintään puolet ämpäreistä on tyhjiä

täyttöaste on suurempi kuin jokin hyväksyttävä yläraja

hakuavaiten koot kasvavat liian suuriksi

ainakin yksi ämpäri alkaa vuotaa

Kysymys 7

Oletetaan, että käytetään hajautustaulua, jossa on ketjutettu hajautus. Mikä on tällaisen hajautustaulun täyttöaste?

tallennettujen alkioiden lukumäärä jaettuna käytettävissä olevien ämpäreiden kokonaismäärällä

käytettävissä olevien ämpäreiden kokonaismäärä jaettuna tallennettujen alkioiden lukumäärällä

suurin lukumäärä alkioita , jotka on tallennettu yhteen ämpäriin

tyhjien ämpäreiden lukumäärä jaettuna käytettävissä olevien ämpäreiden kokonaismäärällä

Kysymys 8

Oletetaan, että käytetään hajautustaulua, jossa on ketjutettu hajautus. Oletetaan, että halutaan etsiä hakuavainta \(k\) hajautustaulusta. Mikä on suoritusaajan tehokkuuden kannalta pahin mahdollinen tilanne tälle etsimistoiminnolle?

Ämpäri, johon hajautusfunktio osoittaa hakuavaimen \(k\), on tyhjä.

Kaikki hajautustaulussa tällä hetkellä tallennetut hakuavaimet ovat osoitettu samaan ämpäriin ja hajautusfunktio osoittaa myös hakuavaimen \(k\) tähän samaan ämpäriin.

On käytävä kaikkien hajautustaulun ämpäreiden läpi, jotta löydetään, mihin ämpäriin hajautusfunktio on tallennettu.

Hajautustauluun ei ole tällä hetkellä tallennettu yhtään hakuavaimia, joten on käytävä kaikkien ämpäreiden läpi, jotta voidaan varmistaa, että ne ovat kaikki tyhjiä.

Kysymys 9

Oletetaan, että käytetään hajautustaulua, jossa on ketjutettu hajautus ja hajautusfunktio jakaa hakuavaimet hyvin tasaisesti kaikkien ämpäreiden kesken. Kun määritellään, milloin uudelleenhajautus tehdään, on asetettava täyttöasteelle yläraja. Tämän ylärajan arvo on kompromissi, minkä kahden asian välillä?

kuinka usein uudelleenhajautus on tehtävä ja hajautusfunktion tehokkuus

yhden hakuoperaation suorittamiseen keskimäärin kuluva aika ja yhden poisto-operaation suorittamiseen keskimäärin kuluva aika

ämpäreihin tarvittavan muistin kokonaismäärä ja yhden haku- tai poisto-operaation suorittamiseen keskimäärin kuluva aika

kuinka paljon uutta muistia tarvitaan uudelleenhajautuksessa ja kuinka usein uudelleenhajautus on tehtävä

Kysymys 10

Mikä seuraavista väittämistä on tarkin hajautustaulun yhden hakuoperaation tehokkuuden suhteen?

Kun hajautusfunktio jakaa hyvin tasaisesti hakuavaimet ämpäreiden kesken, hakuoperaation iso-O tehokkuus on vakioaikainen.

Riippumatta siitä, kuinka hyvin hajautusfunktio jakaa hakuavaimet ämpäreiden kesken, hakuoperaation iso-O tehokkuus on vakioaikainen.

Kun hajautusfunktio jakaa hyvin tasaisesti hakuavaimet ämpäreiden kesken, hakuoperaation amortisoitu iso-O tehokkuus on vakioaikainen.

Riippumatta siitä, kuinka hyvin hajautusfunktio jakaa hakuavaimet ämpäreiden kesken, hakuoperaation iso-O tehokkuus on lineaarinen ämpäreiden lukumäärän suhteen.

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?

Miten hajautustaulu toimii

Hajautusfunktio

Ketjutettu ja suljettu hajautus

Uudelleenhajautus

Kysymys 3

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

Lisäinformaatiota aiheesta:

Viikko12 - Sanasto

Kurssiaiheiden palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

Kurssiaihe 13¶

Itseopiskelu¶

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

Aiheiden opetusvideot ja kalvot:

Binäärihakupuut¶

video: Binäärihakupuut

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

video: Binäärihakupuiden tehokkuus

Esimerkkejä binäärihakupuista¶

video: Esimerkkejä binäärihakupuista

kaikkien videoiden 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

Kurssiaiheiden palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

Kurssiaihe 14¶

Tämän viikon ainoa video on blooper-kokoelma.

Blooper-kokoelma (enimmäkseen suomeksi)¶

Video

Lisäinformaatiota aiheesta:

MITin algoritmien johdanto kurssi

Kurssiaiheiden palautettavat kotitehtävät¶

Ei ole enää kotitehtäviä!

Kurssiaihe 12¶

Itseopiskelu¶

Hajautustaulut¶

Hajautustaulujen toteutus¶

Hajautustaulun tehokkuus ja uudelleenhajautus¶

Hajautusfunktiot¶

Hajautustaulut¶

Kurssiaiheiden palautettavat kotitehtävät¶

Kurssiaihe 13¶

Itseopiskelu¶

Binäärihakupuut¶

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

Esimerkkejä binäärihakupuista¶

Binäärihakupuut¶

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

Kurssiaiheiden palautettavat kotitehtävät¶

Kurssiaihe 14¶

Blooper-kokoelma (enimmäkseen suomeksi)¶

Kurssiaiheiden palautettavat kotitehtävät¶