Tietorakenteet / 1. kurssikoe 11.3.2002

Tehtävä 3.

Ratkaisuehdotuksia.

(Alla aikavaatimuksissa n tarkoittaa puussa olevien sukulaisten lukumäärää.)

a)

i) syvyyssuuntainen haku

   Tässä tulee ongelmia siitä, että haluttaisiin välittää kahta arvoa
   puussa lehdistä juureen päin: nimeä ja etäisyyttä juuresta, eivätkä
   Javan metodit voi palauttaa kuin yhden arvon.

   Yleistä: puussa alaspäin mentäessä EI voida tietää, kumpi haara
   pitäisi valita (erityisesti syntymävuosia ei voi käyttää hyväksi
   ollenkaan). Koko puu pitää siis käydä läpi.

   1) Lasketaan ensin kaukaisimman esivanhemman etäisyys ja sitten
      käydään etsimässä tällä etäisyydellä oleva sukulainen.
      Aikavaatimus Theta(n) (puu käydään pahimmassa tapauksessa kaksi
      kertaa läpi).

    public String kaukaisinEsivanhempi() {
        if (juuri != null) {
            return nimiSyvyydeltä(juuri, kaukaisin(juuri, -1));
        }
        return null;
    }

    private int kaukaisin(Sukulainen s, int syvyys) {
        if (s == null) {
            return syvyys;
        } else {
            int ä = kaukaisin(s.äiti, syvyys + 1);
            int i = kaukaisin(s.isä, syvyys + 1);
            return ä > i ? ä : i;
        }
    }

    private String nimiSyvyydeltä(Sukulainen s, int syvyys) {
        if (s == null) {
            return null;
        } else if (syvyys == 0) {
            return s.nimi;
        } else {
            String ä = nimiSyvyydeltä(s.äiti, syvyys - 1);
            if (ä != null) {
                return ä;
            } else {
                return nimiSyvyydeltä(s.isä, syvyys - 1);
            }
        }
    }

   2) Pidetään kirjaa kaukaisimmasta esivanhemmasta ja etäisyydestä
      puun läpikäynnin aikana. Aikavaatimus Theta(n).

    private String kaukaisinNimi;
    private int kaukaisin;

    public String kaukaisinEsivanhempi() {
        if (juuri != null) {
            kaukaisin = 0;
            kaukaisinNimi = juuri.nimi;
            kaukaisinEsivanhempi(juuri, 0);
            return kaukaisinNimi;
        }
        return null;
    }

    private void kaukaisinEsivanhempi(Sukulainen s, int syvyys) {
        if (s != null) {
            if (syvyys > kaukaisin) {
                kaukaisin = syvyys;
                kaukaisinNimi = s.nimi;
            }
            kaukaisinEsivanhempi(s.äiti, syvyys + 1);
            kaukaisinEsivanhempi(s.isä, syvyys + 1);
        }
    }

    3) Käytetään apuolioita tai Vectoria kahden arvon palauttamiseen.

ii) leveyssuuntainen haku

    Ideana on käydä sukupuu läpi tasojärjestyksessä. Sukulainen, joka
    tulee viimeiseksi jonosta on (jokin) kaukaisin esivanhempi.
    Aikavaatimus Theta(n), mikäli jono-operaatiot ovat vakioaikaisia.
    (Tilavaatimus: jonossa on pahimmassa tapauksessa noin puolet
    sukulaisista.)

    public String kaukaisinEsivanhempi() {
        if (juuri != null) {
            Sukulainen s = juuri;
            Jono q = new Jono();
            q.toQueue(juuri);

            while (!q.isEmpty()) {
                s = (Sukulainen) q.fromQueue();
                if (s.äiti != null) {
                    q.toQueue(s.äiti);
                }
                if (s.isä != null) {
                    q.toQueue(s.isä);
                }
            }
            return s.nimi;
        }
        return null;
    }

b)

   Jokaisen sukulaisen kohdalla katsotaan, löytyykö äidin tai isän
   puolelta samanniminen sukulainen. Aikavaatimus: Theta(n log n), jos
   puu on tasapainoinen; Theta(n^2), jos puu on vino. Näistä
   jälkimmäinen on tietysti varsinainen pahimman tapauksen
   aikavaatimus, koska puun ei voi olettaa olevan tasapainoinen.

    public void tulostaPerinteisenNimenSaaneet() {
        tulostaPerinteisenNimenSaaneet(juuri);
    }

    private void tulostaPerinteisenNimenSaaneet(Sukulainen s) {
        if (s != null) {
            if (samanniminen(s.äiti, s.nimi) || samanniminen(s.isä, s.nimi)) {
                System.out.println(s.nimi + " " + s.syntymävuosi);
            }
            tulostaPerinteisenNimenSaaneet(s.äiti);
            tulostaPerinteisenNimenSaaneet(s.isä);
        }
    }

    private boolean samanniminen(Sukulainen s, String nimi) {
        if (s == null) {
            return false;
        } else if (nimi.equals(s.nimi)) {
            return true;
        } else {
            return samanniminen(s.äiti, nimi) || samanniminen(s.isä, nimi);
        }
    }


Arvostelusta.

Ratkaisuksi on hyväksytty minkälainen tahansa algoritmi, joka tuottaa
oikean tuloksen. Jos ratkaisussa on käytetty apurakenteita (pino,
jono, jne.), myös niiden toteutus on vaadittu esitettäväksi (paitsi
ykköstehtävän rakenteen).  Aikavaatimuksen arvioissa on hyväksytty
oletus puun tasapainoisuudesta. Aikavaatimusarvion on kuitenkin
vaadittu olevan "täsmälleen" oikea, ts. esim. O(2^n) ei kelpaa, jos
algoritmin aikavaatimus on (myös) luokkaa O(n^2).

a) metodi 3 pistettä, aikavaatimus 1 piste

b) metodi 3 pistettä, aikavaatimus 1 piste


Ratkaisuista.

Tehtävässä ei määritelty, mitä metodien pitää tehdä, jos ratkaisua ei
ole (puu on tyhjä tai kenelläkään ei ole perinteistä nimeä). Tällöin
voi periaatteessa itse päättää mitä tapahtuu. Luontevinta on
esivanhemman kohdalla palauttaa null (eikä mitään merkkijonoa "ei
esivanhempia" tms.) ja perinteisen nimen kohdalla olla tulostamatta
mitään. Tällöin tuloksesta käy suoraan ilmi, että vastausta ei ole,
eikä tarvitse arvailla, onko sukupuussa joku jonka nimi sattuu olemaan
"ei esivanhempia".

Monissa metodeissa ei oltu varauduttu siihen, että puu on tyhjä (juuri
== null). Tämä on erityisen yllättävää, koska tehtäväpaperin
konstruktorissa nimenomaan asetettiin juuri = null.