Binärer Baum - wie durchlaufen?

interpreter

@Shade: Ein ganz nettes Applet zu Bäumen findest du hier:
http://www.seanet.com/users/arsen/avltree.html

Jester

RB Trees liegt eine ähnliche wie den AVL-Bäumen zugrunde. Zu Deutsch heißen sie RS (Rot-Schwarz-Bäume) im Sedgewick sind die zum Beispiel drin.
Für große Datenbestände verwendet man übrigens B-Trees (bzw. in der Praxis eher B+ oder B*), die haben den Vorteil, daß sie nicht so tief werden, dafür aber sehr breit.

MfG Jester

RTC

Ich würde put() so machen (Achtung, nicht getestet!):

Node *put(key_type const& key, value_type const& val, Node *root){
  if(!root)
    return new Node(key,val);
  if(root->key < key)
    root->left=put(key,val,root->left);
  else
    root->right=put(key,val,root->right);
  return root;
}

Weiß jetzt nicht, ob das so stimmt, hatte gestern einen anstrengenden Abend

Nuja, auf jeden Fall sieht das doch schon schön rekursiv aus, nicht? Wenn du jetzt "Node *root" nicht als Parameter einsetzen willst, musst du eben noch eine Schnittstelle zu "put()" programmieren. Wäre also z.B. notwendig, wenn du root in "private" einer Klasse stehen hast. Dann geht es nur über eine Schnittstellenfunktion.

Die preorder/inorder/postorder-Traversierung würde auch so rekursiv gehen:

void inorder(Node *root){
  if(root){
    inorder(root->left);
    cout << root->key << ", ";
    inorder(root->right);
  }
}

Hier inorder: zuerst wird der linke Teilbaum besucht, dann der aktuelle Knoten ausgegeben (die "Wurzel"), dann der rechte Teilbaum. So machen Rekursionen Spaß

RTC

Hier nochmal ein binärer Baum von meiner Homepage (musste ich mal so programmieren). Zwar nicht ganz ausgereift (noch ein paar überflüssige Variablen drin), aber die Rekursionen sieht man schon schön:

http://www.linux-related.de/studium/gdinf/suchbaum_bin.c

Shade Of Mine

RTC schrieb:

Ich würde put() so machen (Achtung, nicht getestet!):

Node *put(key_type const& key, value_type const& val, Node *root){
  if(!root)
    return new Node(key,val);
  if(root->key < key)
    root->left=put(key,val,root->left);
  else
    root->right=put(key,val,root->right);
  return root;
}

thx, das sieht gut aus. Da spar ich mir die Referenzen.

Jester

Das finde ich nicht so schön, weil Du damit einen Teil der Arbeit in die nächsthöhere Rekursionsebene verlegst (nämlich das einhägen des angefügten Teils). Beim auflösen der Aufrufe werden dann lauter unnötige Zuweisungen ausgeführt. Ich finde es mit der Referenz am elegantesten.

MfG Jester

volkard

entgegen der herrschenden meinung finde ich hier rekursion nicht hübsch.

Helium

entgegen der herrschenden meinung finde ich hier rekursion nicht hübsch.

dU ARBEITEST GERNE ITERATIV AUF REKURSIVEN dATENSTRUKTUREN? mIT DER mEINUG STEHST DU WOHL ZIEMLICH ALLEINE HIER.

volkard

Helium schrieb:

dU ARBEITEST GERNE ITERATIV AUF REKURSIVEN dATENSTRUKTUREN? mIT DER mEINUG STEHST DU WOHL ZIEMLICH ALLEINE HIER.

keine bange, das bin ich gewohnt.

Bashar

Zum Glück ist 90% aller Software so schlecht, dass man keine Bange haben muss, wenn man von irgendeiner Mehrheitsmeinung abweicht.

Für was bist du denn jetzt Bashar? Rekursiv oder iterativ?

RTC

Bei vielen Knoten im Baum hat die Rekursion speichertechnische Nachteile, das ist klar!

Bashar

Nur bei entarteten Bäumen, sonst geht die Rekursion nicht besonders weltbewegend tief ...

röhrich

Abhängig von der möglichen Rekursionstiefe und dem damit verbundenen Speicherbedarfs (wirkt sich bekanntlich auch auf die Laufzeit aus) ist manchmal eine iteratives durchlaufen von Bäumen vorteilhafter.

volkard

in sachen laufzeit ist in c++ meist iteration schneller. das liegt aber auch nur an den schwachen compilern. manche probleme, wie die türme von hanoi drängen einem die rekursion so stark auf, daß rekursive lösungen sogar ein wenig schneller als iterative sind. und manche probleme gehen nur rekursiv (ich zähle iteration mit nem künstlichen stack als rekursion).
bei den nicht entarteten bäumen dürfte es fast wie bei den türmen von hanoi liegen.