package hjelpeklasser;
import java.util.Comparator;
import java.util.Iterator;
public class SBinTre<T> implements Iterable<T>
{
private static final class Node<T>
{
private T verdi;
private Node<T> venstre, høyre;
private Node(T verdi, Node<T> v, Node<T> h)
{
this.verdi = verdi;
venstre = v; høyre = h;
}
private Node(T verdi)
{
this(verdi, null, null);
}
@Override
public String toString(){ return "" + verdi;}
}
private Node<T> rot;
private int antall;
private final Comparator<? super T> comp;
public SBinTre(Comparator<? super T> c)
{
rot = null;
antall = 0;
comp = c;
}
public int antall()
{
return antall;
}
public boolean tom()
{
return antall == 0;
}
public void leggInn(T verdi)
{
Node<T> p = rot, q = null;
int cmp = 0;
while (p != null)
{
q = p;
cmp = comp.compare(verdi,p.verdi);
p = cmp < 0 ? p.venstre : p.høyre;
}
p = new Node<>(verdi);
if (q == null) rot = p;
else if (cmp < 0) q.venstre = p;
else q.høyre = p;
antall++;
}
public boolean inneholder(T verdi)
{
Node<T> p = rot;
while (p != null)
{
int cmp = comp.compare(verdi,p.verdi);
if (cmp < 0) p = p.venstre;
else if (cmp > 0) p = p.høyre;
else return true;
}
return false;
}
public Liste<T> intervallsøk(T fraverdi, T tilverdi)
{
Stakk<Node<T>> s = new TabellStakk<>();
s.leggInn(null);
Node<T> p = rot;
while (p != null)
{
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();
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 p = s.taUt();
}
return liste;
}
public boolean fjern(T verdi)
{
Node<T> p = rot, q = null;
while (p != null)
{
int cmp = comp.compare(verdi,p.verdi);
if (cmp < 0) { q = p; p = p.venstre; }
else if (cmp > 0) { q = p; p = p.høyre; }
else break;
}
if (p == null) return false;
if (p.venstre == null || p.høyre == null)
{
Node<T> b = p.venstre != null ? p.venstre : p.høyre;
if (p == rot) rot = b;
else if (p == q.venstre) q.venstre = b;
else q.høyre = b;
}
else
{
Node<T> s = p, r = p.høyre;
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;
}
antall--;
return true;
}
private class InordenIterator implements Iterator<T>
{
private Stakk<Node<T>> s = new TabellStakk<>();
private Node<T> p = null;
private Node<T> først(Node<T> q)
{
while (q.venstre != null)
{
s.leggInn(q);
q = q.venstre;
}
return q;
}
public InordenIterator()
{
if (rot == null) return;
s.leggInn(null);
p = først(rot);
}
@Override
public T next()
{
T verdi = p.verdi;
if (p.høyre != null) p = først(p.høyre);
else p = s.taUt();
return verdi;
}
@Override
public boolean hasNext()
{
return p != null;
}
}
@Override
public Iterator<T> iterator()
{
return new InordenIterator();
}
}