Oppgave 1A

  public Mengde(int[] b, int n)
  {
    if (n < 0 || n > b.length)
    {
      throw new IllegalArgumentException("n er utenfor tabellen!");
    }

    for (int i = 1; i < n; i++)  // usortert? duplikater?
    {
      if (b[i-1] >= b[i])
      {
        String melding = b[i-1] > b[i] ? "Usortert!" : "Duplikat!";
        throw new IllegalArgumentException(melding);
      }
    }

    // henter de n første verdiene i b
    a = Arrays.copyOf(b, n);    // en metode fra klassen Arrays
  }

  public String toString()
  {
    return Arrays.toString(a);  // en metode fra klassen Arrays
  }

Oppgave 1B

  public boolean equals(Mengde B)
  {
    if (this == B) return true;
    return Arrays.equals(a, B.a);  // en metode fra klassen Arrays 
  }

  public Mengde snitt(Mengde B)
  {
    int[] b = B.a;
    int[] c = new int[Math.min(a.length, b.length)];  // hjelpetabell

    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)
    {
      if (a[i] < b[j]) i++;      // hopper over a[i]
      else if (a[i] == b[j])
      {
        c[k++] = a[i++];         // a[i] == b[j], tar med a[i]
        j++;                     // hopper over b[j]
      }
      else  j++;                 // hopper over b[j]
    }

    return new Mengde(c,k);      // bruker konstruktøren
  }

Oppgave 2A

Oppgave 2B

Utskriften blir:

0 4 D
1 3 C

Det er D som ligger på toppen av stakken og den tas ut først. Så tas C ut. Men der stopper det. Husk at antallet på stakken reduseres med en for hvert uttak. Det betyr at metoden antall() returnerer 4 første gang, så 3 og så 2. Men indeksen i øker med en om gangen. Det betyr at løkken stopper siden det ikke er sant at 2 < 2.

Oppgave 3A

Det som er lurt å gjøre her er først å legge inn tallene fra 1 til 15 i treet i inorden. Dvs. slik:

Deretter gjelder det å velge en rekkefølge på tallene slik at en forelderverdi legges inn før verdiene i barna. Det er mange muligheter. F.eks. kan vi sette opp tallene i nivåorden: 8, 2, 11, 1, 4, 9, 15, 3, 6, 10, 13, 5, 7, 12, 14. Setter vi inn i denne rekkefølgen i et på forhånd tomt tre, får vi et tre med samme form som det i oppgaven. Men som sagt er det mange andre rekkefølger som gir det samme treet.

I del to skulle det ved siden av hver node settes opp det antallet noder som det er i nodens venstre subtre. Det gir flg. figur:

Oppgave 3B

  public T minst()
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot;
    while (p.venstre != null) p = p.venstre;
    return p.verdi;
  }

Oppgave 3C

Når vi i letingen etter rett plass går til venstre i en node p, betyr det at p vil få en ekstra node i sitt venstre subtre. Når vi går høyre, blir det ingen endring:

    while (p != null)
    {
      q = p;
      cmp = comp.compare(verdi,p.verdi);

      if (cmp < 0)
      {
        p.vAntall++;
        p = p.venstre;
      }
      else
      {
        p = p.høyre;
      }
    }

En enkel (men i gjenomsnitt ineffektiv) måte å lage hent-metoden på er å traversere treet i inorden og stoppe når en har kommet til noden med oppgitt indeks:

  public T hent(int indeks)
  {
    if (indeks < 0 || indeks >= antall)
      throw new NoSuchElementException("Indeks er utenfor treet!");

    Liste<T> liste = new TabellListe<>();
    traverser(rot, indeks, liste);
    return liste.hent(indeks);
  }

  public void traverser(Node<T> p, int indeks, Liste<T> liste)
  {
    if (liste.antall() <= indeks)
    {
      if (p.venstre != null) traverser(p.venstre, indeks, liste);
      liste.leggInn(p.verdi);
      if (p.høyre != null) traverser(p.høyre, indeks, liste);
    }
  }

Den rekursive teknikken over vil i gjennomsnitt bli av orden n der n er antall noder i treet. Det kommer av at vi må gå gjennom treet i inorden inntil vi kommer til noden vi søker etter. I gjennomsnitt må vi gjennom halve treet. Det verste tilfellet er at vi skal finne den siste i inorden. Da må vi gå gjennom hele treet. Det beste tilfellet får vi hvis indeks er 0. Da blir den av logaritmisk orden.

