next up previous
Next: About this document Up: No Title Previous: No Title

Algoritmien teoria, kevät 1999
Harjoitus 2, 1.2. klo 10-12 sali MaD380

    1. Esitä binäärisen hakupuun päivitysalgoritmien toiminta, kun aluksi tyhjään puuhun ensin lisätään alkiot 6, 2, 7, 0, 4, 5, 9, 8, ja näin saadusta puusta sitten poistetaan alkio 2.
    2. Osoita, että n alkion lisääminen aluksi tyhjään binääriseen hakupuuhun vaatii pahimmassa tapauksessa tex2html_wrap_inline37 vertailuoperaatiota.
  1. Bonustehtävä. Osoita, että vertailujen määrän odotusarvo, kun aluksi tyhjään binääriseen hakupuuhun lisätään n satunnaista alkiota, on tex2html_wrap_inline41 . (Ohje: Olkoot lisättävät alkiot tex2html_wrap_inline43 . Puun juureen sijoittuva alkio tex2html_wrap_inline45 on todennäköisyydellä tex2html_wrap_inline47 joukon k:nneksi pienin. Tässä tapauksessa vasempaan alipuuhun sijoittuu k-1 alkiota ja oikeaan alipuuhun n-k alkiota. Muodosta tältä pohjalta vertailujen määrän odotusarvoa kuvaava rekursioyhtälö ja ratkaise se joko arvauksen sovitusmenetelmällä tai ns. historian eliminoinnilla (ks. pikalajittelualgoritmin analyysi, muistiinpanojen s. 35).)
    1. Esitä (2,3)-puun päivitysalgoritmien toiminta, kun aluksi tyhjään puuhun ensin lisätään alkiot 6, 2, 7, 0, 4, 5, 9, 8, ja näin saadusta puusta sitten poistetaan alkio 0.
    2. Osoita, että n alkion lisääminen aluksi tyhjään (2,3)-puuhun vaatii enintään tex2html_wrap_inline41 operaatiota.
    1. Esitä AVL-puun lisäysalgoritmin toiminta, kun aluksi tyhjään puuhun lisätään alkiot 6, 2, 7, 0, 4, 5, 9, 8.
    2. Suunnittele AVL-puille poistoalgoritmi ja esitä algoritmisi toiminta, kun edellisessä tehtävässä muodostetusta puusta poistetaan alkio 2.
  2. Osoita, että AVL-puussa, jonka korkeus on h, on oltava vähintään tex2html_wrap_inline61 solmua, missä tex2html_wrap_inline63 on ns.\ kultaisen leikkauksen suhde, tex2html_wrap_inline65 . (Ohje: Johda puun rakenteen perusteella rekursioyhtälö pienimmän h:n korkuisen puun solmujen määrälle ja ratkaise se.) Päättele tämän tiedon perusteella, että n-solmuisen AVL-puun korkeus on luokkaa tex2html_wrap_inline71 .
  3. Osoita, että universaalihajautusta käytettäessä minkä tahansa avaimen x kanssa törmäävien muiden avainten tex2html_wrap_inline75 määrän odotusarvo on alle 1 (vrt. Cormen/Leiserson/Rivest, Introduction to Algorithms, ss. 230-231). Päättele tästä, että hakemisto-operaatiot MEMBER, INSERT ja DELETE voidaan universaalihajautusta käyttäen toteuttaa odotusarvoisesti vakioajassa. (Huom. Odotusarvo lasketaan siis hajautinten, ei syötteenä saatavien avainkokoelmien suhteen. Kaikki avainkokoelmat ovat samassa asemassa.)


next up previous
Next: About this document Up: No Title Previous: No Title

Pekka Orponen
Mon Mar 22 15:29:18 EET 1999