Oppgave 1

  public T maks()               // skal returnere treets største verdi
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot;                            // starter i roten
    while (p.høyre != null) p = p.høyre;        // går mot høyre
    return p.verdi;                             // den største verdien
  }

Oppgave 2

Hvis den største verdien forekommer flere ganger, vil de ligge nederst langs den høyre kanten. Vi kan bruke en hjelpepeker q som oppdateres hver gang vi finner en ny og større verdi nedover langs høyre kant.

  public T maks()          // returnerer treets største verdi
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot, q = rot;                   // starter i roten

    while (p.høyre != null)                     // går mot høyre
    {
       p = p.høyre;
       if (comp.compare(p.verdi,q.verdi) > 0) q = p;
    }
    return q.verdi;                             // den største verdien
  } 

Oppgave 4

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

    Node<T> p = rot;
    T gulv = null;

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

      if (cmp < 0) p = p.venstre;  // gulv(verdi) ligger til venstre
      else
      {
        gulv = p.verdi;            // nodeverdien er en kandidat
        p = p.høyre;
      }
    }

    return gulv;
  }

Oppgave 5

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

    Node<T> p = rot;
    T tak = null;

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

      if (cmp < 0)
      {
        tak = p.verdi;
        p = p.venstre;
      }
      else if (cmp > 0)
      {
        p = p.høyre;
      }
      else
      {
        return p.verdi;
      }
    }

    return tak;
  }

Oppgave 6

Vi kan bruke flg. idé: Hvis verdi er mindre enn eller lik en nodeverdi, så må vi lete til venstre for noden. Hvis ikke, er nodeverdien en foreløpig kandidat.

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

    Node<T> p = rot;
    T mindre = null;

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

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

    return mindre;
  } 

Oppgave 7

a) Med n = 1 har vi kun én node og den er derfor også den første i inorden. Avstanden er 0. Med n = 2 blir det to trær. I det første er avstanden lik 1 og i det andre lik 0. Dermed 1/2 som gjennomsnitt. I tilfellet n = 3 er det 6 trær. Se Figur 5.2.4 c). Vi ser at avstanden til den første i inorden er henholdsvis 0, 0, 1, 1, 1 og 2. Det gir 5/6 = 1/2 + 1/3 som gjennomsnitt. I tilfellet n = 4 er det 24 trær. Se fasiten til Oppgave 2 i Avsnitt 5.2.4. Der blir avstandene 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 2 og 3. Det gir 26/24 = 1/2 + 1/3 + 1/4 som gjennomsnitt.

b) I Avsnitt 1.1.6 så vi på flg. problemstilling: Gitt n forskjellige verdier i rekkefølge. Hvor mange av dem (fra og med den andre verdien) vil da være større enn den største av de foran. Vi fant at det i gjennomsnitt ville være H(n) − 1 der H(n) er det n-te harmoniske tallet (dvs. summen av de inverse heltallene fra 1 til n). Vi får selvfølgelig samme formel for det omvendte problemet. Dvs. hvor mange av dem vil være mindre enn den minste foran.

Vi bygger opp et binært søketre ved å legge inn en og en av n forskjellige verdier. Den første verdien blir rotnodeverdi. Den første deretter som er mindre enn den, vil bli venstre barn p til rotnoden. Den første deretter som er mindre enn den, vil da bli venstre barn til p, osv. Dermed vil lengden på venstre ryggrad (avstanden ned til den første i inorden) bli:

    H_n − 1 = 1/2 + 1/3 + 1/4 + . . . + 1/n   ≈   log(n) – 0,423   ≈   0,693·log₂(n) - 0,423

I Avsnitt 5.2.4 fant vi at den gjennomsnittlige nodedybden i et binært søketre er gitt ved:

    2(1 + 1/n)H_n − 4

Halvparten av det blir (1 + 1/n)H_n − 2 = H_n − 1 + (1/n)H_n − 1. Hvis n er stor, blir med andre ord gjennomsnittlig nodedybde for den første i inorden 1 mer enn halvparten av den gjennomsnittlige nodedybden. Hvis f.eks. n = 1000 vil gjennomsnittsdybden til den første i inorden være 6,5 og gjennomsnittlig nodedybde lik 11.