Oppgave 1 og 2

Oppgave 3

  public int fjernAlle(T verdi)
  {
    int verdiAntall = 0;
    while (fjern(verdi)) verdiAntall++;
    return verdiAntall;
  }

Oppgave 4

Hvis to noder p og q med samme verdi skulle ligge i forskjellige grener, må de ha en nærmeste felles forfeder f. Anta at p ligger i det venstre subtreet til f. Da må q ligge i det høyre subtreet. Det betyr at verdien i p er mindre enn verdien i f som igjen er mindre enn eller lik verdien i q. Men det er umulig siden p og q har like verdier.

La p være noden som inneholder første (i inorden) forekomst av en verdi. Anta at det er flere forekomster av verdien. La q være en av dem. Da må q ligge i det høyre subtreet til p. Hvis q har et venstre barn r, må verdien i r være mindre enn verdien i q. Men siden r ligger i det høyre subtreet til p, må verdien til p være mindre enn eller lik verdien til r. Men det er umulig sidene p og q har samme verdi.

  public int fjernAlle(T verdi)
  {
    if (verdi == null) throw new
      IllegalArgumentException("verdi er null!");

    Node<T> p = rot;   // hjelpepeker
    Node<T> q = null;  // forelder til p
    Node<T> r = null;  // neste i inorden mhp. verdi
    Node<T> s = null;  // forelder til r

    Stakk<Node<T>> stakk = new TabellStakk<>();

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

      if (cmp < 0) // skal til venstre
      {
        s = r;
        r = q = p;
        p = p.venstre;
      }
      else
      {
        if (cmp == 0)  // verdi ligger i p
        {
          stakk.leggInn(q);  // legger inn forelder til p
          stakk.leggInn(p);  // legger inn p
        }
        // skal videre til høyre
        q = p;
        p = p.høyre;
      }
    }

    // det er lagt inn to noder for hvert treff
    int verdiAntall = stakk.antall()/2;

    if (verdiAntall == 0) return 0;

    while (stakk.antall() > 2)
    {
      p = stakk.taUt();  // p har ikke venstre barn
      q = stakk.taUt();  // forelder til p

      if (p == q.venstre) q.venstre = p.høyre;
      else q.høyre = p.høyre;
    }

    // Har nå fjernet alle duplikatene, 
    // men har igjen første forekomst

    p = stakk.taUt();  // p inneholder verdi
    q = stakk.taUt();  // forelder til p    

    // Tilfelle 1) og 2), dvs. p har ikke to barn
    if (p.venstre == null || p.høyre == null)
    {
      Node<T> x = p.høyre == null ? p.venstre : p.høyre;
      if (p == rot) rot = x;
      else if (p == q.venstre) q.venstre = x;
      else q.høyre = x;
    }
    else  // p har to barn
    {
      p.verdi = r.verdi;   // kopierer fra den neste i inorden
      if (r == p.høyre) p.høyre = r.høyre;
      else s.venstre = r.høyre;
    }

    antall -= verdiAntall;

    return verdiAntall;
  }

Oppgave 5

Enkel, men ikke effektiv metode (orden nlog(n)):

  public void nullstill()
  {
    while (!tom()) fjernMin();
  }

En effektiv metode. Rekursiv traversering i postorden (orden n):

  public void nullstill()
  {
    if (!tom()) nullstill(rot);  // nullstiller
    rot = null; antall = 0;      // treet er nå tomt
  }

  private void nullstill(Node<T> p)
  {
    if (p.venstre != null)
    {
      nullstill(p.venstre);      // venstre subtre
      p.venstre = null;          // nuller peker
    }
    if (p.høyre != null)
    {
      nullstill(p.høyre);        // høyre subtre
      p.høyre = null;            // nuller peker
    }
    p.verdi = null;              // nuller verdien
  }

Oppgave 6

En enkel, men noe ineffektiv metode kunne være å finne den første i inorden og så bruke den vanlig fjerningsmetoden til å fjerne den og evntuelle andre forekomster av samme verdi:

  public int fjernAlleMin()  // hører til klassen SBinTre
  {
    if (tom()) return 0;

    Node<T> p = rot;

    while (p.venstre != null) p = p.venstre;

    T minimum = p.verdi;

    int antallFjernet = 0;
    while (fjern(minimum)) antallFjernet++;
    return antallFjernet;
  }

Det er mulig å lage en mer effektiv, men mer komplisert, løsning som går nedover i treet bare en gang:

  public int fjernAlleMin()  // hører til klassen SBinTre
  {
    if (tom()) return 0;  // ingen fjernet

    int antallFjernet = 1;
    T minimum = null;
    Node<T> p = null, q = null;

    if (rot.venstre == null) // rotverdien er minst
    {
      minimum = rot.verdi;
      p = rot;

      while (p.høyre != null && minimum.equals(p.høyre.verdi))
      {
        antallFjernet++;
         p = p.høyre;
      }
      rot = p.høyre;
    }
    else
    {
      p = rot.venstre;
      q = rot;
      while (p.venstre != null)
      {
        q = p;  // q er forelder til p
        p = p.venstre;
      }
      // p er noden med minst verdi
      q.venstre = p.høyre;

      minimum = p.verdi;
    }

    // Må fjerne resten av eventuelle forekomster
    // av den minste verdien

    while (p.høyre != null)
    {
      p = p.høyre;
      while (p.venstre != null)
      {
        q = p; p = p.venstre;
      }
      if (minimum.equals(p.verdi)) q.venstre = p.høyre;
      else break;

      antallFjernet++;
    }

    antall -= antallFjernet;

    return antallFjernet;
  }

