Suchbaum Elternknoten finden Level eines Knoten bestimmen

[ocsme]

Hallo zusammen,

das was ich gemacht habe Funktioniert zwar doch leider finde ich es Persönlich viel zu umständlich. Ich laufe beim ermitteln des Level eines bestimmten Knoten z. B. zwei mal rekursiv durch. Das Problem ist ich rechne pro Ebene immer +1 doch wenn ein Knoten nicht gefunden wird bekomme ich ja auch ein Rückgabe wert

Hier mal mein Code:

    public int level(T o) {
        int count = 0;
        if(find(o))
            return level(o, root);
        return count;
    }
    
    private int level(T value, Node<T> current) {
        if (current == null)
            return -1;
        int cmp = value.compareTo(current.getKey());
        if (cmp == 0)
            return 1;
        if (cmp < 0)
            return 1+level(value, current.getLeft());
        return 1+level(value, current.getRight());
    }
    
    private boolean find(T value) {
        return findRecursive(value, root);
    }
    
    private boolean findRecursive(T value, Node<T> current) {
        if (current == null)
            return false;
        int cmp = value.compareTo(current.getKey());
        if (cmp == 0)
            return true;
        if (cmp < 0)
            return findRecursive(value, current.getLeft());
        return findRecursive(value, current.getRight());
    }
    
    public T findParent(T x){
        if(!find(x))
            return null;
        boolean foo = true;
        TreeNode<T> tmp = root;
        T h = tmp.getKey();
        while(foo) {
            int cmp = x.compareTo(tmp.getKey());
            if (cmp == 0)
                foo = false;
            else if(cmp < 0) {
                h = tmp.getKey();
                tmp = tmp.getLeft();
            }
            else if(cmp > 0) {
                h = tmp.getKey();
                tmp = tmp.getRight();
            }
        }
        return h;
    }

Wie bekomme ich das finde des Levels in 1 Rekusive Methode? und wie kann ich den ElternKnoten des gesuchten Knotens rekusiv bestimmen?

LG

 

[mrBrown]

Was willst du denn überhaupt machen? Du hast leider jeglichen Kontext weggelassen...

 

[mihe7]

wie kann ich den ElternKnoten des gesuchten Knotens rekusiv bestimmen?

Indem Du bei der Suche den Elternknoten mitgibst?

Wie bekomme ich das finde des Levels in 1 Rekusive Methode?

Indem Du bei der Suche das Level mitgibst?

Du kannst jetzt die "billig Copy & Paste Variante" nehmen, d. h. die findRecursive-Methode nehmen, kopieren und umbenennen (findLevel, findParent) und anpassen.

Oder aber, Du schreibst die findRecursive-Methode um, dass diese den Pfad zum Knoten zurückgibt...

private Stack<Node<T>> findRecursive(T value, Node<T> current, Stack<Node<T>> visited) {
    if (current == null) { return null; }

    visited.push(current);
    ...
    if (value.compareTo(current.getValue()) == 0) { return visited; }
    ...
}

 

[ocsme]

Was willst du denn überhaupt machen? Du hast leider jeglichen Kontext weggelassen...

hupsi ja das habe ich weil ich versucht hatte das ganze relativ allgemein zu schreiben vor allem auch für die Such Funktion hier im Forum. Denn manche Themen die einfach nur Exception heißen oder so etwas sind nur noch nervig dann schreibt man lieber ein Thema zum 1.000ten mal neu auch nervig.

@mihe7 hat es erfasst ich wollte "einfach" nur die 2 Methoden kleiner verpacken. Das verstehe ich zwar noch nicht so ganz doch ich werde mir mühe geben und es später weiter versuchen vielleicht klappt es ja wenn nicht melde ich mich hier wieder. Es läuft ja doch nur !!!nervig!!! unnötig 2x rekursiv rauf und runter den Baum zu laufen nur damit es so angepasst wird

Liebe Grüße

 

[ocsme]

Ich hab ein Problem. Wenn ich bei dem Level eines Knotens das Level immer übergebe, habe ich das gleiche Problem wie oben.
Er gibt mir natürlich auch eine Zahl zurück obwohl der Knoten nicht existiert

Könnte ja auch einfach eine Exception werfen wenn das Element nicht gefunden wird "Fertig!"

