Algoritmien esittämisestä sanallisesti tai pseudokoodina

Jos algoritmeja esitetään vain sanallisesti, tulee kiinnittää huomiota siihen, että kuvaus on riittävän täsmällinen.

Pseudokoodiesityksen tarkoitus on tuoda esiin algoritmin olennaiset toimintaperiaatteet ilman

• syntaktisia ohjelmointikielen yksityiskohtia,
• kaikkien yksityiskohtien tarkkaa esittämistä (esim. jos jonkin abstraktion tarkka toteutus voidaan olettaa tunnetuksi ja aikavaativuus on tiedossa),
• algoritmin implementointia ohjelmaksi.

Seuraavassa on esitetty joitakin yksinkertaisia tehtäviä ja niiden ratkaisut. Viimeisessä esimerkissä pseudokoodi on sanallisella tasolla.
 
Esimerkki 1:  Esitä algoritmi, joka käy binääripuun läpi esijärjestyksessä.  Mikä on algoritmisi tehokkuus O-notaatiossa?

Selostus:  Algoritmi lähtee liikkeelle puun juuresta ja käy kaikki puun alkiot läpi seuraavassa järjestyksessä.  Ensin käsitellään  juuri, sitten vasen alipuu rekursiivisesti ja lopuksi oikea alipuu rekursiivisesti.

Analyysi: Koska kutakin solmua käsitellään vain kerran, on kokonaissuoritusaika O(N).

Pseudokoodi:

Traverse (tree t)
  if t is not a leaf node
  begin
    Visit (t)
    Traverse (t.left)
    Traverse (t.right)
  end
 

Esimerkki 2:  Esitä algoritmi, joka yhdistää kaksi AVL-puuta A ja B, joissa on M ja N avainta, yhdeksi AVL-puuksi. Mikä on algoritmisi tehokkuus O-notaatiossa?

Selostus:  Algoritmin toimintaperiaate on yksinkertainen:  Käydään läpi puu A esijärjestyksessä ja lisätään jokainen solmu yksitellen puuhun B. Solmun lisäys AVL-puuhun B on perusalgoritmi, jonka toiminta kuuluu kurssin perusaineistoon, joten sitä ei ole tässä yksityiskohtaisesti kuvattu.

Analyysi:  Puun A läpikäyntiin kuluu aikaa O(M).  Jokainen avain lisätään AVL-puuhun B, ja lisäys vie aikaa O(log N).  Kokonaisaika on tällöin O(M log N)  (tarkasti ottaen aika olisi O(M log (N + M)), koska puun B kokohan kasvaa kun siihen lisätään alkioita, mutta tätä ei vastauksessa vaadittaisi).
 
Pseudokoodi:

Traverse (tree t)
  if t is not a leaf node
  begin
    Insert t into tree B
    Traverse (t.left)
    Traverse (t.right)
  end
 

Esimerkki 3:  Oletetaan, että meillä on binääripuun juuri t ja t:llä on kaksi alipuuta A ja B, jotka molemmat ovat AVL-puita.  A:n ja B:n korkeusero voi olla mielivaltainen. Oletetaan lisäksi, että puun jokaiseen solmuun on talletettu solmun korkeus. Esitä algoritmi, joka tasapainottaa puun, niin että se on kokonaisuudessaan AVL-puu. Mikä on algoritmisi tehokkuus O-notaatiossa?

Selostus:  Oletetaan, että A:n korkeus on suurempi kuin B:n korkeus ja että A on t:n vasen alipuu.  Muut tapaukset ovat vain tämän tapauksen peilikuvia.  Tehtävä voidaan ratkaista rotaatioilla ja perusperiaate on se, että teemme rotaatioita ensin juuressa, sitten juuren oikeassa lapsessa, tämän oikeassa lapsessa, jne. niin kauan kuin ko. solmun lasten korkeusero on suurempi kuin 1.  Tasapainotekijät voidaan laskea suoraan solmujen korkeuksista.

Tapaus on kuitenkin hieman mutkikkaampi, koska A voi olla kallistunut oikealle ja silloin aloitetaan kaksoisrotaatiolla.  Vastaava tilanne voi tulla myöhemminkin eli algoritmi joutuu tutkimaan, minkä rotaation se tekee.

Rotaatio voi samalla pienentää sen alipuun korkeutta, jonka juuressa rotaatio tehdään.  Tästä seuraa, että viimeisen rotaation jälkeen jokin solmu viimeisen rotaatiokohdan yläpuolella voi olla epätasapainossa (tasapainotekijän arvo +2).  Siksi algoritmi palaa juureen edeten puun oikeanpuolimmaista haaraa tarkistaen tasapainon jokaisessa solmussa ja tekee tarvittaessa uuden rotaation ja palaa sitten ylemmäs.

Analyysi:  Algoritmi tekee 1. vaiheessa korkeintaan O(log N) rotaatiota, koska se on puun korkeus.  Paluuvaiheessa joudutaan samoin tekemään korkeintaan O(log N) rotaatiota => tehokkuus on O(log N), koska rotaatio voidaan tehdä vakioajassa.

Pseudokoodi (tämä esittää vain ko. tapauksen, jossa A:n korkeus on suurempi kuin B:n korkeus)

Balance (tree t)
begin
  if t.left.height > t.right.height + 1 then
  begin
    if node t.left has balance factor -1 then
      LR_Double_rotation (t)    ; rotaation jälkeen t osoittaa samaan
    else                        ; solmuun kuin ennen rotaatiota
      Rotate_right (t)
    Balance (t)
  end
  t.height := max(t.left.height, t.right.height) + 1
  if node t is not balanced then
    Perform appropriate rotation at t
end
 

Esimerkki 4:  Esitä algoritmit, miten radix search trie -rakenteesta haetaan avainta ja miten siihen lisätään uusi alkio.

Esimerkki on opetusmonisteesta ja siinä pseudokoodi on pelkistetymmällä sanallisella tasolla.  Tässä tapauksessa erillistä sanallista kuvausta algoritmin perusideasta ei anneta, koska se ei eroaisi riittävästi alla olevasta pseudokoodista:

Haku:

1. Aloitetaan juuresta ja eniten merkitsevästä bitistä.
2. Edetään bitti kerrallaan puussa alaspäin kääntyen vasempaan tai oikeaan haaraan, kunnes kohdataan puun lehti tai tyhjä haara.
3. Katsotaan, onko lehdessä oleva alkio sama kuin haettu alkio.
1. Jos on, palautetaan osoitin siihen.
2. Jos ei ole, haku epäonnistui.
3. Jos haku päättyy tyhjään haaraan, avainta ei ole puussa

Lisäys:

1. Etsitään alkion paikka bittien perusteella, kuten edellä hakuoperaatiossa.
1. Jos löydetty paikka oli tyhjä, lisätään alkio tähän kohtaan puun lehdeksi.
2. Jos paikassa oli lehti,
1. Lehden tilalle laitetaan puun sisäsolmu
2. Sen alle rakennetaan alipuu tai alipuut sen mukaan, että lehdessä ollut avain ja lisättävä avain eroavat toisistaan.
3. Lopuksi luodaan uudet lehtisolmut, joihin entisen lehden avain ja lisättävä avain talletetaan.