// AlgoDat SoSe 2000, Aufgabe 57
// Loeschen im binaeren Suchbaum
// Methoden der Klasse LinkedBinaryTree
//
// -- !!! UNGETESTET !!! --
//
// Christian Semrau
// gsemrau@cs.uni-magdeburg.de

/**
 * Entfernt das Element x aus dem Baum, wenn es enthalten ist.
 * Es ist nicht moeglich, den null-Zeiger zu entfernen, aber der kann ja auch
 * nicht eingefuegt werden.
 */

private void delete(Comparable x){

// Uebernimmt die Suche nach dem Element x, das eigentliche Entfernen
// macht dann die Methode delete(TreeNode B, TreeNode pre)

    if (root==null)
    // im leeren Baum ist kein x das man loeschen koennte
        return;

    TreeNode B = root;
    // der Knoten, der x in seinem Unterbaum enthaelt, wenn x im Baum ist
    TreeNode pre = null;
    // der Vorgaenger von B

    while (true){
    // Endlosschleife, wird durch break verlassen. Der Abbruch haette
    // genauso gut ueber eine Statusvariable realisiert werden koennen.

        if (B.getElement().compareTo(x)>0)
        // das Knotenelement ist groesser als x, also muss x links 
        // von B sein
            // wenn der linke Unterknoten nicht existiert,
            // ist x nicht im Baum enthalten, ansonsten wird
            // die Suche im linken Teilbaum fortgesetzt
            if(B.getLeft()==null)
                break;
            else{
                pre = B;
                B = B.getLeft();
            }
        else
        if (B.getElement().compareTo(x)<0)
        // das Knotenelement ist kleiner als x
            if(B.getRight()==null)
                break;
            else{
                pre = B;
                B = B.getRight();
            }
        else{
        // das Knotenelement ist gleich x
            delete(B, pre);
            // Knoten B loeschen
            break;
        }
    } // while
} // delete(Comparable)


/**
 * Entfernt den Knoten B aus dem Baum, pre ist der Vorgaengerknoten von B.
 * Wenn pre==null, dann ist B die Wurzel des Baums.
 */
private void delete(TreeNode B, TreeNode pre){

    if (B.getLeft() != null && B.getRight() != null){
    // B hat beide Unterknoten. In diesem Fall ist es egal,
    // ob B die Wurzel ist oder nicht.

        // Wir loeschen anstelle des Knotens B den kleinsten
        // Knoten im rechten Teilbaum von B (minright), nachdem wir
        // dessen Inhalt nach B kopiert haben. Nach dem Loeschen von
        // minright ist der Baum wieder sortiert und x entfernt.

        TreeNode minright = B.getRight();
        // enthaelt am Ende der Suche den kleinsten Knoten
        // im rechten Teilbaum
        TreeNode minpre = B;
        // enthaelt am Ende der Suche dessen Vorgaenger

        // Die Suche beginnt im rechten Unterknoten

        while(minright.getLeft()!=null){
        // nach links wandern bis es nicht mehr weitergeht
            minpre = minright;
            minright = minright.getLeft();
        }

        B.setElement(minright.getElement());
        // Inhalt von minright nach B kopieren

        minpre.setLeft(minright.getRight());
        // Ersatzknoten loeschen, indem wir den linken Nachfolger
        // von minpre (der vorher auf minright zeigte) auf den
        // rechten Nachfolger von minright setzen (ein linker
        // Knoten von minright existiert nicht). Wenn minright
        // keinen rechten Unterknoten hat, ist das eben der
        // null-Zeiger.

    }else{
    // B fehlt mindestens ein Unterknoten

        if (pre!=null){
        // wir sollen NICHT die Wurzel loeschen

            boolean isLeft = (pre.getLeft()==B);
            // gibt an, ob B der linke oder rechte Unterknoten 
            // von pre ist
            
            // Die folgenden drei Faelle koennten auf zwei
            // Faelle reduziert werden, dann ist aber nicht
            // mehr so durchsichtig, was passiert.

            if (B.getLeft()==null && B.getRight()==null){
            // beide Unterknoten von B fehlen
                if (isLeft)
                    pre.setLeft(null);
                else
                    pre.setRight(null);
                // wir muessen den linken oder den rechten 
                // Unterknoten von pre auf null setzen, je
                // nachdem, welcher B ist
            }else
            if (B.getLeft()==null){
            // B hat nur den rechten Unterknoten
                if (isLeft)
                    pre.setLeft(B.getRight());
                else
                    pre.setRight(B.getRight());
            }else{
            // B hat nur den linken Unterknoten
                if (isLeft)
                    pre.setLeft(B.getLeft());
                else
                    pre.setRight(B.getLeftt());
            }
        }else{
        // wir sollen die Wurzel loeschen

            // Ebenso koennten diese drei Faelle als zwei Faelle
            // behandelt werden

            if (B.getLeft()==null && B.getRight()==null)
            // B fehlen beide Unterknoten
                root = null;
                // einziger Knoten des Baums wurde geloescht
            else
            if (B.getLeft()==null)
            // B hat nur den rechten Unterknoten
                root = B.getRight();
            else
            // B hat nur den linken Unterknoten
                root = B.getLeft();
        }
    }
} // delete(TreeNode, TreeNode)

// Helfen die Kommentare oder wirken sie sich schon stoerend aus?
// Naja, der Ausdruck wird etwas laenger, aber da macht man sich halt mal
// die Muehe, die Kommentare soweit wie noetig zu entfernen - oder hat dann
// eben drei Seiten Quelltext. ;)