binärer Suchbaum

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.

hustbaer

314159265358979 schrieb:

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

Die fällt nicht mal auf wie unglaublich überheblich das ist, oder?

unskilled

zu node root; vs. node* root; :
wenn man die 1. variante nimmt, hat man das problem, dass der value_type einen standard-ctor haben muss (oder man ein zusätzliches new bräuchte). und man wird vermutlich nicht drum herum kommen, bevor man den wert des knotens ausliest, zu prüfen, ob ein gültiger wert in value stehen könnte oder nicht...

oder gibts da irgend nen tollen trick?