import java.util.Comparator;
public class SBinTre<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);
}
}
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 static <T extends Comparable<? super T>> SBinTre<T> naturligOrdenTre()
{
return new SBinTre<>(Comparator.naturalOrder());
}
public static <T> SBinTre<T> komparatorTre(Comparator<? super T> c)
{
return new SBinTre<>(c);
}
public static <T> SBinTre<T> komparatorTre(T[] a, Comparator<? super T> c)
{
SBinTre<T> tre = new SBinTre<>(c);
for (T verdi : a) tre.leggInn(verdi);
return tre;
}
public static <T extends Comparable<? super T>> SBinTre<T> naturligOrdenTre(T[] a)
{
return komparatorTre(a, Comparator.naturalOrder());
}
public int antall()
{
return antall;
}
public boolean tom()
{
return antall == 0;
}
public boolean leggInn(T verdi)
{
if (verdi == null) throw new NullPointerException("Ulovlig nullverdi!");
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++;
return true;
}
private static int høyde(Node<?> p)
{
if (p == null) return -1;
return 1 + Math.max(høyde(p.venstre), høyde(p.høyre));
}
public int høyde()
{
return høyde(rot);
}
public String toString()
{
StringBuilder s = new StringBuilder();
s.append('[');
if (!tom()) toString(rot,s);
s.append(']');
return s.toString();
}
private static <T> void toString(Node<T> p, StringBuilder s)
{
if (p.venstre != null)
{
toString(p.venstre, s);
s.append(',').append(' ');
}
s.append(p.verdi);
if (p.høyre != null)
{
s.append(',').append(' ');
toString(p.høyre, s);
}
}
}