Den optimale måten er å utnytte verdien til variabelen vAntall i nodene. La rotnoden ha et vAntall på k. Alle de k nodene i venstre subtre kommer foran rotnoden i inorden. Dermed har rotnoden indeks k i inorden siden indekseringen starter med 0. Med andre ord hvis indeks er mindre enn k, må vi lete videre i venstre subtre etter noden. Hvis derimot indeks er større enn k, må vi gå til høyre og redusere indeks med k + 1 siden det er så mange verdier som kommer foran det høyre subtreet i inorden. Dermed får vi flg. metode som er av logaritmisk orden i gjennomsnitt:

  public T hent(int indeks)
  {
    if (indeks < 0 || indeks >= antall)
      throw new NoSuchElementException("Indeks er utenfor treet!");

    Node<T> p = rot;

    while (true)
    if (indeks < p.vAntall) p = p.venstre;
    else if (indeks == p.vAntall) return p.verdi;
    else
    {
      indeks -= (p.vAntall + 1);
      p = p.høyre;
    }
  }

Oppgave 3D

Det står i oppgaveteksten at «resultatet fra et punkt som du ikke har løst, kan brukes senere i en oppgave som om det var løst». Det betyr at det er mulig å bruke metoden hent. Hvis en bruker den til fortløpende å hente verdiene som har indeks 0, indeks 1, indeks 2, osv. vil en få treets verdier i inorden. Problemet er imidlertid at dette blir helt unødvendig ineffektivt. I beste fall er hent-metoden logaritmisk. Det betyr at fortløpende bruk av den vil gi en metode som i gjennomsnitt er loglineær (av orden n log(n)). Men i verste fall blir det en kvadratisk metode. Hvis en bruker denne ideen og gjør det på en korrekt måte, vil en få noe for det, men et stykke unna fullt hus. Koden kan lages slik:

  public String toString()
  {
    StringBuilder s = new StringBuilder();
    s.append('[');

    // her må en passe på ikke å få en ',' og en ' ' for mye
    if (!tom()) s.append(hent(0));

    for (int i = 1; i < antall; i++)
      s.append(',').append(' ').append(hent(i));

    s.append(']');

    return s.toString();
  }

Den mest effektive måten er å traverserer treet i inorden (iterativt eller rekursivt) og legge verdiene f.eks. i en liste. Deretter bruker vi listens toString-metode. Dette gir en metode som er av orden n både i gjennomsnitt og i det verste tilfellet. En rekursiv traversering kan lages slik:

  private static <T> void toString(Node<T> p, Liste<T> liste)
  {
    if (p.venstre != null) toString(p.venstre, liste);
    liste.leggInn(p.verdi);
    if (p.høyre != null) toString(p.høyre, liste);
  }

  public String toString()
  {
    Liste<T> liste = new TabellListe<>();
    if (!tom()) toString(rot, liste);
    return liste.toString();
  } 

Hvis en ikke vil gå veien om en liste, kan en isteden bruke en StringBuilder direkte. Dvs. slik:

  private static <T> void toString(Node<T> p, StringBuilder s)
  {
    if (p.venstre != null)
    {
      toString(p.venstre, s);
      s.append(',').append(' ');
    }

    s.append(p.verdi);

    if (p.høyre != null)
    {
      s.append(',').append(' ');
      toString(p.høyre, s);
    }
  }

  public String toString()
  {
    StringBuilder s = new StringBuilder();
    s.append('[');
    if (!tom()) toString(rot, s);
    s.append(']');
    return s.toString();
  }

Oppgave 4A

Indeks v starter i venstre ende og indeks h i høyre ende av tabellen c. Så byttes fortløpende verdiene i c[v] og c[h] inntil v og h møtes på midten. Legg merke til at utskriftssetningen i oppgaveteksten var satt opp slik:

 System.out.println(Arrays.toString(c));

Her brukes metoden toString fra klassen Arrays. Den lager en tegnstreng som inneholder verdiene i tabellen «rammet inn» med [ og ] og med komma og mellomrom mellom hver verdi. Utskriften blir derfor:

[S, T, O, R, A, R, T, E, T]

Oppgave 4B

6 er lagt inn	10 er lagt inn

Den minste verdien er fjernet