binärer Suchbaum

ands

Hallo zusammen

Als Übungsaufgabe müssen wir einen binären Suchbaum mit den Operationen einfügen und löschen erstellen.

Das Prinzip eines Baumes verstehen ich in der Theorie vollkommen. Allerdings bin ich noch nicht so geübt im programmieren und arbeite noch nicht so lange mit C++ und kämpfe nun damit dies in einen Code reinzubringen.

Könnte mir jemand ein kleines Beispiel machen (am liebsten gleich in Codeform), wie ich einen Baum erstelle und die Knoten einfügen/entfernen kann?

Wäre superfroh um eure Hilfe!
Gruss

SeppJ

Willkommen im Forum.

Fragen dieser Art haben erfahrungsgemäß wenig Aussicht auf (ernsthafte) Antworten. Bitte lies dir den ersten Link in meiner Signatur gründlich durch und beherzige die Ratschläge.

Mechanics

Du brauchst doch nur etwas googeln... [Sarkasmus]Ich sag jetzt nicht STFW, weil du den Begriff wahrscheinlich nicht ergoogeln könntest ;)[/Sarkasmus]

http://math.hws.edu/eck/cs225/s03/binary_trees/

Erster Treffer bei Google, scheint mir recht brauchbar zu sein.

unskilled

class binary_tree
{
  typedef int value_type;

  binary_tree : root(nullptr)
  {}
  ~binary_tree()
  {
    clear();
  }

  void clear()
  {
    /* ... */
  }

  void insert(value_type to_add)
  {
    /* ... */
  }

  void erase(value_type to_erase)
  {
    /* ... */
  }
private:
  struct node
  {
    binary_tree* root;
    binary_tree* left, right;
    value_type value;

    node(binary_tree* root)
    : root(root), left(0), right(0), value()
    {}
  };

  node* root;
};

mal ein einfaches grundgerüst - erase sollte ggf. eine andere signatur haben(iterator statt wert übergeben bekommen). aber so ists denke ich erst mal ausreichend.
die algorithmen für erase und insert solltest du bei google leicht finden könnnen. wenn mich nicht alles täuscht, dann bei wikipedia so gar mit erklärung und evtl visualisierung.
clear sollte trivial sein.

bb

314159265358979

für root brauchst du keinen extra Zeiger.

unskilled

314159265358979 schrieb:

für root brauchst du keinen extra Zeiger.

ja, brauch ich nicht - vereinfacht aber vieles. und stört auch nicht.

314159265358979

Vereinfacht nichts, machts nur ineffizienter.

unskilled

314159265358979 schrieb:

Vereinfacht nichts, machts nur ineffizienter.

vereinfacht das löschen enorm, wenn man später mit iteratoren arbeitet - weil es das löschen dann ne konstante laufzeit hat anstatt einer logarithmischen.

314159265358979

node* root;

->

node root;

Michael E.

Das sorgt auch nur dafür, dass man Sonderbehandlungen für den ersten Knoten machen muss.

otze

Pi, implementiere einfach einen Binären Suchbaum. Wenn du willst auch einen ausbalancierten. Dann komm wieder :).

ands

vielen Dank für eure Antworten, das hat mir schon mal super geholfen, obwohl ich die Frage sehr allgemein gestellt habe, hat es mein Problem gut gelöst...hatte nämlich Mühe mit den Referenzen, aber das ist nun ok

noch eine kleine Frage: falls ich will, dass jeder Wert höchstens einmal in meinem Baum vorkommt, muss ich ja jedes Mal prüfen, ob dieser Wert bereits vorhanden ist. Habe dies nun mal mit der normalen "Suche" gemacht. Gäbe es noch eine effizientere Variante?

vario-500

schau dir doch mal den wikipedia artikel an. da steht sogar pseudo code, wie man die suche machen muss.
außerdem glaub ich gibt es hier im forum einen artikel zum binären suchbaum.

icarus2

ands schrieb:

noch eine kleine Frage: falls ich will, dass jeder Wert höchstens einmal in meinem Baum vorkommt, muss ich ja jedes Mal prüfen, ob dieser Wert bereits vorhanden ist. Habe dies nun mal mit der normalen "Suche" gemacht. Gäbe es noch eine effizientere Variante?