Ich verstehe es leider nicht!

LG

 

[ocsme]

findParent ist nur leider das selbe Problem. Sobald ich einen Knoten abfrage der nicht existiert gibt er mir etwas zurück

public T findParent(T x) {
        return findParent(x, root, null);
    }
    
    private T findParent(T x, TreeNode<T> root, T parent) {
        if(root != null) {
            int cmp = x.compareTo(root.getKey());
            if(cmp == 0)
                return parent;
            if(cmp < 0)
                return findParent(x,root.getLeft(),root.getKey());
            else if(cmp > 0)
                return findParent(x,root.getRight(),root.getKey());
        }
        return parent;
        
    }

 

[mihe7]

Wenn ich bei dem Level eines Knotens das Level immer übergebe, habe ich das gleiche Problem wie oben.
Er gibt mir natürlich auch eine Zahl zurück obwohl der Knoten nicht existiert

Du musst den Fall, wenn ein Element nicht gefunden wird, natürlich irgendwie abbilden. Hierfür gibt es zig Möglichkeiten.

Wenn Du z. B. einen primitiven Datentypen als Rückgabetyp verwendest, kannst Du einen Wert nehmen, der außerhalb des Wertebereichs dessen liegt, was bei vorhandenem Element möglich wäre. Anders gesagt: wenn das gesuchte Element im Baum vorhanden ist, dann ist garantiert, dass level >= 0 gilt. Damit kannst Du den Fall, dass das gesuchte Element nicht im Baum vorhanden ist, durch level < 0 abbilden.

Statt eines primitiven Datentyps kannst Du auch ein Objekt zurückgeben. Im einfachsten Fall wäre das ein Integer und der "Sonderfall" könnte mit null statt einer negativen Zahl dargestellt werden. Besser könnte das durch Optional<Integer> beschrieben werden.

findParent ist nur leider das selbe Problem. Sobald ich einen Knoten abfrage der nicht existiert gibt er mir etwas zurück

Ja, änder halt einfach Dein letztes return.

 

[ocsme]

Ja, änder halt einfach Dein letztes return.

Ahhhh... das hatte ich vorhin so gemacht mit return null ein bisschen hab ich ja gelernt
Doch dann kam immer null zurück (läuft jetzt aber kann gut sein das ich auch vorhin etwas geändert noch hatte )

Das mit dem Integer habe ich das Problem gehabt das immer wenn ich -1 zurück gegeben hab wurde das ins "return Ergebnis" gerechnet. Also wenn dort normal 5 raus kam obwohl das Objekt nicht im Baum ist kam 4 raus

Ich versuch es nochmal

Bin ja schon mal froh das Parent jetzt läuft

Danke nochmals

LG

 

[ocsme]

Mit dem level tu ich mir zu schwer ich bekomme es so nicht hin.
Wenn ich die Wurzel angebe gibt er mir 1 zurück. Wenn ich einen anderen Knoten im Baum als Parameter übergebe bekomme ich -1 und wenn der Knoten nicht existiert auch -1.

    public int level(T o) {
        int count = 0;
        return level(o, root, count);
    }
  
    private int level(T o, Node<T> root, int count) {
        if(root != null) {
            int cmp = o.compareTo(root.getKey());
            if(cmp == 0)
                return ++count;
            if(cmp < 0)
                return level(o,root.getLeft(),++count);
            else if(cmp > 0)
                return level(o,root.getLeft(),++count);
        }
        return -1;
    }

Okay was mir jetzt klar ist, ich return nur 1x den count um 1 hoch. das aufrufen von links und rechts mit ++count zählt irgendwie nicht.
Deswegen dachte ich es würde so gehen

if(cmp < 0)
                return ++count  + level(o,root.getLeft(),count);
            else if(cmp > 0)
                return ++count  +level(o,root.getLeft(),count);

Doch leider klappt das auch nicht denn jetzt hätte ich wieder das alte Problem ich zähle munter hoch und gebe bei root == null -1 zurück also wird das Ergebnis um 1 wieder inkrementiert.

mhh... stelle ich mich gerade nur so doof an

LG

 

[ocsme]

Mir reicht es
LESEN MUSS GELERNT SEIN

