Oppgave 1

    public void remove()
    {
      if (q == null) throw new IllegalStateException("Fjerning er ulovlig!");

      if (iteratorendringer != endringer)
                 throw new ConcurrentModificationException("Treet er endret!");

      if (q.høyre == null)                     // Tilfelle 1)
      {
        if (p == null)                         // Tilfelle 1a)
        {
          if (q == rot)                        // q er lik roten
          {
            rot = q.venstre;                   // q fjernes
          }
          else
          {
            Node<T> f = rot;                   // starter i roten
            while (f.høyre != q) f = f.høyre;  // går mot høyre
            f.høyre = q.venstre;               // q fjernes
          }
        }
        else // p != null                      // Tilfelle 1b)
        {
          if (q == p.venstre)                  // p.venstre har ikke høyre subtre
          {
            p.venstre = q.venstre;             // q fjernes
          }
          else
          {
            Node<T> f = p.venstre;             // starter i p.venstre
            while (f.høyre != q) f = f.høyre;  // går mot høyre
            f.høyre = q.venstre;               // q fjernes
          }
        }
      }
      else // q.høyre != null                  Tilfelle 2)
      {
        q.verdi = p.verdi;                     // kopierer

        if (q.høyre == p)                      // q.høyre har ikke venstre barn
        {
          q.høyre = p.høyre;                   // fjerner p
        }
        else                                   // q.høyre har venstre barn
        {
          Node<T> f = s.taUt();                // forelder f til p ligger på stakken
          f.venstre = p.høyre;                 // fjerner p
          while (f != q.høyre) f = s.taUt();   // fjerner fra stakken
        }

        p = q;                                 // setter p tilbake til q
      }

      q = null;                // q settes til null
      iteratorendringer++;     // en endring i treet via iteratoren
      endringer++;             // en endring i treet
      antall--;                // en verdi mindre i treet

    } // remove()

Oppgave 2

  int[] a = Tabell.randPerm(20);
  SBinTre<Integer> tre = SBinTre.sbintre();       // oppretter et tomt tre

  for (int k : a) tre.leggInn(k);                 // bygger treet
  System.out.println(tre);                        // skriver ut treet

  for (Iterator<Integer> i = tre.iterator(); i.hasNext(); )
  {
    if (i.next() % 2 == 0) i.remove();
  }

  System.out.println(tre);

  // Utskrift:
  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
  // [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

Oppgave 3

  int[] a = {4,8,3,1,7,4,9,1,6,10,2,1,5,10,7,8};  // tabell med duplikater

  SBinTre<Integer> tre = SBinTre.sbintre();       // oppretter et tomt tre
  for (int k : a) tre.leggInn(k);                 // bygger treet

  System.out.println(tre);                        // skriver ut treet

  Liste<Integer> liste = new TabellListe<>();     // en tom liste

  Iterator<Integer> i = tre.iterator();           // en iterator
  int verdi = i.next();                           // første verdi

  while (i.hasNext())                             // traverserer
  {
    int nesteverdi = i.next();                    // neste verdi
    if (verdi == nesteverdi)
      liste.leggInn(nesteverdi);                  // et duplikat
    verdi = nesteverdi;                           // oppdaterer
  }

  for (int k : liste) tre.fjern(k);               // fjerner duplikatene

  System.out.println(tre);

Oppgave 4

Oppgave 5

Oppgave 6

    public void remove()
    {
      if (q == null) throw new IllegalStateException("Fjerning er ulovlig!");

      if (iteratorendringer != endringer)
                 throw new ConcurrentModificationException("Treet er endret!");

      if (q.venstre == null)
      {
        if (p == null)
        {
          if (q == rot)
          {
            rot = q.høyre;
          }
          else
          {
            Node<T> f = rot;
            while (f.venstre != q) f = f.venstre;
            f.venstre = q.høyre;
          }
        }
        else // p != null
        {
          if (p.høyre == q)
          {
            p.høyre = q.høyre;
          }
          else
          {
            Node<T> f = p.høyre;
            while (f.venstre != q) f = f.venstre;
            f.venstre = q.høyre;
          }
        }
      }
      else // q.venstre != null
      {
        if (p == q.venstre)
        {
          q.verdi = p.verdi;
          q.venstre = p.venstre;
          p = q;
        }
        else if (comp.compare(p.verdi,s.kikk().verdi) != 0)
        {
          q.verdi = p.verdi;
          Node<T> f = s.taUt();
          f.høyre = p.venstre;
          while (f != q.venstre) f = s.taUt();
          p = q;
        }
        else if (q.høyre != null)
        {
          Node<T> s = q.høyre;

          if (s.venstre == null)
          {
            q.høyre = s.høyre;
          }
          else
          {
            Node<T> r = s;
            s = s.venstre;
            while (s.venstre != null)
            {
              r = s; s = s.venstre;
            }
            q.verdi = s.verdi;
            r.venstre = s.høyre;
          }
        }
        else if (q == rot)
        {
          rot = q.venstre;
        }
        else
        {
          Node<T> f = rot, g = null;
          while (f != q)
          {
            g = f;
            if (comp.compare(q.verdi, f.verdi) < 0) f = f.venstre;
            else f = f.høyre;
          }
          if (q == g.høyre) g.høyre = q.venstre;
          else g.venstre = q.venstre;
        }
      }

      q = null;                // q settes til null
      iteratorendringer++;     // en endring i treet via iteratoren
      endringer++;             // en endring i treet
      antall--;                // en verdi mindre i treet

    } // remove