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; } }