Baumstruktur

werdas34

Bekanntes Mitglied
Hallo,

ich möchte gerne eine Baumstruktur basteln, bestehend aus Wurzel und immer exakt zwei weitere Knoten.

Java:
public class BaumKnoten {

  public double daten;
  public BaumKnoten links;
  public BaumKnoten rechts;
  
  // einfacher Konstruktor
  public BaumKnoten(double n) {
    daten  = n;
    links  = null;   // zeigen noch nirgendwo hin
    rechts = null;
  }

  // Konstruktor mit Zielen
  public BaumKnoten(double n, BaumKnoten l, BaumKnoten r) {
    daten = n;
    links = l;
    rechts = r;
  }
}

Nun möchte ich gerne die Tiefe des Baumes nicht vorher festlegen sondern sagen, wenn man vier eingibt ensteht ein Baum der Tiefe vier.
Allerdings möchte ich jederzeit auf alle Knoten von außen zugreifen können ohne von der Wurzel startend durchgehen zu müssen.

Hier mal zwei Ideen von mir:
1. Wäre möglich einen Baum der Tiefe x zu generien, aber kann nicht auf einen bestimmten Knoten von außen zugreifen.
2. Kann von außen auf die einzelnen Knoten zugreifen, aber schlecht automatisiert die Tiefe x generieren lassen.

Java:
public class Bsp {

    public static void main(String[] args) {
        //1.
        BaumKnoten wurzel1 = new BaumKnoten(0, new BaumKnoten(0), new BaumKnoten(0));
       
        //2.
        BaumKnoten l1 = new BaumKnoten(0);
        BaumKnoten r1 = new BaumKnoten(0);
        BaumKnoten wurzel2 = new BaumKnoten(0, l1, r1);
       
    }

}

Wie geht das was ich vorhabe?

Danke
mfg werdas34
 

httpdigest

Top Contributor
Ich würde mal fast sagen: "Einfach mal einen Baum einer gegebenen Tiefe `n` voranzulegen" ist niemals ein Anwendungsfall für eine Baumstruktur. Was soll denn dann in den Knoten als Daten hinterlegt sein?
Nein, eine Baumstruktur dient vorallererst einmal dazu, den Zugriff auf die enthaltenen Daten effizient zu gestalten. Im Falle eines Binärbaumes (wie du ihn willst), in welchem die Knoten double-Werte enthalten, und die Knoten sortiert sind (left also immer kleiner als right ist) könnte man etwa effizient ermitteln, ob eine bestimmte Zahl im Baum enthalten ist.
Ein Baum ist also in erster Linie eine Datenstruktur, um "Queries" effizient zu implementieren, dadurch, dass die Daten im Baum eine gewissen Ordnung haben. Das gilt übrigens für alle Bäume, die ich so kenne, z.B. auch für Quadtrees oder Octrees in der Computergrafik bzw. der "Computational Geometry", wo man effizientes Indexieren von zweidimensionalen oder dreidimensionalen Punkten oder Flächen/Volumen für effiziente (Überschneidungs-)abfragen und z.B. k-nearest-neighbor realisieren will.
Die Frage ist nun: Welche Art von Query möchtest du mit deinem Baum effizient gestalten?
Die nächsten Punkten, wie etwa das Hinzufügen, Löschen und auch Sortieren der Baumknoten (bzw. Einhalten von Invarianten für die Baumstruktur - z.B. immer eine gewisse "Ausgewogenheit" des Baumes - siehe hierzu z.B. Red-Black-Trees) sollte dann danach implementiert werden, wenn man weiß, was eigentlich der Anwendungsfall für die Baumstruktur ist.
 

werdas34

Bekanntes Mitglied
Du hast Recht.

Stellen wir uns mal einen Binärbaum unendlicher Tiefe vor.
Die Werte sind nicht so entscheidend deswegen sagen wir, wenn das Feld leer sein soll (z.B. durch 0 repräsentiert) stellen wir uns es als weißen Knoten dar. Ist das Feld nicht leer (positiver Wert) dann ist das Feld Schwarz.

Die Wurzel ist immer Schwarz.
Es kann nur das nächstliegende Weiße Feld in Schwarz umgewandelt werden(egal ob man Tiefe oder Breite macht).
Mir ist nur das Gesamtbild aus Schwarzen und Weißen Knoten wichtig. Ich brauche die Zahlen Werte um nacher zu verstehen in welcher Reihenfolge die Knoten umgewandelt werden(sollte eig. auch ein int sein), da dies dann zufällig geschehen soll.

Aber ich möchte dann von einem x-beliebigen Knoten herausfinden, wie viele Schwarze Knoten auf der linken und rechten Seite sind. Erfüllt dies eine Bedingung z.B. links 2 Schwarze und rechts 2 Schwarze ,dann sollte ein Rabbat gegeben werden. Bei 4 - 2 z.B. nicht. Es gilt jedoch der Rabbat von 2 - 2 da ja mindestens 2 Schwarze Knoten auf jeder Seite ist.

