Datenstruktur auf SET prüfen in O(n)

Bitte aktiviere JavaScript!
Guten Tag,

habe wieder einmal eine Aufgabe wo ich zwar denke ich hätte einen "Lösungsansatz" doch bekomme ich es nicht Programmiert. Hier mal die Aufgabe:

Eine Multimenge sei mit Hilfe von binären Suchbäumen wie unten aufgeführt implementiert. Für jeden Knoten (Node) im Baum ist sein Wert ungleich null und größer oder gleich allen Werten im linken Teilbaum und kleiner als alle Werte im rechten Teilbaum. Gesucht ist die Methode isSet(). Diese Methode überprüft bei einer Komplexität von maximal O(n), ob eine Menge vorliegt (d.h. keine Duplikate vorkommen). Achtung: Die Werte sollen nicht etwa in eine andere Repräsentation kopiert werden; es ist lediglich der Baum geeignet zu analysieren.
Der Code dazu:
Code:
class TreeBag<X extends Comparable<X>> {
    private class Node {
    X value;
    Node left, right;
    }

    private Node root;
    public boolean isSet() {
    
    }
}
Die Idee von mir wäre man nimmt Intervalle. Wenn der Baum oben mit 8 Anfängt hätten wir Links [8 ... ] und Rechts [ ... 7]. Doch es sind ja nicht nur Integer zugelassen sondern sämtliche X die Vergleichbar sind. Wie ich dort dann ein Intervall bilden könnte keine Ahnung. Weiß'noch nicht mal ob die Idee dafür geeignet wäre.
Alle anderen Ideen die ich hatte Speichern den Baum in eine andere Struktur oder laufen 10.000x durch den Baum also nicht O(n).
Es sind bis jetzt auch erst Ideen zu einer Implementierung kam ich bis jetzt noch nicht und wüsste auch nicht wie das mit den Intervallen gehen würde :(

Danke im voraus :)

LG
 
Also das klingt mir zu kompliziert. Wenn es einen Wert doppelt gibt: Wie ist dieser dann im Baum gespeichert? Wenn Du dieses Kriterium definieren kannst, dann kannst Du einmal durch den ganzen Baum gehen und jeden Knoten darauf überprüfen.

Somit muss der Baum nicht mehrfach durchlaufen werden und die Daten auch nicht anders gespeichert werden.
 
Meinst du das:
größer oder gleich allen Werten im linken Teilbaum
Sprich wenn ich bei der Wurzel anfangen muss ich ja im linken Teilbaum schauen da dort das gleiche Element stehen könnte.
Doch dann bräuchte man doch auch wieder ein Array oder so etwas zum Speichern der Element. Denn das Element könnte weiter nach Links rücken und könnte dann nicht direkt verglichen werden.

