Java. Binärer Suchbaum mit allen Kindknoten größer als ihr Eltern?

Mein Ziel ist es eine Insert Methode zu schreiben, die Sicherstellt, dass größere Werte immer weiter nach unten geschoben werden. Die root des baumes soll also am ende der kleinste Wert sein und alle nodes darunter halt immer größer. Das hier ist mein kläglicher erster Ansatz aber ich glaube das macht wirklich gar keinen Sinn. Kann mir jemand einen geigneteren Ansatz erläutern? Würde mir wirklich sehr weiterhelfen!

public void insert(T value){
    if(root==null){
        this.root = new BTreeNode(value);
        return;
    }

    insert(root,value);
}

public void insert(BTreeNode node, T value){
    if(node.prev.value.doubleValue() <= node.value.doubleValue()) {
        double z = Math.random() * 2;
        if (z > 1) {
            if (node.left == null) {
                node.left = new BTreeNode(value);
                node.prev = node.left;
                return;
            } else {
                node.prev = node.left;
                insert(node.left, value);
            }

        } else if (z < 1) {
            if (node.right == null) {
                node.right = new BTreeNode(value);
                node.prev = node.right;
                return;
            } else {
                node.prev = node.right;
                insert(node.right, value);
            }

        } else {
            return;
        }
    }else{
        BTreeNode temp = node;
        node = node.prev;
        node.prev = temp;
    }
}

Answer 1

[ralphdieter]

ich glaube das macht wirklich gar keinen Sinn

Korrekt :-) Dein Baum hat offenbar die Eigenschaft, dass das kleinste Element ganz oben steht. Schreibe also insert() so, dass diese Eigenschaft erhalten bleibt.

Dein größtes Problem steckt wohl hier:

    if(node.prev.value.doubleValue() <= node.value.doubleValue()) {
        // ...
    }else{
        BTreeNode temp = node;
        node = node.prev;
        node.prev = temp;
    }

Die Bedingung sollte in Deinem Baum immer wahr sein. Der else-Teil wird also nur ausgeführt, wenn der Baum schon kaputt ist. Das ist auch gut so, denn dort wird der neue Wert value einfach weggeworfen und der Baum dann hoffnungslos verknotet. Denn im Baum steht node entweder in root, oder in node.prev.left oder node.prev.right. Die Zuweisung an die lokale Variable node ändert diese eigentliche Stelle im Baum nicht.

Außerdem ist es ziemlich fragwürdig, den neuen Wert zufällig zu platzieren und manchmal (bei z==1) einfach wegzuwerfen.

So könnte der Code funktionieren:

    if(node.value.doubleValue() <= value) {
        // value wahlweise in node.left oder node.right einfügen:
        if (node.left == null) {
            node.left = new BTreeNode(value);
        } else {
            insert(node.left, value);
        }
    } else {
        // neuen Knoten zwischen node.prev und node quetschen
    }

Mach Dir klar, dass Du im else-Teil herausfinden müsstest, ob node in root, oder in node.prev.left oder node.prev.right hängt. Das führt zwangsläufig zu Spaghetti-Code mit Fehlersoße.

Leichter geht es, wenn Du node.value auf den neuen Wert setzen darfst. Dann erzeugst Du einen Knoten mit dem alten Wert node.value und fügst ihn zwischen node und node.left (oder node.right) ein:

    }else{
        BTreeNode child = new BTreeNode(node.value.doubleValue());
        node.value = new T(value);
        // Aus   node -> left, right
        // wird  node -> (child -> left, null), right
        // oder  node -> left, (child -> null, right)
        child.prev = node;
        child.left = node.left; // oder .right
        node.left = child;      // oder .right
    }

Beachte, dass hier kein wirkungsloses „node=...“ mehr auftaucht.

Natürlich kannst Du hier auch rekursiv vorgehen:

    }else{
        T nodeVal = node.value.doubleValue();
        node.value = new T(value);
        insert(node.left, nodeVal); // oder .right
    }

Damit überschreibst Du weitere Knoten und hängst ganz unten ein neues Blatt an.

Kleiner Tipp: Eine Funktion verify(BTreeNode node, BTreeNode parent), die den Baum auf Konsistenz prüft, macht Dir das Leben leichter:

void verify(BTreeNode node, BTreeNode parent){
    if (node != null) {
        assert node.prev == parent;
        if (parent != null) {
            assertnode.value.doubleValue() >= parent.value.doubleValue();
        verify(node.left, node);
        verify(node.right, node);
    }
}

Answer 2

[KarlRanseierIII]

Was Du beschreibst ist kein binärer Suchbaum, weil es dem Wesen des binären Suchbaumes widerspricht.

Wenn zu dem von Dir genannten Kriterium noch eine Ordnung von links nach rechts je Ebene hinzukäme, wäre das ein binärer Min-Heap.

Comments

[InformatikIdiot]

damit es trzdm ein Baum ist wird zufällig entschieden ob die Wert links oder rechts eingeordnet werden. Ich weiß dass es kein richtiger Binärer Suchbaum ist. Aber brauche trzdm einen Ansatz zu dieser Aufgabe :D