Oppgave 7

Vi kan som et første forsøk, lage metoden fjernMaks som en speilvending av fjernMin. Hvis den største verdien forekommer flere ganger, vil det da imidlertid være den siste av dem som blir fjernet:

  public void fjernMaks()  // hører til klassen SBinTre
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    if (rot.høyre == null) rot = rot.venstre;  // rotverdien er minst
    else
    {
      Node<T> p = rot.høyre, q = rot;
      while (p.høyre != null)
      {
        q = p;  // q er forelder til p
        p = p.høyre;
      }
      // p er noden med minst verdi
      q.høyre = p.venstre;
    }
    antall--;  // det er nå én node mindre i treet
  }

En enkel måte å fjerne den største verdien og hvis det er flere av dem, den første, er å finne den siste i inorden og så kalle den vanlige fjern-metoden på dens verdi. Ulempen er at vi må gå nedover i treet to ganger:

  public void fjernMaks()  // hører til klassen SBinTre
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot;
    while (p.høyre != null) p = p.høyre;
    fjern(p.verdi);
  }

Det er mulig å fjerne første forekomst av den største ved å gå kun én gang ned i treet, men da blir koden litt mer komplisert:

  public void fjernMaks()  // hører til klassen SBinTre
  {
    if (tom())
      throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot, q = null;
    while (p.høyre != null)
    {
      if (comp.compare(p.høyre.verdi, p.verdi) > 0) q = p;
      p = p.høyre;
    }

    if (q == null)
    {
      if (rot.høyre == null) rot = rot.venstre;
      else
      {
        rot.høyre.venstre = rot.venstre;
        rot = rot.høyre;
      }
    }
    else
    {
      p = q.høyre;
      if (p.høyre == null) q.høyre = p.venstre;
      else
      {
        p.høyre.venstre = p.venstre;
        q.høyre = p.høyre;
      }
    }
    antall--;
  }

Det å fjerne alle forekomstene av den største verdien er enklere å få til enn det å fjerne alle forekomstene av den minste. Det kommer av at hvis det er flere forkomster av den største verdien, ligger de på rekke nederst langs treets høyre kant. Da er det bare den første av dem som kan ha venstre barn. Oppgave går derfor ut på å finne den første av dem (og forelderen til den første):

  public int fjernAlleMaks()  // hører til klassen SBinTre
  {
    if (tom()) return 0;

    int antallFjernet = 1;

    Node<T> p = rot, q = null;
    while (p.høyre != null)
    {
      if (comp.compare(p.høyre.verdi, p.verdi) > 0)
      {
        q = p;
        antallFjernet = 1;
      }
      else antallFjernet++;

      p = p.høyre;
    }

    if (q == null) rot = rot.venstre;
    else q.høyre = q.høyre.venstre;

    antall -= antallFjernet;
    return antallFjernet;
  }

Oppgave 8

Oppgave 9

Treet er slik det var på forhånd.

Oppgave 10

Den nye versjonen av fjern-metoden krever at klassen SBinTre får en ny instansvariabel boolean nestefjerning. Den settes f.eks. til true fra starten av. Den vil da skifte verdi i metoden:

  public boolean fjern(T verdi)
  {
    Node<T> p = rot, q = null;  // q skal være forelder til p

    while (p != null)     // leter etter verdi
    {
      int cmp = comp.compare(verdi, p.verdi);    // sammenligner
      if (cmp < 0)
      {
        q = p;
        p = p.venstre;
      }
      else if (cmp > 0)
      {
        q = p;
        p = p.høyre;
      }
      else break;    // den søkte verdien ligger i p
    }
    if (p == null) return false;   // fant ikke verdi    

    if (p.venstre == null || p.høyre == null)
    {
      Node<T> b = p.høyre == null ? p.venstre : p.høyre;  // b for barn
      if (p == rot) rot = b;
      else if (p == q.venstre) q.venstre = b;
      else q.høyre = b;
    }
    else if (nestefjerning)
    {
      Node<T> r = p.høyre, s = p;
      while (r.venstre != null)
      {
        s = r;
        r = r.venstre;
      }
      p.verdi = r.verdi;
      if (s != p) s.venstre = r.høyre;
      else s.høyre = r.høyre;
      nestefjerning = false;
    }
    else  // forrigefjerning
    {
      Node<T> r = p.venstre, s = p;
      while (r.høyre != null)
      {
        s = r;
        r = r.høyre;
      }
      if (r.verdi.equals(s.verdi))
      {
        // Kan ikke sette p.verdi = r.verdi her. Det
        // vil ødelegge treet. Må bruke nestefjerning

        r = p.høyre;
        s = p;
        while (r.venstre != null)
        {
          s = r;
          r = r.venstre;
        }
        p.verdi = r.verdi;
        if (s != p) s.venstre = r.høyre;
        else s.høyre = r.høyre;
      }
      else
      {
        p.verdi = r.verdi;
        if (s != p) s.høyre = r.venstre;
        else s.venstre = r.venstre;
        nestefjerning = true;
      }
    }

    antall--;   // det er nå én node mindre i treet
    return true;
  }

Oppgave 11

Løsningsforslag mangler.