Ich hab keine Ahnung wie das gehen soll :p :(

LG
 
Sprich wenn ich bei der Wurzel anfangen muss ich ja im linken Teilbaum schauen da dort das gleiche Element stehen könnte.
Ja, aber dort muss es entweder die Wurzel des linken Teilbaumes sein oder irgendwo in dessen rechten Teilbaum. Du musst dir also nur (getrennt) überlegen, was du im linken und rechten Teilbaum jeweils vorfinden könntest, das die Set-Eigenschaft verletzt. Dann genügt ein Durchlauf. Am besten malst du dir mal so einen Baum auf und spielst es durch.
Doch dann bräuchte man doch auch wieder ein Array oder so etwas zum Speichern der Element
Man kann den Duplikats-Kandidaten für den linken und rechten Teilbaum jeweils eindeutig identifizieren.
 
Nein sorry ich kann es mir auch aufzeichnen ich komme nicht drauf ohne die Struktur zu speichern :(

Hier mal mein Beispiel:
Code:
                44   
          50                40
    52            46
107...48      48...44
Wie sollte man nun erkennen das 44 oder 48 doppelt drin sind?

LG
 
Es geht ja nur darum, zu prüfen, ob es ein set ist. So also ein Duplikat gefunden wurde, kannst Du false zurück geben.

Somit prüfst Du:
Ist der Node ein Duplikat (Wert im linker Teilbaum gleich Wert aktueller Node?) -> false zurückgeben.
Ist linker Teilbaum ein Set? Wenn nicht: false zurückgeben.
Dann rechts prüfen und fertig....

Du musst Dir nur noch alle notwendigen Checks überlegen, damit du keine NPE bekommst.
 
Nein sorry ich kann es mir auch aufzeichnen ich komme nicht drauf ohne die Struktur zu speichern :(

Hier mal mein Beispiel:
Code:
              44  
        50            40
    52        46
107      48  48   44
Wie sollte man nun erkennen das 44 oder 48 doppelt drin sind?

LG
Kann es so einen Baum denn geben?

Wobei die Striche fehlten, aber ich habe es so verstanden, dass an der 52 die 107 und 48 hängen und davon der Parent 50 sein soll.
 
Wieso sollte es so einen Baum nicht geben?
Es geht doch darum Duplikate einzubauen und dann zu suchen.

Wurzel: 44
1 Ebene: <- Links 50 -> rechts 40
2 Ebene: (unter 50) <- Links 52 -> rechts 46
3 Ebene: (unter 52) <- Links 107 -> rechts 48 (unter 46) <- links 48 -> rechts 44
 
Gut dann scheitert es nicht nur an der Bewältigung der Aufgabe sondern schon am Verständnis der Aufgabe (mal wieder :()

Dann drehen wir denn Baum etwas um. Das macht es bei mir nur immer noch nicht verständlicher :(

Danke trozdem :)

LG
 
Wenn man deinen Baum spiegelt (damit er der Aufgabenstellung entspricht) befindet sich eine 44 im rechten Teilbaum der Wurzel 44. Das kann nicht sein, weil dort nur größere Elemente existieren dürften. Die doppelte 48 im rechten Teilbaum der 50 kann es auch nicht geben, weil sie ja kleiner als 50 ist.
 
Für jeden Knoten (Node) im Baum ist sein Wert ungleich null und größer oder gleich allen Werten im linken Teilbaum und kleiner als alle Werte im rechten Teilbaum.
Ich stehe hier gerade schon auf dem Schlauch :D denke das ist nichts für mich :p Die Aufgabe überfordert mich ja schon bei der Fragestellung :(
Wo sollen nun immer die doppelten stehen?
Denn beim insert erkenne ich ja x.compareTo(x) == 0 :) also doppelt füge Element x immer Links ein oder Rechts :p

Wollte es an einem kleineren Baum einfach nochmal versuchen doch wie gesagt wo soll den nun das doppelte Element hin?
Wurzel: 7 linkes Blatt 3 rechtes Blatt 9 nun wieder 7 wohin ?

LG
 
Binärer Suchbaum bedeutet: Alle Werte auf einer Seite sind größer bzw. kleiner als der eigene Wert.

Also kann es auf einer Seite der 50 nicht eine kleiner und eine größere Zahl geben. Hier ist es konkret vorgegeben: links sind die Werte kleiner oder gleich, rechts sind die Werte größer.

Aber ich merke gerade, dass ich auch einen kleinen Denkfehler gemacht habe, denn ich bin bisher davon ausgegangen, dass es der direkte linke Kindknoten sein müsste. Aber das muss nicht sein. Einfacher binärer Suchbaum, der aufgebaut wurde mit z.B. einfügen von 5, 3, 5. Der hat dann einen Root mit der 5, links davon ist die 3 und rechts davon dann die zweite 5. Also muss man für jeden Wert tatsächlich den linken Teilbaum weiter betrachten und da dann den Wert ganz rechts....

Aber da ist dann tatsächlich die Frage, ob wir hier noch O(n) haben, weil wir ja bei jedem Knoten dann den linken Teilbaum bis zum "rechten Ende" durchgehen müssen.
 
Suchbäume muss ich mir anschauen ich bin total falsch und bevor das noch "falscher :D" wird höre ich an der Stelle auf und schaue mir morgen erst einmal wieder mit Ruhe die Datenstruktur an.
Danach Zeichne ich mir das Vernünftig wieder hin und wenn es dann immer noch nicht klappt melde ich mich wieder.

Ich wüsste zwar immer noch nicht wie das gehen soll ohne etwas zu speichern aber naja :D

LG
 
Denn beim insert erkenne ich ja x.compareTo(x) == 0 :) also doppelt füge Element x immer Links ein oder Rechts :p
Links, denn der aktuelle Knoten muss ja größer oder gleich sein. Würdest du rechts einfügen, wäre er ja kleiner.
Wollte es an einem kleineren Baum einfach nochmal versuchen doch wie gesagt wo soll den nun das doppelte Element hin?
Wurzel: 7 linkes Blatt 3 rechtes Blatt 9 nun wieder 7 wohin ?
Die zweite 7 wäre dann der rechte Kindknoten der 3.
 
Code:
Leerer Baum
[]

Einfügen von 10
[10]

Einfügen von 5 und 15
    [10]
  [5]  [15]

Einfügen von 6
      [10]
  [5]      [15]
    [6]

Einfügen von 10

      [10]
  [5]      [15]
    [6]
      [10]
 
Naja dann verstehe ich nur nicht wieso man "nur" in-order durchlaufen muss und wie bekomme ich die alter Informaiton in den rekursien aufruf.

Denke für heute ist schluss ich bekomme gerade rein gar nichts mehr hin!

Java:
public void inorder() {
        inorder(root);
    }

    private void inorder(Node<T> n) {
        if (n != null) {
            inorder(n.getLeft());
            System.out.println(n.toString());
            inorder(n.getRight());
        }
    }
LG
 
Wäre bei der Aufgabenstellung es erlaubt inorder iterativ durch zu laufen und die Knoten dann im Stack eben abzulegen. Dann könnte man es so wie mihe7 sagte machen :)

wenn es rekursiv gehen soll wüsste ich nicht wie ich die Information weitergeben kann.

lg
 
Kannst Du denn sagen, was für eine Information du weitergeben musst? Wozu möchtest Du den die Knoten im Stack ablegen?

Du kannst den Baum inorder durchlaufen? Dann bekommst Du ja alle Werte in aufsteigender Reihenfolge. Und da reicht es dann ja, den aktuellen Knoten mit dem Vorgänger (oder Nachfolger) zu vergleichen.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben