Search Tree

[Kirby.exe]

Also wir sollen einen Search Tree implementieren. Soweit so gut xD Jedoch sieht meine remove()-Methode ugly as fuck aus xD Habt ihr tipps die cleaner zu schreiben oder zu formatieren

@Override
    public boolean remove(KeyType key) {
        if(isEmpty()) {
            return false;
        }
        TreeNode<KeyType,DataType> it = head;
        
        while(it != null && it.getKey().compareTo(key) != 0) {
            it = key.compareTo(it.getKey()) < 0 ? it.getLeftNode() : it.getRightNode();
        }
        
        if(it == null) {
            return false;
        }
        
        if(it.getLeftNode() == null && it.getRightNode() == null) {
            if(it.getKey().compareTo(it.getParentNode().getKey()) < 0) {
                it.getParentNode().setLeftNode(null);;
            }else {
                it.getParentNode().setRightNode(null);;
            }
            it.setParentNode(null);
            
        }else if(it.getLeftNode() != null && it.getRightNode() == null) {
            if(it.getKey().compareTo(it.getParentNode().getKey()) < 0) {
                it.getParentNode().setLeftNode(it.getLeftNode());;
            }else {
                it.getParentNode().setRightNode(it.getLeftNode());;
            }
            it.getLeftNode().setParentNode(it.getParentNode());
            
        }else if(it.getLeftNode() == null && it.getRightNode() != null) {
            if(it.getKey().compareTo(it.getParentNode().getKey()) < 0) {
                it.getParentNode().setLeftNode(it.getRightNode());;
            }else {
                it.getParentNode().setRightNode(it.getRightNode());;
            }
            it.getRightNode().setParentNode(it.getParentNode());
            
        }else {
            //Still have to thing about this xD
        }
        size--;
        return true;
    }

class TreeNode<KeyType extends Comparable<? super KeyType>, DataType>{
    
    private KeyType key;
    private DataType data;
    private TreeNode<KeyType,DataType> parent;
    private TreeNode<KeyType,DataType> left;
    private TreeNode<KeyType,DataType> right;
    
    public TreeNode(KeyType key, DataType data) {
        this.key = key;
        this.data = data;
        left = right = parent = null;
    }
    
    public KeyType getKey() {
        return key;
    }
    
    public void setKey(KeyType key) {
        this.key = key;
    }
    
    public DataType getData() {
        return data;
    }
    
    public void setData(DataType data) {
        this.data = data;
    }
    
    public TreeNode<KeyType,DataType> getParentNode(){
        return parent;
    }
    
    public void setParentNode(TreeNode<KeyType,DataType> parent) {
        this.parent = parent;
    }
    
    public TreeNode<KeyType,DataType> getLeftNode(){
        return left;
    }
    
    public void setLeftNode(TreeNode<KeyType,DataType> left) {
        this.left = left;
    }
    
    public TreeNode<KeyType,DataType> getRightNode(){
        return right;
    }
    
    public void setRightNode(TreeNode<KeyType,DataType> right) {
        this.right = right;
    }
    
    public String toString() {
        return key+": " + data + " (left: " + (left == null ? null : left.key) + " right: " + (right == null ? null : right.key)+")";
    }
}

 

[mihe7]

Formulier die Schritte mal in groben Worten.

 

[Kirby.exe]

1. When der Baum leer ist --> brich ab
2. Durchlaufe den Baum und suche das element(brich ab falls keine Knoten mehr vorhanden sind oder der gesuchte Knoten anliegt)
3. Prüfe ob ein Knoten vorliegt anonsten ---> return null
4. Prüfe ob der Knoten keine Kinder hat --> löschen
   1. Prüfe ob der Knoten ein linkes Kind hat --> lege referenz des Kinds um und lösche den gesuchten Node
   2. Prüfe ob der Knoten ein rechtes Kind hat --> lege referenz des Kinds um und lösche den gesuchten Node
   3. Da alles fälle nicht erfüllt sind, hat der Knoten zwei Kinder ---> finde successor und tausche mit der zu löschenden Wurzel
5. size erhöhen und return true

 

[mihe7]

Noch gröber. (EDIT: die Ideen sollen klar werden; was der Code macht, steht ja schon da )

 

[Kirby.exe]

Noch gröber xD Oh gott xD

Also im Grunde möchte ich einen Node löschen, aber es muss vorher geschaut werden ob und wie viele Kinder dieser Knoten hat bevor er gelöscht werden kann xD

 

[mihe7]

OK. Die Schritte 1 bis 3 lassen sich zusammenfassen: Suche den zu löschenden Knoten, gibt es diesen nicht, sind wir fertig, da das Element nicht gelöscht werden konnte:

TreeNode<KeyType, DataType> toDelete;
if ((toDelete = find(key)) == null) {
    return false;
}

Das Löschen selbst läuft so ab, dass der zu löschende Knoten durch einen geeigneten Knoten (oder null, falls es keinen solchen gibt) ersetzt wird. Hat toDelete also zwei Kinder, wird toDelete durch den in-order-Nachfolger im rechten Teilbaum ersetzt. Ansonsten wird toDelete durch seinen pre-order-Nachfolger ersetzt.

Einen Knoten n durch einen Knoten m zu ersetzen, heißt:
1. Falls n die Wurzel ist, ist m die neue Wurzel
2. Sonst: m.parent = n.parent und
2.1 n.parent.left=m, falls n.parent.left == n
2.2 n.parent.right = m, falls n.parent.right == n

Darfst Du eigentlich die Klasse TreeNode verändern?

