Suche Begriff für Breitensuche-artige Baumerstellung

[Stephan++ 0]

Hallo!

Ich muss am kommenden Dienstag einen Vortrag halten, in dem ich u.a. über Bäume reden muss.
In einem Projekt von mir habe ich einen Baum so implementiert, so dass dieser Parallel aufgebaut wird.

Man unterscheidet ja grundsätzlich zwei Arten, wie man einen Baum aufbauen kann. Entweder per Tiefensuche oder per Breitensuche. Wie nennt man das aber, wenn man einen Baum ebenenweise aufbaut? Gibt es dafür überhaupt einen Begriff? Ich finde es ist der Breitensuche sehr ähnlich, bei genauerem hinsehen ist es aber keine Breitensuche.

Zum besseren verständnis habe ich mal ein paar gif Bilder von Wikipedia hochgeladen. (Die letzte Animation habe ich selbst erstellt)

Tiefensuche: http://i.imgur.com/Cgy96.gif
Breitensuche: http://i.imgur.com/q8sLP.gif
Parallelsuche???: http://i.imgur.com/3EyvH.gif

[Th69]

Die Begriffe "Tiefensuche" und "Breitensuche" beziehen sich ja auf die "Suche" und nicht auf das Erstellen.
Was du vllt. meinst: Balancierter Baum?

[icarus2]

Bist du dir sicher, dass du den Baum ebenenweise aufbaust in deinem Algorithmus? Weil dann würde die Anzahl deiner Threads exponentiell wachsen (wenn denn wirklich pro Ebene alles parallel läuft).

Ich nehme an, dass du zu Beginn parallel und nach einer gewissen Zeit sequentiell mit Tiefen- oder Breitensuche weitermachst.

[Stephan++ 0]

Nunja, wenn man es genau nimmt, verhält es sich dann eher doch wie eine Breitensuche.
Ich errechne jede Ebene auf einer CUDA GPU parallel und reiche diese Information dann an die CPU weiter, welche den Baum dann pro Ebene zusammensteckt.

[anbieter]

Eigtl ist das doch genau eine Breitensuche. Die erste Ebene wird doch sicherlich nach einander aufgebaut und dann für jeden Knoten eine rekursive Breitensuche durchgeführt. Der Unterschied ist nur, dass diese Breitensuchen gleichzeitig stattfinden.
Der Anbieter schlägt vor: Parallelisierte Breitensuche (...was für ein knaller Begriff!)

[Bashar]

Strukturell ist es eher eine Tiefensuche. Tiefensuche sieht so aus:

traversiere(k) {
  if (k != null) {
    foreach(c in kinder(k))
      traversiere(c);
    besuche(k);
  }
}

Das Backtracking-Verhalten kommt dabei implizit durch die Stackverwaltung bei der Rekursion zustande. In der vollständig parallelisierten Version sieht der Algorithmus exakt genauso aus, nur dass traversiere(c) sofort zurückkehrt und im Hintergrund in einem eigenen Thread läuft.

[anbieter]

Von Wikipedia

"Hierbei ist zu beachten, dass Breitensuche immer zuerst alle direkt nachfolgenden Knoten bearbeitet, und nicht wie die Tiefensuche einem Pfad in die Tiefe folgt."

Ist das hier nicht genau der Fall?

Für die Knoten 1,2,3,4 auf der ersten Ebene werden nacheinander Threads erzeugt. Also kein direkt rekursiver Aufruf sondern eher sowas wie

foreach(Kind-Knoten)
{
   createThread!!
}

Das Folgen in die Tiefe folgt in den Threads und je nach Dauer des Erstellens evtl. erst nachdem alle Kinder beuscht wurden.

[volkard]

Macht man es nicht rekursiv, sondern mit einem künstlichen Zwischenspeicher, dann ist der Unterschied nur

//tiefensuch-artig
stack todo;

todo.push(root);
while(!todo.is_empty())
{
   aktuell=todo.pop();
   foreach(kind in aktuell.kinder)
   {
      todo.push(kind)
   }
}

versus

//breitensuch-artig
queue todo;

//sonst alles gleich

Oder sag statt stack und queue lieber FIFO und LIFO bzw LILO und FILO.

Die Unbestimmtheit beim Tiefensuch-Code mit Threads ist, in welcher Reihenfolge das liebe Betriebssystem die Threads anstubst. Beides könnte rauskommen.