[Suchalgorithmus] Iterativ in binaerem Baum

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

TGGC

Nein, ist nicht schwer. Geht auch fuer den n-ten Wert, aber irgendwann ist es sinnvoller einfach alle Elemente zu ordnen.

Skym0sh0

TGGC schrieb:

Ja. Jeder rekursive Algorithmus kann iterativ formuliert werden.

Bye, TGGC (Wähle deine Helden)

seit wann denn das?

bei uns in mathe kam mal dran, dass alles iterative durch rekursion berechenbar ist. aber umgekehrt eben nicht...

(mal sehen, wannd er erste kommt und mieser lehrer/prof/dozent sagt xD :D)

SeppJ

Skym0sh0 schrieb:

(mal sehen, wannd er erste kommt und mieser lehrer/prof/dozent sagt xD :D)

Vor sieben Jahren, siehe erste Seite.

Michael E.

Skym0sh0 schrieb:

bei uns in mathe kam mal dran, dass alles iterative durch rekursion berechenbar ist. aber umgekehrt eben nicht...

Spielst du auf LOOP an? Da hast du Recht, weil die Ackermann-Funktion sich nicht mit LOOP berechnen lässt. Die Einschränkung in dieser Sprache ist aber, dass die Zählvariable nicht verändert werden kann (bzw. eine Veränderung keinen Einfluss auf die Anzahl der Iterationen hat). For- und/oder while-Schleifen in gängigen Programmiersprachen haben diese Einschränkung nicht.

TGGC

Skym0sh0 schrieb:

seit wann denn das?

Seit Alan Turing seine Maschine erdacht hat.