Ich brauche keine Sortierung, oder sowas.
Nur eine schöne Ausgabe und die Möglichkeit per Zufall die nächsten Knoten zu markieren.
Alles andere sind dann eigene Methoden.

Hoffe es ist klar geworden.

mfg werdas34
 

Anhänge

  • 20180816_230259-1.jpg
    20180816_230259-1.jpg
    2,2 MB · Aufrufe: 47

mihe7

Top Contributor
Der Sinn des Ganzen erschließt sich mir zwar nicht aber gut:
egal ob man Tiefe oder Breite macht
Deinem Bild nach zu urteilen, ist die Breite des einen die Tiefe des anderen. Wenn Du einen Knoten schwarz färbst, hat dieser also immer einen schwarzen Elternknoten.

D. h. Du kannst eine Menge der schwarzen Knoten verwalten, für die es mindestens noch einen freien Kindknoten (= weiß) gibt. Aus dieser Menge wählst Du einen x-beliebigen Knoten aus, um einen weißen Knoten (= ggf. zufällig gewählter Kindknoten des ausgewählten Knotens) einzufärben.

Sind im Anschluss beide Kindknoten belegt, fliegt der Knoten aus der Menge. Der soeben schwarz gefärbte Kindknoten wird dagegen in die Menge aufgenommen.

Willst Du die Höhe des Baums begrenzen, brauchst Du lediglich die Invariante der Menge um die Tiefe anzupassen.

Das Zählen der schwarzen Knoten läuft dann einfach rekursiv vom gegebenen Knoten aus.
 

werdas34

Bekanntes Mitglied
Mit Tiefe oder Breite wollte ich nur ausdrücken, dass es total egal ist wie die Knoten schwarz werden, es gilt nur die Bedingung das der Eltern-Knoten auch schwarz sein muss.

Ich weiß wie man einen binären Baum bastelt.
Mir gehts darum, dass ich ihn automatisiert erzeugen lasse, was durch BaumKnoten wurzel= new BaumKnoten(4, new BaumKnoten(3), BaumKnoten(2));
Nur kann ich nicht auf den linken Kindknoten von wurzel außerhalb zugreifen, sondern müsste immer durch die Wurzel laufen.
Ich könnte es auch so machen:
BaumKnoten l1 = new BaumKnoten(0);
BaumKnoten r1 = new BaumKnoten(0);
BaumKnoten wurzel2 = new BaumKnoten(0, l1, r1);
Nur wenn ich jetzt eine Tiefe von 10 darstellen möchte, muss ich 1024 knoten hardgecodet hinschreiben. Ist natürlich auch nicht der Sinn der Informatik.

Vorallem, da ich mal eine Tiefe von 7, eine von 12 usw durchtesten möchte, dennoch immer auf jeden Knoten von außen zugreifen möchte. Das ist meine Frage.
Wie ich dann die Methoden schreibe, weiß ich zum Teil. Aber es bringt mir nichts wenn das Grundgerüst fehlt.

Auf dem Bild sieht man das mit den von außen auf Knoten zugreifen:
Der Gelbmarkierte Knoten setzt Methode zählSchwarzeKnotenLinks() und zählSchwarzeKnotenRechts(), und kommt auf das Ergbnis 3 - 2. Nun möchte ich beim Nächsten Knoten dasselbe machen ohne ihn erst von der Wurzel durchlaufen zu müssen sondern einfach sagen können, ich wende bei dem Blauen Knoten diese Methoden an.
Denn ich könnte bei der zweiten Möglichkeit die ich oben erwähnt habe, den Knoten l1 auswählen und dann l1.zählSchwarzeKnotenLinks() ausführen. Das wäre kein Problem.

Ich möchte quasi vereinfacht gesagt, ein Grundgerüst mit nur Weißen Knoten der Tiefe x erzeugen. Sobald dieses steht, laufe ich zufällig durch die Knoten und markiere sie Schwarz wenn sie die Bedingung, ElternKnoten ist auch schwarz markiert, erfüllen. Dann habe ich einen Baum der aus weißen und schwarzen Knoten besteht und darauf wende ich nun die Methoden an.

Ich hoffe ich konnte es verständlich machen.

mfg werdas34
 

Anhänge

  • asd.PNG
    asd.PNG
    144,8 KB · Aufrufe: 39

httpdigest

Top Contributor
Nur wenn ich jetzt eine Tiefe von 10 darstellen möchte, muss ich 1024 knoten hardgecodet hinschreiben.
Natürlich musst du das nicht. Das Erzeugen eines Baumes einer gegebenen Tiefe lässt sich sehr einfach entweder rekursiv oder iterativ lösen. Hier mal eine rekursive Factory-Methode:
Java:
public class BaumKnoten {
  private BaumKnoten links;
  private BaumKnoten rechts;
  public static BaumKnoten makeTreeOfDepth(int depth) {
    BaumKnoten n = new BaumKnoten();
    if (depth > 0) {
      n.links = makeTreeOfDepth(depth - 1);
      n.rechts = makeTreeOfDepth(depth - 1);
    }
    return n;
  }
}
 