Ich gehe immer nur nach Links :/
so jetzt sollte es gehen

Könnt ihr mir noch erklären wie ich das mit dem count schöner machen kann?

public int level(T o) {
        return level(o, root, 0);
    }
   
    private int level(T o, Node<T> root, int count) {
        if(root != null) {
            int cmp = o.compareTo(root.getKey());
            if(cmp == 0)
                return count+1;
            if(cmp < 0)
                return level(o,root.[B]getLeft()[/B],count+1);
            else if(cmp > 0)
                return level(o,root.[B]getRight()[/B],count+1);
        }
        return -1;
    }

 

[mihe7]

Du könntest zu Beginn count++ ausführen. Und wenn Du Langeweile hast oder üben möchtest, dann implementierst Du den Spaß noch so um, dass Dir findRecursive einen Pfad zum gesuchten Knoten liefert

 

[ocsme]

Und wenn Du Langeweile hast oder üben möchtest, dann implementierst Du den Spaß noch so um, dass Dir findRecursive einen Pfad zum gesuchten Knoten liefert

:O Wie soll das den Funktionieren?
Zum Üben ist das sicherlich gut doch mir fällt jetzt nichts ein wie das gehen soll. Denn wir hätten dann ja mitten im Baum eine Referenz oder null. Doch ich Frage mich wie bewege ich mich von dieser Referenz dann nach oben?
Wenn ich das wüsste wäre Parent ja auch super damit gemacht 1 Aufruf Finde den Knoten und 1 Aufruf gehe einmal nach oben

Ich überlege mal noch. Doch ich hätte auch noch die zwei Übungen wo ich auch nicht weiter kommen:
successor(key) soll das nächst größere Element von key zurück geben
und deccessor(key) soll das nächst kleinere Element von key zurück geben.

Zuerst dachte ich das ist doch ganz einfach, doch das sind ja wieder Intervall untersuchungen
Wenn ich im Baum 2 Knoten habe Root = 10 und links = 5 ich suche successor(6) müsste er mir 10 zurück geben. Ist der Baum jetzt größer Root = 30 dann 10 und 5 müsste er mir wieder 10 zurück geben. Ich hätte es so gemacht das der erste Wert zurück kommt der größer ist als Key also die 30

Aber erst einmal bin ich froh das endlich das hier geklappt hat

LG

 

[mihe7]

Zuerst dachte ich das ist doch ganz einfach

Wenn Du den Knoten von key hast, ist der Nachfolger das Blatt links im rechten Teilbaum und der Vorgänger das Blatt rechts im linken Teilbaum.

 

[ocsme]

Wenn Du den Knoten von key hast, ist der Nachfolger das Blatt links im rechten Teilbaum und der Vorgänger das Blatt rechts im linken Teilbaum.

Muss Key denn im Baum sein?
Wenn Ja ist es ja nicht schwer aber ich dachte Key müsse nicht im Baum sein. Sprich man übergibt ein Element was vergleichbar ist und gibt dann das kleinste Element im Baum das zu Key passt zurück. Wobei wenn ich jetzt gerade so überlege sollte das Iterativ glaube nicht schwer sein man speichert einfach ein minimum z. B.
mal probieren

Wie das mit der findeRecusive Methode gehen soll hab ich noch nicht raus gefunden Mein Problem ist eben das ich keine Ahnung habe wie ich dann an die höheren Referenzen komme Ich überlege aber noch

LG

 

[ocsme]

Hab es erstmal versucht wenn das Element key im Suchbaum vorhanden ist doch auch dort habe ich ein Problem.
Das Problem steht auch im Code:

/*
* hier fehlt der else Teil, wenn der Knoten
* ein Blatt ist muss man im Baum zwei Elternteile nach oben
* und dann dort ganz nach rechts in den Baum
*/

Leider bekomme ich es ohne Hilfe nicht hin da ich nicht weiß wie ich 2 Knoten nach oben komme. Wollte erst den 2ten Elternknoten mit in der Rekursion mit geben doch auch das weiß ich nicht wie es geht

Kann mir jemand Helfen?

