Oppgave 1

Den finner den første av dem.

Oppgave 2

  public int antall(T verdi)
  {
    Node<T> p = rot;
    int antallVerdi = 0;

    while (p != null)
    {
      int cmp = comp.compare(verdi,p.verdi);
      if (cmp < 0) p = p.venstre;
      else
      {
        if (cmp == 0) antallVerdi++;
        p = p.høyre;
      }
    }
    return antallVerdi;
  }  

Oppgave 3

  public Liste<T> intervallsøk(T fraverdi, T tilverdi)
  {
    Stakk<Node<T>> s = new TabellStakk<>();

    Node<T> p = rot;
    while (p != null)    // leter etter fraverdi
    {
      int cmp = comp.compare(fraverdi,p.verdi);
      if (cmp < 0)
      {
        s.leggInn(p); p = p.venstre;
      }
      else if (cmp > 0) p = p.høyre;
      else break;
    }

    if (p == null) p = s.taUt();  // neste i inorden

    Liste<T> liste = new TabellListe<>();

    while (p != null && comp.compare(p.verdi,tilverdi) < 0)
    {
      liste.leggInn(p.verdi);

      if (p.høyre != null)
      {
        p = p.høyre;
        while (p.venstre != null)
        {
          s.leggInn(p); p = p.venstre;
        }
      }
      else if (!s.tom()) p = s.taUt();
      else p = null;
    }

    return liste;
  }  

Oppgave 4

  public boolean inneholder(T verdi)
  {
    return inneholder(rot,verdi,comp);  // kaller den rekursive metoden
  }

  private static <T>
  boolean inneholder(Node<T> p, T verdi, Comparator<? super T> c)
  {
    if (p == null) return false;
    int cmp = c.compare(verdi,p.verdi);
    if (cmp < 0) return inneholder(p.venstre,verdi,c);
    else if (cmp > 0) return inneholder(p.høyre,verdi,c);
    else return true;
  }

Oppgave 7

  int n = 1000000;
  int[] a = Tabell.randPerm(n);

  SBinTre<Integer> tre = SBinTre.sbintre();
  for (int k : a) tre.leggInn(k);

  long tid = System.currentTimeMillis();
  for (int i = 0; i < n; i++) tre.inneholder2(a[i]);
  tid = System.currentTimeMillis() - tid;

  System.out.println(tid);