[Suchalgorithmus] Iterativ in binaerem Baum

Raptor

Ist es moeglich mittels eines iterativen(nicht rekursiv!) Suchverfahrens einen kleinsten/groessten Wert in einem ungeordneten binaeren Baum zu finden?
(Natuerlich in effizienter Weise und nicht durch 10000-fache Schachtelung von Schleifen.)

Dommel

kannst du nicht mit der Breitensuche durch den Baum gehen, die wäre ja nicht rekursiv...

TGGC

Ja. Jeder rekursive Algorithmus kann iterativ formuliert werden.

Bye, TGGC (Wähle deine Helden)

Helium

Ist es moeglich mittels eines iterativen(nicht rekursiv!) Suchverfahrens einen kleinsten/groessten Wert in einem ungeordneten binaeren Baum zu finden?

Und Wieso? Ist dir der Code sonst einfach zu klar und übersichtlich? Oder ist dir einfach nur langweilig?

Korbinian

wenn dir nicht einfällt, nimm dir tggcs rat zu herzen und wandel einfach die rekursion in eine iteration um. der schlüssel zum erfolg ist hierbei die zuhilfenahme eines stacks. mit dem kannst du das "zurückfallen" machen, dass sonst durch die rückgabewerte in der rekursion passieren würde.

Raptor

Helium schrieb:

Ist es moeglich mittels eines iterativen(nicht rekursiv!) Suchverfahrens einen kleinsten/groessten Wert in einem ungeordneten binaeren Baum zu finden?

Und Wieso? Ist dir der Code sonst einfach zu klar und übersichtlich? Oder ist dir einfach nur langweilig?

Darum geht es nicht. Es ist eine mir gestellte Aufgabe.

Helium

Raptor schrieb:

Helium schrieb:

Ist es moeglich mittels eines iterativen(nicht rekursiv!) Suchverfahrens einen kleinsten/groessten Wert in einem ungeordneten binaeren Baum zu finden?

Und Wieso? Ist dir der Code sonst einfach zu klar und übersichtlich? Oder ist dir einfach nur langweilig?

Darum geht es nicht. Es ist eine mir gestellte Aufgabe.

Die Aufgabe ist dann aber mal so richtig Praxisfern.

volkard

Helium schrieb:

Die Aufgabe ist dann aber mal so richtig Praxisfern.

nehmen wir mal einen nicht künstlich ballancierten baum. den nehmen wird, weil zu erwarten ist, daß die eingangsdaten gut zufällig kommen und der baum nicht entartet. außerdem ist die anwendung nirgends zeitkritisch. es kann vorkommen, daß der baum ein wenig entartet, und dann crasht die rekursion.

oder nehmen wir mal an, daß wir für die bahn coden. vor einigen jahren hatte die noch in eigenen programmen rekursion verboten.

in diesem liste ist es nicht total praxisfern, das maximum zu suchen, und dabei rekursion nicht zu wollen.

double findMax(Node* root){
   double max=DBL_MIN;
   stack<Node*> toDo;
   toDo.push_back(root);
   while(!toDo.empty()){
      Node* n=toDo.peek();
      toDo.pop();
      if(n->left) toDo.push_back(left);
      if(n->right) toDo.push_back(tight);
      if(n->value>max)
         max=n->value;
   }
   return max;
}

Dommel

was ja der Breitensuche entspricht...

volkard

Dommel schrieb:

was ja der Breitensuche entspricht...

nee, tiefensuche. breitensuche ging eher so:

double findMax(Node* root){
   double max=DBL_MIN;
   queue<Node*> toDo;
   toDo.push_back(root);
   while(!toDo.empty()){
      Node* n=toDo.peek();
      toDo.pop();
      if(n->left) toDo.push_back(left);
      if(n->right) toDo.push_back(tight);
      if(n->value>max)
         max=n->value;
   }
   return max;
}

Bashar

Das ist doch im Grunde Augenwischerei. Ob du nen Stack selber aufbaust oder auf das zurückgreifst, was die Maschine von sich aus mitbringst ... sprengen kannst du beides. Und die Zeiten, in denen der Stack auf lächerliche Größen eingeschränkt ist, sind vorbei.

Wenn du wirklich iterativ nen Baum durchlaufen willst, wirst du wohl einen gefädelten Baum (heißt das so? threaded tree) verwenden wollen, auch wenn der insgesamt natürlich mehr Speicher zusätzlich verbraucht als der (selbst gemanagte) Rekursionsstack im worst case

volkard

Bashar schrieb:

Das ist doch im Grunde Augenwischerei. Ob du nen Stack selber aufbaust oder auf das zurückgreifst, was die Maschine von sich aus mitbringst ... sprengen kannst du beides. Und die Zeiten, in denen der Stack auf lächerliche Größen eingeschränkt ist, sind vorbei.