//gibt nächstgrösseren keyzurück
    public T successor(T key) {
        if(key!=null)
            return successor(key, root, null);
        else return null;
    }
   
    private  T successor(T x, Node<T> root, T parent) {
        if(root != null) {
            int cmp = x.compareTo(root.getKey());
            if(cmp == 0)
                if(root.getRight()!=null)
                    return root.getRight().getKey();
                else
                    /*
                     * hier fehlt der else Teil, wenn der Knoten
                     * ein Blatt ist muss man im Baum zwei Elternteile nach oben
                     * und dann dort ganz nach rechts in den Baum
                     */
            if(cmp < 0)
                return findParent(x,root.getLeft(),root.getKey());
            else if(cmp > 0)
                return findParent(x,root.getRight(),root.getKey());
        }
        return null;
       
    }

 

[mihe7]

Muss Key denn im Baum sein?

Ach so... Übrigens habe ich vorhin übersehen, dass der Vorgänger auch der Elternknoten sein kann - und das Blattproblem auch :-(

* ein Blatt ist muss man im Baum zwei Elternteile nach oben
* und dann dort ganz nach rechts in den Baum

   9
/   \
5     12
\    /\
  7  11 13

Wenn der Nachfolger der 7 gesucht wird, dann ist 7 ein Blatt. Zwei Elternteile nach oben wäre die 9 -> OK. Aber warum sollte man dann noch ganz rechts in den Baum?!? Das stünde die 13.

 

[ocsme]

   9
/   \
5     12
\    /\
  7  11 13

Wenn der Nachfolger der 7 gesucht wird, dann ist 7 ein Blatt. Zwei Elternteile nach oben wäre die 9 -> OK. Aber warum sollte man dann noch ganz rechts in den Baum?!? Das stünde die 13.

Ja, da hast du absolut recht ich müsste nur 2 Elternknoten nach oben. Hab mir das gestern auch schön aufgezeichnet und so in meiner Zeichnung rum gekritzelt das ich später wieder etwas verwirrt war.

Aber das Problem mit dem zweiten Elternpaar hätte ich immer noch Wie kann ich den in der Rekursion zurück geben? Indem ich ihn mitgeben okay aber wie gebe ich den mit? Da ist mir leider auch nichts effektives eingefallen.

Das andere sollte stimmen wenn der Knoten kein Blatt ist gehe "einfach" nach rechts

----
Das nächste Problem wäre natürlich was ist wenn Key gar nicht im Baum ist doch eins nach dem anderen

LG

 

[ocsme]

ufff diese Bäume bringen mich noch um.
Ich bekomme das delete nicht richtig hin.

Hier mal meine Version:

delete(T x, Node<T> root) {
        if (root != null) {
            int cmp = x.compareTo(root.getKey());
            if (cmp < 0)
                root.setLeft(delete(x, root.getLeft()));
            else if (cmp > 0)
                root.setRight(delete(x, root.getRight()));
            else {
                if (root.getLeft() == null)
                    root = root.getRight();
                else if (root.getRight() == null)
                    root = root.getLeft();
                else {
                    Node<T> help = root.getLeft();
                    Node<T> previous = null;
                    while(help.getRight() != null) {
                        previous = help;
                        help = help.getRight();
                    }
                    if(help == root.getLeft()) {
                        help.setRight(root.getRight());   
                        root.setRight(null);
                        root.setKey(null);
                    }
                    else {
                        previous.setRight(help.getLeft());
                        help.setLeft(root.getLeft());
                        help.setRight(root.getRight());
                    }
                    root = help;
                }
            }
        }
        return root;

    }

wenn ich nun die Knoten: 4, 2, 6, 8, 9, 7, 5, 3 und 1 einfüge und versuche sie so zu löschen: 5, 6, 4, 7, 8, 9, 2, 1 und 3.
Löscht er bei der 4 nicht die Wurzel sondern die 3 und die 4 bleibt immer über.

Dieser Code ist nicht von mir der geht aber:

delete(Node<T>  n, T x){
        if(n==null){
            System.out.println("Not Found");
            return null;
        }
        if(n.getKey().compareTo(x)<0) n.setRight(delete(n.getRight(), x));
        else if(n.getKey().compareTo(x)>0) n.setLeft(delete(n.getLeft(), x));
        else{
            if(n.getLeft()==null) n = n.getRight();
            else if(n.getRight()==null) n = n.getLeft();
            else if(n.getLeft().getRight()==null){
                n.getLeft().setRight(n.getRight());
                n = n.getLeft();
            }
            else{
                Node<T> h = n.getLeft();
                Node<T> p = null;
                while(h.getRight()!=null){
                    p=h;
                    h=h.getRight();
                }
                p.setRight(h.getLeft());
                h.setLeft(n.getLeft());
                h.setRight(n.getRight());
                n=h;
            }
        }
        return n;
    }

Verstehe leider auch nicht so ganz was er hier anstellt:

if(n.getLeft().getRight()==null){
                n.getLeft().setRight(n.getRight());
                n = n.getLeft();
            }

 

[Xyz1]

Ich las nicht alles... Soll der Baum nach einfügen/entfernen/ vor suchen ausbalanciert sein? Das ist wieder ein anderes Kaliber.

 

[ocsme]

ausbalanciert

Nein soll er soweit ich weiß nicht
Bekomme ja leider nicht mal das normale Löschen hin

LG

 

[mihe7]

Nochmal zurück zum Nachfolger/Vorgänger:

Gesucht ist für einen gegebenen Wert v der Knoten im Baum, der den kleinsten Wert größer als v enthält.

Wenn wir bei einem beliebigen Knoten k feststellen, dass dessen Wert größer als v ist, kann sich der gesuchte Knoten höchstens im linken Teilbaum befinden. Existiert er dort nicht, muss k der gesuchte Knoten sein.

Stellen wir bei einem beliebigen Knoten k dagegen fest, dass dessen Wert kleiner als v ist, kann sich der gesuchte Knoten höchstens im rechten Teilbaum befinden. Existiert er dort nicht, dann hat v keinen Nachfolger im Baum.

Habe ich was übersehen?

 

[ocsme]

Ich glaube du hast nichts vergessen.

 

[ocsme]

@mihe7 denke so sollte es dann sein
Hatte gestern dann auch ein MEGA Denkfehler

// gibt nächstgrösseren keyzurück
    public T successor(T key) {
        if (key != null)
            return successor(key, root, null);
        else
            return null;
    }

    private T successor(T x, TreeNode<T> root, T parent) {
        if (root != null) {
            int cmp = x.compareTo(root.getKey());
            if (cmp == 0)
                if (root.getRight() != null)
                    return root.getRight().getKey();
                else
                    return parent;
                if (cmp < 0)
                    return successor(x, root.getLeft(), root.getKey());
                else if (cmp > 0)
                    return successor(x, root.getRight(), root.getKey());
        }
        return null;

    }

Getestet mit den Zahlen:
bt.insert(5); -> wurzel
bt.insert(20);
bt.insert(10);
bt.insert(30);
bt.insert(11);
bt.insert(4);
bt.insert(1);
bt.insert(7);
bt.insert(9);
bt.insert(37);
bt.insert(130);


System.out.println(bt.successor(1)); -> Ausgabe: 4
System.out.println(bt.successor(10)); -> Ausgabe: 11

1 hängt ganz links im Baum die 4 ist der Vaterknoten.
10 hängt mitten im Baum und 11 ist der nächst größere Wert

 

[mihe7]

denke so sollte es dann sein

Was liefert denn System.out.println(bt.successor(11)); ?

 

[ocsme]

Was liefert denn System.out.println(bt.successor(11)); ?

haha 10 so ein misst aber auch zu früh gefreut

LG

so geht es dann bekommt man eben einen Hinweis das man doof ist quatsch bei Seite.
Das Problem wäre gelöst wenn ich den parent des parent mit geben würde. Doch leider weiß ich nicht wie das geht. Wie muss ich denn dann die Rekursion aufrufen? also mir ist klar das die Methode dann 4 Parameter hat.

private T successor(T x, TreeNode<T> root, T parent) {
        if (root != null) {
            int cmp = x.compareTo(root.getKey());
            if (cmp == 0)
                if (root.getRight() != null)
                    return root.getRight().getKey();
                else if(x.compareTo(parent) > 0)
                    System.out.println("doof");
                else return parent;
                if (cmp < 0)
                    return successor(x, root.getLeft(), root.getKey());
                else if (cmp > 0)
                    return successor(x, root.getRight(), root.getKey());
        }
        return null;

    }