TreeNode<KeyType, DataType> replacement;
replacement = replacementFor(toDelete);
replace(toDelete, replacement);

Wäre jetzt eine mögliche Strukturierung.

 

[Kirby.exe]

THX für deine Tipps Ich darf alles anpassen aus TreeNode Nur leider nichts aus dem eigentlichen Tree...Sonst könnte ich einiges an Code reusen...xD

 

[Kirby.exe]

OK. Die Schritte 1 bis 3 lassen sich zusammenfassen: Suche den zu löschenden Knoten, gibt es diesen nicht, sind wir fertig, da das Element nicht gelöscht werden konnte:

TreeNode<KeyType, DataType> toDelete;
if ((toDelete = find(key)) == null) {
    return false;
}

Das tue ich ja xD Aber ich könnte es natürlich auslägern xD Scheint sinnvoll xD

 

[Kirby.exe]

Eine Sache die mich an meinem If-Else Block ekelt ist, dass ich ständig suchen muss ob der zu löschende Knoten jetzt der linke oder der rechte ist xD

 

[Kirby.exe]

Alsooo ich habe es jetzt einfach verallgemeinert und in eine helper klasse gesteckt xD

@Override
    public boolean remove(KeyType key) {
        if(isEmpty()) {
            return false;
        }
        
        TreeNode<KeyType,DataType> toDelete;   
        if((toDelete = find(key)) == null) {
            return false;
        }
        
        if(toDelete.getLeftNode() != null && toDelete.getRightNode() != null) {
            TreeNode<KeyType,DataType> replacement;
            replacement = replacementFor(toDelete);
            replace(toDelete, replacement);
            
        }else if(toDelete.getLeftNode() == null && toDelete.getRightNode() != null) {
            setRefrence(toDelete, toDelete.getRightNode());
            toDelete.getRightNode().setParentNode(toDelete.getParentNode());
            
        }else if(toDelete.getLeftNode() != null && toDelete.getRightNode() == null) {
            setRefrence(toDelete, toDelete.getLeftNode());
            toDelete.getLeftNode().setParentNode(toDelete.getParentNode());
            
        }else if(toDelete.getLeftNode() == null && toDelete.getRightNode() == null) {
            setRefrence(toDelete, null);
            toDelete.setParentNode(null);
            
        }
        size--;
        return true;
    }

    private void setRefrence(TreeNode<KeyType,DataType> baseNode, TreeNode<KeyType,DataType> newNode) {
        if(baseNode.getKey().compareTo(baseNode.getParentNode().getKey()) < 0) {
            baseNode.getParentNode().setLeftNode(newNode);
        }else {
            baseNode.getParentNode().setRightNode(newNode);
        }
    }

 

[Kirby.exe]

Ich habe es jetzt weitestgehend aufgeräumt Derzeit kämpfe ich jedoch noch mit meiner findSuccessor Method xD Ich suche gerade warum zur Hölle er mir eine NullPointer schmeißt xD Das passiert wenn der Node halt zwei Kinder hat...

Hier ist die Methode dafür:

@Override
    public DataType successor(KeyType key) {
        TreeNode<KeyType,DataType> toDelete;
        if((toDelete = find(key)) == null)     return null;
       
        TreeNode<KeyType,DataType> replacement;
        replacement = replacementFor(head,toDelete,null); //  <--- liefert null zurück
        System.out.println(replacement);
        //replace(toDelete, replacement);
        return replacement.getData(); // <--- NullPointerException da es null ist
    }

private TreeNode<KeyType,DataType> replacementFor(TreeNode<KeyType,DataType> root, TreeNode<KeyType,DataType> node, TreeNode<KeyType,DataType> successor){
        if(isEmpty())  return null;
        if(root.getKey().compareTo(node.getKey()) == 0){
            if(root.getRightNode() != null)
                return findMin(root.getRightNode());
            else
                return successor;
        }
       
        if(node.getKey().compareTo(root.getKey()) < 0)  
            return replacementFor(root.getLeftNode(),node,root);
        else
            return replacementFor(root.getRightNode(),node,successor);
    }
   
    private TreeNode<KeyType,DataType> findMin(TreeNode<KeyType,DataType> node){
        if(node == null)  return node;
        while(node.getLeftNode() != null)    node = node.getLeftNode();
        return node;
    }

Hiermit teste ich den ganzen Kram:

public static void main(String[] args) {
        SearchTree<Integer, String> t = new SearchTree<Integer, String>();
        System.out.println(t);
        t.insert("Wurzel", 5);
        System.out.println(t);
        t.insert("lol", 3);
        t.insert("Wurzel2", 19);
        System.out.println(t);
        t.insert("Wurzel3", 13);
        System.out.println(t);
        t.insert("Wurzel4", 7);
        System.out.println(t.insert("Wurzel5", 7));
        t.insert("lalo", 14);
        System.out.println(t);
        System.out.println(t.successor(19)); // <--- Das geht nicht
    }

Das lustige ist, dass es auch bei 2 Childs geht nur beim Key = 19 nicht...Wenn ich zum Beispiel Successor von 5(Urwurzel) haben möchte dann liefert er mir das Element mit Key = 7, was korrekt ist

 

[Kirby.exe]

Alsoo ich habe den Übeltäter...Er glaubt, dass der Node mit dem Key = 19 gar kein rechtes Kind hat, jedoch ist das Bullshit xD

Edit: Ich habe scheiße erzählt....Key = 19 hat auch kein rechtes Kind sondern nur ein linkes....