Pisteytys: a) 1 piste, b) ja c) molemmat 1 1/2 pistettä, d) 2 pistettä, yhteensä 6 pistettä. a) (Luentomonisteen määritelmä) Jos x on hakupuun solmu, niin x:n mille tahansa vasemman alipuun solmulle y pätee: key[y] <= key[x] ja solmun x mille tahansa oikean alipuun solmulle z pätee: key[x] <= key[z]. Tuon saattoi selittää omin sanoin. Yleinen väärinkäsitys (jolla sai kuitenkin puoli pistettä) oli, että solmun (tai juuren) vasemman lapsen on oltava pienempi ja oikean lapsen suurempi kuin solmu itse. Tämä ei kuitenkaan vielä tee puusta binäärihakupuuta (vaan ehdon on siis katettava koko vasen ja oikea alipuu). esim: 6 / \ 3 8 /\ 2 10 puu täyttää ehdon left[x] <= x ja right[x] >= x kaikille solmuille muttei ole binäärihakupuu. b) (Luentomonisteen algoritmit) ei-rekursiivinen versio search(x,k) while x != NIL and key[x] !=k do if k < key[x] then x <- left[x] else x <- right[x] return x aikavaativuus pahimmillaan O(n) ("listamainen" puu) ja tilavaativuus O(1). rekursiivisesti: search(x,k) if x = NIL or key[x] = k then return x if k < key[x] then return search(left[x],k) else return search(right[x],k) Aikavaatimus sama O(n) kuin edellä mutta tilavaatimus pahimmillaan O(n) (rekursiopinossa koko listapuu). Jos return-lause unohtui kahdelta viimeiseltä riviltä, väheni 1/2 pistettä (tämä virhe oli myös luentomonisteessa). Yllättävän moni väitti aikavaativuudeksi O(log n), joka pätee vain tasapainoisille binääripuille. Jos aikavaatimus oli väärin tai puuttui väheni 1/2 pistettä. Jotkut yksittäiset virheet algoritmissa (esim. and silloin kun pitäisi olla or tai vertailu- ja sijoitusoperaatiot sekaisin) vähensivät 1/2-1 pistettä jos yritys oli muuten oikeansuuntainen mutta jos koodinpätkä oli kertakaikkisen toimimaton ei pisteitä tullut. Rekursiivisen algoritmin kirjoittaminen toimivasti osoittautui hankalaksi. c) saadakseen täydet 1 1/2 pistettä piti vastauksesta ilmetä poisto-operaation kolme eri tapausta (luentomonisteen sivut 61-62): poistettavalla ei lapsia, poistettavalla 1 lapsi, poistettavalla 2 lasta ja se, miten niissä tapauksissa menetellään, lisäksi tietysti aika- ja tilavaativuus tuli olla oikein. Aikavaativuus O(h), missä h on puun korkeus, pahimmillaan siis O(n) kun n on solmujen määrä. Tilavaativuus O(1). Täydet pisteet saattoi saada tästä kohdasta vaikkei tullut huomioineeksi erikoistapauksia joissa poistettava on juuri. Väärä tai puuttuva aika/tilavaativuus vähensi taas 1/2 pistettä. Tapauksessa 1 (pistettavalla ei lapsia) ei riittänyt kuvaukseksi että solmu "vain poistetaan" vaan piti ilmaista asia vähän täsmällisemmin (esimerkiksi: muutetaan viite solmun vanhemmasta solmuun NIL:ksi). Tapauksessa 3 tuli selvästi ilmetä, että kun on löydetty poistettavan solmun seuraaja sisäjärjestyksessä, sen avain kopioidaan poistettavaan solmuun ja sitten poistetaan seuraajasolmu (tapaus 1 tai 2), ei vaihdeta itse solmuja. d) 1 piste tuli kierto-operaation selityksestä ja 1 piste algoritmista aika- ja tilavaativuuksineen. Selitys löytyy kuvineen löytyy kalvojen sivulta 70. Useimmat olettivat vastauksissa, että solmuissa on viite solmun vanhempaan (p[x]). Tällöin edellytin, että kiertoalgoritmi päivittää myös p-linkit ajan tasalle. Useimmilla jäi päivittämättä joitain viitteitä jolloin väheni 1/2 pistettä jos algoritmi oli muuten toimiva. Mitä vastauksista odotettiin (kovin moni tosin ei siihen koetilanteessa päätynyt) oli se, että algoritmi palauttaa kierretyn alipuun uuden juuren, jotta viite voidaan ottaa talteen siellä missä algoritmia mahdollisesti kutsutaan ja päivittää sitten linkit ajan tasalle. left-rotate(T,x) y <- right[x] right[x] <- left[y] left[y] <- x return y Vasemman kierron toteuttava algoritmi, jossa on käytössä p-viitteet löytyy luentokalvojen sivulta 69. Aika- ja tilavaativuus O(1) molemmilla tavoilla. Ilman p-viitettä saattoi selvitä myös niin, että etsi puun juuresta liikkeelle lähtien solmun vanhemman (vähän muokattu search-operaatio) jotta sai päivitettyä viitteen lierretyn alipuun yläpuolelle. Tälläkin vastauksella sai pisteet kotiin jos se toimi vaikka aikavaativuus ei enää ole O(1).