auf deinem rechner vielleicht. ich hab nen x86, und da zweigt man vom adressraum (nur 4G) einfach einen festen raum für den stack ab (und zwar pro thread). 1M ist ne übliche größe. und 1G wäre schlichter unfug.
1M ist recht schnell voll. eine klasse stack kennt solche probleme meistens nicht.

TheTester

Bashar schrieb:

gefädelten Baum (heißt das so? threaded tree)

Zumindest wäre so die direkte Übersetzung, bin aber der Meinung man sollte bei "threaded tree" bleiben, da weiß wenigstens jeder was gemeint ist ;).

Ponto

Braucht man dafür einen extra Stack zur Taversierung? Die meisten Datenstrukturen für Bäume haben durch den parent-Zeiger schon einen Stack eingebaut. Und ein Baum ohne parent-Zeiger ist meistens nutzlos. Ein Algorithmus könnte so aussehen:

void traverse(Tree & tree)
{
  Node current = tree.root();
  while (not current.isNull())
  {

    //Eigentliche Arbeit am Knoten erledigen
    //Zum Beispiel min/max Berechnung

    if (not current.left().isNull()) {
       current = current.left();
       continue;
    }
    if (not current.right().isNull()) {
       current = current.right();
       continue;
    }
    while(not current == tree.root())
    {
      Node parent = current.parent();
      if ((current == parent.right()) or parent.right().isNull()) {
        current = parent;
      } else {
        current = parent.right();
        break;
      }
    }
    if (current == tree.root()) break;
  }
}

Edit: Die Abbruchbedingung der inneren Schleife korrigiert.

b7f7

Ponto: ohne stack macht man endlosschleifen.
Wenn man parent von nem linken kind macht ist der nächste schritt zurück.
ne möglichkeit ohne stack ist mit zähler pro node

BTW:
so realitätsfremd ist das garnet. wenn man zB ein iterator gür den baum implementiert solte man das schon iterativ machen.

Ponto

b7f7 schrieb:

Ponto: ohne stack macht man endlosschleifen.
Wenn man parent von nem linken kind macht ist der nächste schritt zurück.
ne möglichkeit ohne stack ist mit zähler pro node

Das verstehe ich grad nicht? Was läuft genau falsch?

b7f7

current=left
->
current=parent
->
current=left

Ponto

b7f7 schrieb:

current=left
->
current=parent
->
current=left

Daraus sehe ich nichts. Also ein Beispiel: Nehmen wir einen Baum mit drei Knoten w,l,r. Eine Wurzel und linkes und rechtes Kind. Der Algorithmus startet an der Wurzel.

Da ein linker Teilbaum existiert wird damit weitergemacht. Dieser hat weder ein linkes noch rechtes Kind, so dass die innere while-Schleife aufgerufen wird. Darin wird parent auf w gesetzt. Da der aktuelle Knoten nicht der rechte ist und der rechte vorhanden ist, wird in den else-Zweig gesprungen. Current wird auf r gesetzt und die innere Schleife verlassen.

In der nächsten Iteration hat current keine Kinder, so dass erneut die innere while-Schleife beginnt. Parent ist wieder w. Da aber current gleich dem rechten Kind ist, wird current auf w gesetzt. Hier ist jetzt ein Fehler, die innere Schleife muss die Traversierung ganz abbrechen, wenn hier current == parent, da er fertig ist.

Ich sehe jedoch keine Endlosschleife.

Dommel

also ich erkenne auch keine Fehler... Habs mal mit nem etwas komplexeren Baum ausprobiert und das hat gefunzt, wenn ich keine Fehler gemacht hab

@b7f7: meinst du das mit dem Zähler so, dass man mitzählt, wie oft man schon in nem Knoten war, so dass man, wenn man zB zum zweiten Mal durch den Baum geht und man im linken Knoten schon 2x war, in den rechten geht (falls vorhanden natürlich...)

Hallo,

ich habe mal eine Frage, ist es schwer/ bzw. möglich einen iterativen Suchalg. zu entwerfen, der das n-kleinste/größte Element in einem Baum findet?
Oder muss man einen Algorithmus schreiben / bzw. eine Funktion für jeden Fall extra? Also für den kleinsten Wert eine Funktion, für den 2.kleinsten Wert eine Funktion, für den 3. größten Wert eine Funktion, oder kann man es auch komprimiert schreiben iterativ für alle Fälle?

Generell wo liegt der Sinn etwas iterativ im Baum zu suchen. Soll es nur trickreicher werden? Der Langeweile entfliehend?

Danke!

Grüße