Um eine Suche wirst du nicht drumherumkommen. Aber du brauchst bloss einmal durch den Baum zu laufen um einzufuegen:

Wenn du den Schluessel k einfuegen moechtest, dann machst du eine Suche nach dem Schluessel k. Dann koennen zwei Faelle eintreten:

1. Der Schluessel k wird gefunden
Dann gibst du true zurueck und du musst nichts mehr einfuegen.

2. Der Schluessel k wird nicht gefunden
Dann endet die Suche in einem Blatt. Dieses Blatt ist dann auch sogleich die Einfuegestelle und du kannst dir beim Runtergehen im Baum den Vater dieses Blattes merken. Du gibst dann false zurueck und speicherst die Einfuegestelle. Dann musst du im insert nicht erneut nach der Einfuegestelle suchen.

unskilled

314159265358979 schrieb:

node* root;

->

node root;

wenn man in node statt value_type nen ptr nimmt, ja - ansonsten gar nichts gekonnt. und das wiederrum bringt imho nicht so viele vorteile.. eigtl gar keinen...

314159265358979

Michael E. schrieb:

Das sorgt auch nur dafür, dass man Sonderbehandlungen für den ersten Knoten machen muss.

Bevor du so einen Schwachsinn behauptest, zeig eine Implementierung her.

otze schrieb:

Pi, implementiere einfach einen Binären Suchbaum. Wenn du willst auch einen ausbalancierten. Dann komm wieder :).

Au ja. Weil ich ja nichts besseres zu tun habe
Ich muss dir nichts beweisen. Ich muss gar niemandem etwas beweisen.

SeppJ

Du musst niemandem etwas beweisen. Aber wenn du immer recht haben musst, deine Behauptungen aber nicht stützen kannst, dann sinkt deine Glaubwürdigkeit zurecht noch weiter. Wenn das überhaupt noch möglich ist.

Wäh! Wäh ich habe Recht! Aber ich verrate nicht, warum! Wäh Wäh!

Bevor du so einen Schwachsinn behauptest, zeig eine Implementierung her.

Hier hast du deine Chance, dich als brillianter Coder oder als rechthaberischer Drückeberger zu beweisen:

class tree
{
 node *root;
 public:
  void delete(Value_t value)
  {
   delete_node(root, value); 
  }

 private:
  delete_node(Node* &node, Value_t value)
  {
   if (node)
    if (node->value == value)
     {
      // node Wert eines Kindes von *node geben, Baum umhängen, Element freigeben
     }
     else
      // weitersuchen
  }
};

Und jetzt zeig mal ein delete mit node root; und ohne Prüfung, ob das gesuchte Element das root-Element ist.

P.S.: Was übrigens eine ganz brauchbare Idee ist, ist einen

Node node;

als Member zu haben und dann den root-Knoten als *node.parent, front als *node.right und back als *node.left zu haben. Vielleicht lässt du dich davon inspirieren.

Michael E.

314159265358979 schrieb:

Michael E. schrieb:

Das sorgt auch nur dafür, dass man Sonderbehandlungen für den ersten Knoten machen muss.

Bevor du so einen Schwachsinn behauptest, zeig eine Implementierung her.

Du behauptest doch, dass alles besser wird. Dann zeig mal, wie du den Wurzelknoten löschst.

cooky451

delete() könnte man dann doch noch in remove() oder erase() umbenennen.

314159265358979

Na schön. Ich war gerade in Gedanken bei was anderem. Fühlt ihr euch jetzt besser?

SeppJ

cooky451 schrieb:

delete() könnte man dann doch noch in remove() oder erase() umbenennen.

Ach, mal nicht übertreiben, wenn ich fliegend im Foreneditor programmiere.

314159265358979 schrieb:

Na schön. Ich war gerade in Gedanken bei was anderem. Fühlt ihr euch jetzt besser?

Ich glaube, heute werden sich viele rot im Kalender anstreichen.

Ich hatte dir übrigens noch einen Tipp bei mir reineditiert, der wahrscheinlich zu spät kam, als dass du ihn gelesen hättest. An sich finde ich die Grundidee nämlich nicht verkehrt und die GCC-STL macht das auch so. Man muss es eben bloß begründen, wenn man andere des "Schwachsinns" bezichtigt, insbesondere, wenn diese weitaus erfahrener sind, als man selbst.