@Override
    /**
     * Fügt dem Baum einen Wert hinzu
     *
     */
    public void addValue(Integer value) throws BinarySearchTreeException {
        if (root == null) {
            //Wenn es noch keinen root Knoten gibt, erzeuge diesen mit dem hinzuzufügenen Wert
            root = new Node(value);

            //Rebalancing muss hier nicht durchgeführt werden, weil der Wert als einziger Knoten daherkommt
        } else {
            //Der Anfangsknoten zum suchen nach einer Einfügeposition ist immer root
            Node n = root;

            //Stack für das nachverfolgen des weges über die Nodes
            Stack nodeTrace = new Stack();

            nodeTrace.add(root);

            Node newNode = new Node(value);

            //Solange dem Baum folgen, bis ein freier Platz gefunden wird
            while (true) {
                if (value < n.getValue()) { //Wenn der Wert kleiner als der des aktuellen Knotens ist, suche links nach einem freien Platz
                    if (n.getLft() == null) {
                        //Freier Platz gefunden, Knoten einfügen
                        n.setLft(newNode);
                        break;
                    } else {
                        //Nächste Ebene durchsuchen
                        n = n.getLft();

                        //Knoten zum Stack hinzufügen
                        nodeTrace.add(n);
                    }

                } else if (value > n.getValue()) { //Wenn der Wert größer als der des aktuellen Knotens ist, suche rechts nach einem freien Platz
                    if (n.getRgt() == null) {
                        //Freier Platz gefunden, Knoten einfügen
                        n.setRgt(newNode);
                        break;
                    } else {
                        //Nächste Ebene durchsuchen 
                        n = n.getRgt();

                        //Knoten zum Stack hinzufügen
                        nodeTrace.add(n);
                    }
                } else {
                    //Knoten bereits vorhanden, Exception werfen
                    throw new BinarySearchTreeException();
                }
            }

            nodeTrace.add(newNode);

            //Baum rebalancieren
            performRebalance(nodeTrace);
        }
    }