Binärer Baum - wie durchlaufen?

Shade Of Mine

Du meinst also so?

void input(Node*& node, key_type const& key, value_type const& val)
  {
    if(!node)
      node=new Node(key, val);
    else if(node->key>key)
      input(node->left, key, val);
    else
      input(node->right, key, val);
  }

  void put(key_type const& key, value_type const& val)
  {
    if(!root)
    {
      root=new Node(key, val);
      return;
    }
    input(root, key, val);
  }

zu put und get: es soll ja ne map sein
wie würden denn die passenden operationen bei nem Baum heissen?

Griffin

Shade schrieb:

wie würden denn die passenden operationen bei nem Baum heissen?

Create() - erzeugt den Baum, alternativ Init
Insert() - hinzufügen, alternativ grow *lol*
Delete()
Search()
Traverse() - Inorder, Postorder, Preorder
Balance()
Empty
etc.

Der Code sieht nu auch viel besser aus, oder?! Allerdings würd ich die if's nochmal prüfen Wenn der neue Knoten einen größeren Inhalt hat als das Parent, wird rechts eingefügt

Shade Of Mine

Ist get() so jetzt auch OK?

value_type& get(key_type const& key)
  {
    if(!root)
      put(key, value_type());
    return read(root, key);
  }

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

was die namen betrifft: thx, aber die passen in eine map nicht rein
mit welchem baum ist std::map denn meistens implementiert?

Taurin

void put(key_type const& key, value_type const& val)
  {
    if(!root)
    {
      root=new Node(key, val);
      return;
    }
    input(root, key, val);
  }

put() kannst du kürzen. Das if(!root) {} brauchst du nicht, schau mal nach input()
rein

edit: Und wenn das ganze eine map werden soll, dann musst du doch noch irgendwie
den Fall abfangen, dass key schon vorhanden ist (in input())

Taurin

In get() kannst du dir wieder das entsprechende if sparen. Ansonsten siehts
doch schick aus (solange du keinen Wert auf einen balancierten Baum wert legst).

Shade Of Mine

@Taurin: thx, habs bei mir ausgebessert.

Ein balanzierter Baum wäre natürlich besser. Ich sehe mir gerade AVL Tree an. Ist der OK? Ich bilde mir mal ein gelesen zu haben, dass std::map öfters mit 'RB Trees' implementiert ist. Stimmt das, bzw. was ist ein RB Tree (bzw. wo finde ich etwas darüber)?

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.