public class SearchTree<T extends Comparable<T>> {

  private class Node {
    T    value;
    Node left;
    Node right;

    Node(T val) {
	    value = val;
	    left = null;
	    right = null;
    }
  }

  private Node root;
  private int size;

  public SearchTree() {
    root = null;
    size = 0;
  }

  public int size() {
    return size;
  }

  public boolean contains(T elem) {
    Node node = root;
    int  diff;

    while (node != null) {
	    diff = node.value.compareTo(elem);
	    if (diff == 0) {
	        return true;
	    }
	    else if (diff>0) {
	        node = node.left;
	    }
	    else {
	        node = node.right;
	    }
    }

    return false;
  
  }

  public void insert(T elem) {
    Node node = root;
    Node father = null;
    
    int  diff=0;
    
    while (node!=null) {
      father = node;
      diff = node.value.compareTo(elem);
      if (diff==0) {
        return;
      }
      else if (diff>0) {
        node = node.left;
      }
      else {
        node = node.right;
      }
    }

    node = new Node(elem);

    if (father==null) {
      root = node;
    }
    else if (diff>0) {
	    father.left = node;
    }
    else {
      father.right = node;
    }

    size++;
  }
  
  public void delete(T elem) {
    Node node = root;
    Node wurzel = node;
    Node father = null;
    int  diff=0;

    // suche nach zu loeschenden node
    while (node!=null) {
      father = node;  
      diff   = node.value.compareTo(elem);
      
      // node gefunden
      if (diff==0) {
        node = null;
        
        if ( father.left == null && father.right == null) {
          // Moeglichkeit a (w ist ein Blatt)
          System.out.println("a");
          diff   = father.value.compareTo(wurzel.value);

          if (diff>0) {
            wurzel.right = null;
          } else
            wurzel.left = null;
          
          size--;

        
        } else if ( father.left != null && father.right == null ) {
          // Moeglichkeit b 1 (Tl ist nicht leer, Tr ist leer)
          System.out.println("Fall: Moeglichkeit b 1 (Tl ist nicht leer, Tr ist leer)");
          diff   = wurzel.value.compareTo(father.left.value);
          
          if (diff>0) {
            wurzel.left = father.left;
          } else
            wurzel.right = father.left;
          
          size--;

        } else if ( father.left == null && father.right != null ) {
          // Moeglichkeit b 2 (Tl ist leer, Tr ist nicht leer)
          System.out.println("Fall: Moeglichkeit b 2 (Tl ist leer, Tr ist nicht leer)");
          diff   = wurzel.value.compareTo(father.right.value);
          
          if (diff>0) {
            wurzel.left = father.right;
          } else
            wurzel.right = father.right;
          
          size--;

          
        } else if ( father.left != null && father.right != null ) {
          // Moeglichkeit c (Weder Tl noch Tr ist leer)
          System.out.println("Fall: Moeglichkeit c (Weder Tl noch Tr ist leer)");
          Node maximum = null;
          Node oldFather = null;
          
          if ( father.right.left == null )
            maximum = father.right;
          else
            maximum = maximumAbKnoten(father.right.left);    
          
          father.value = maximum.value;
          
          size--;
          
        }
      }
      // wenn node nicht gefunden, merke dir die wurzel und gehe weiter im tree
      else if (diff>0) {
        wurzel = node;
        node = node.left;
      }
      else {
        wurzel = node;
        node   = node.right;
      }
    }  
  }
  
  private Node maximumAbKnoten(Node knoten) {
    Node node = knoten;
    
    while (node.right != null) {
      node = node.right;      
    }
    
    return node;
  }
}