mihe7

Top Contributor
Ich möchte quasi vereinfacht gesagt, ein Grundgerüst mit nur Weißen Knoten der Tiefe x erzeugen.
Hat Dir @httpdigest ja schon gezeigt.

Sobald dieses steht, laufe ich zufällig durch die Knoten und markiere sie Schwarz wenn sie die Bedingung, ElternKnoten ist auch schwarz markiert, erfüllen.
Das willst Du nicht tun :)

Nochmal: es müssen nur schwarz markierte Knoten betrachtet werden, die wenigstens einen weißen Kindknoten besitzen. Hat ein solcher, zufällig ausgewählter Knoten zwei weiße Kindknoten, entscheidet der Zufall.

Du nimmst z. B. eine ToDo-Liste, in der anfangs nur die Wurzel steht (sofern der Baum aus wenigstens drei Knoten besteht). Das Färben eines weiteren Knotens läuft dann einfach so ab:
Code:
1. k := zufälliger Knoten aus ToDo-Liste
2. Falls k.links weiß UND k.rechts weiß, dann x := zufälliger Knoten aus {k.links, k.rechts}
3. Sonst: falls k.links weiß, dann x := k.links sonst x := k.rechts
4. färbe x schwarz
5. Falls x kein Blattknoten ist, füge x zur ToDo-Liste hinzu.
6. Falls jetzt alle Kindknoten von k schwarz sind, dann entferne k aus ToDo-Liste

Gefärbt werden kann, so lange es Einträge in der ToDo-Liste gibt.

dennoch immer auf jeden Knoten von außen zugreifen möchte. Das ist meine Frage.
Du brauchst Dir doch nur eine Liste der Baumknoten erstellen.

Java:
import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

public class BaumKnoten {
  private BaumKnoten links;
  private BaumKnoten rechts;
  public static BaumKnoten makeTreeOfDepth(int depth) {
    BaumKnoten n = new BaumKnoten();
    if (depth > 0) {
      n.links = makeTreeOfDepth(depth - 1);
      n.rechts = makeTreeOfDepth(depth - 1);
    }
    return n;
  }
  public void forEach(Consumer<BaumKnoten> c) {
    c.accept(this);
    if (links != null) {
      links.forEach(c);
    }
    if (rechts != null) {
      rechts.forEach(c);
    }
  }
  public List<BaumKnoten> toList() {
    List<BaumKnoten> result = new ArrayList<>();
    forEach(knoten -> result.add(knoten));
    return result;
  }
}

Dann z. B.:

Code:
BaumKnoten wurzel = BaumKnoten.makeTreeOfDepth(10);
List<BaumKnoten> knoten = wurzel.toList();
 

httpdigest

Top Contributor
@mihe7 dein Algorithmus hat mich auf die Idee gebracht, das Erzeugen der weißen Knoten eher lieber lazy zu machen. Man braucht ja streng genommen nur die schwarzen Knoten und die direkten weißen Kinder jedes schwarzen Knotens (um diese schwarz färben zu können).
Auch die Idee mit der ToDo-Liste finde ich gut, würde sie jedoch etwas abändern: Man merkt sich nicht alle schwarzen Knoten mit noch mindestens einem weißen Kind, sondern man merkt sich nur die weißen Knoten, die einen schwarzen Elternknoten haben (also somit schwarz gefärbt werden können). Dann muss man nicht zweimal zufällig auswählen (1. welcher schwarze Knoten ist Kandidat, 2. welcher von seinen möglicherweise noch zwei weißen Kindern soll gefärbt werden) und das Verwalten der ToDo-Liste wird denke ich etwas einfacher (immer einen Kandidaten löschen/nehmen und immer seine zwei Kinder hinzufügen).
Java:
import java.util.*;
public class Tree {
  public static class Node {
    final int depth;
    Node left, right;
    boolean black;
    Node(int depth) {
      this.depth = depth;
    }
  }
  private final Random rnd = new Random();
  private final List<Node> candidates = new ArrayList<>();
  private final int maxDepth;
  private final Node root;
  public Tree(int maxDepth) {
    this.root = new Node(0);
    this.maxDepth = maxDepth;
    candidates.add(root);
    markRandomNodeBlack(); // <- mark root
  }
  public Node markRandomNodeBlack() {
    if (candidates.isEmpty())
      throw new IllegalStateException("All nodes are already black");
    Node candidate = candidates.remove(rnd.nextInt(candidates.size()));
    candidate.black = true;
    if (candidate.depth < maxDepth) {
      candidates.add(candidate.left = new Node(candidate.depth + 1));
      candidates.add(candidate.right = new Node(candidate.depth + 1));
    }
    return candidate;
  }
  public static void main(String[] args) {
    Tree root = new Tree(3); // <- Tree with maximum depth of 3
    for (int i = 0; i < 5; i++) { // <- mark 5 random nodes
      root.markRandomNodeBlack();
    }
  }
}
 

Ähnliche Java Themen

Neue Themen


Oben