Binärer Baum - wie durchlaufen?

Shade Of Mine

Hallo Leute!

Ich spiele mich zum ersten mal mit Bäumen - genauer gesagt will ich eine map mit einem binären Baum implementieren. Ganz primitiv - um den Umgang mit Bäumen zu lernen.

get() ist ja relativ simpel:

value_type& get(key_type const& key)
  {
    Node* node=root; //beginne bei wurzel
    while(node)
    {
      if(node->key==key)
        return node->val;
      else if(node->key>key)
        node=node->left;
      else
        node=node->right;
    }
    //ineffizient:
    put(key, value_type()); //erzeuge default objekt
    return get(key); //und returne es
  }

nur die Methode put() bereitet mir kopfzerbrechen:

void put(key_type const& key, value_type const& val)
  {
    Node* node=root;
    while(1)
    {
      if(node->key==key)
      {
        return update(node, val);
      }
      if(node->key>key)
      {
        if(!node->left) //wenn nächster knoten leer, einfügen
        {
          return insert_left(node, key, val);
        }
        node=node->left;
      }
      else
      {
        if(!node->right)
        {
          return insert_right(node, key, val);
        }
        node=node->right;
      }
    }
  }

das ist mir viel zu lang und kompliziert. das muss doch vernünftiger gehen, oder?

kurz zum algo: ich weiss, dass es wahrscheinlich blödsinn ist nur beim ersten passenden knoten einzufügen - da der baum so nicht balanziert ist, aber es ist so schön simpel

Es heisst überall, dass man Bäume am besten rekursiv angeht - nur irgendwie fehlt mir da der Zugang/der Sinn... Oder ist eine map eine Situation wo man ohne Rekursion besser dran ist?

Griffin

Als erstes sei gesagt, put und get sind wohl untypische Bezeichnungen bei Binärbäumen
Zweitens was zur Rekursions beim Einfügen. Also das lässt sich doch wunderbar mit Rekursion lösen. Du hast ja einen Parent und leftChild und rightChild. Du betrachtest als erstes den Elementarfall. Sprich der Baum ist leer. Also neuen Knoten erstellen und leftChild und rightChild auf 0 setzen. Und Inhalt zuweisen.
Rekursionsfall ist demzufolge, wenn der Baum nicht lerr ist. Also schaust du dir den Inhalt des Parent und des einzufügenden Knoten an. Ist dieser größer, Rufst du input() für rightChild auf und andersherum für leftChild. Und fertig ist die Rekursion

RTC

Ja, Bäume durchläuft man am besten rekursiv, ansonsten hast du zuviele unnötige Schleifen drin. Kann jetzt auch nicht ausführlich antworten, nur mal ein Zugang zu dem Problem: rekursiv lösen kannst du das Ganze, indem du put() noch einen Parameter gibst, nämlich die Wurzel des Baumes. Heißt natürlich, dass du die in der aufrufenden Funktion gespeichert haben musst.

So und nun kannst du in put() prüfen: wenn das einzuordnende Blatt kleiner als Wurzel ist, dann rufe put() mit dem Knoten als Argument auf, welcher links von Wurzel liegt, ansonsten mit dem rechten "Sohn". Das machst du solange, bis du zu einem Blatt kommst, dort reservierst du dann Speicher für das neue Blatt und setzt den darauf verweisenden Zeiger entsprechend -> du siehst, schön rekursiv lösbar!

Hoffe, das konnte dir etwas helfen...
Ciao
RTC

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?