C++ - Wert in einem Baum löschen

[Hans W. (Gast)]

Hi Leute!

Ich muss eine Methode schreiben, die mir einen Wert in einem Suchbaum 
löscht. Ich hab bisher diesen Code geschrieben:

void searchtree1::DeleteValue(object o)
{
  tree_element1* tmpRoot = root;

  tree_element1* pred = SearchPred(root, o);  //liefert Zeiger auf den Vorgänger des zu löschenden Elements
  
  //nach Methode "SearchPred()" steht nun in Variable "root" der Zeiger auf das zu löschende Element
  tree_element1* elemtodel = root;  //Zeiger auf zu löschendes Element setzen


  tree_element1* succ;
  
  if(o <= root->val)
  {
    succ = root->left;
    pred->left = succ;
    //Element löschen; momentan ist das Element nur "ausgehängt"
  }
  else
  {
    succ = root->right;
    pred->right = succ;
    //Element löschen; momentan ist das Element nur "ausgehängt"
  }

  root = tmpRoot;
}


tree_element1* searchtree1::SearchPred(tree_element1* pred, object o)
{
  //Wert im Baum suchen
  if(root->val == o)
  {
    return pred;  //in aufrufender Methode steht nun in Variable "root" der Zeiger auf das zu löschende Element
  }
  else if(o <= root->val)
  {
    pred = root;
    root = root->left;
    
    SearchPred(pred, o);
  }
  else
  {
    pred = root;
    root = root->right;

    SearchPred(pred, o);
  }
}

Nun besteht das Problem, dass die Methode an manchen stellen richtig 
funktioniert, an manchen anderen Stellen aber nicht. Wo sie nicht 
funktioniert, ist immer dann wenn ich die Wurzel eines Teilbaums löschen 
will. Vielleicht könnt ihr mir ja weiterhelfen?

[Klaus W. (mfgkw)]

Hast du dir mal auf einem Papier überlegt, wie man ein Element löscht?
Nach welchen Regeln soll es ablaufen?

Was heißt "funktioniert nicht"?

[Εrnst B. (ernst)]

in *C++* schreibt man das so:

std::set<object> searchtree; // Üblich: red-black-tree, also ein binärer Suchbaum

searchtree.insert(...);
searchtree.erase(...);

Hans Wurst schrieb:
> Ich muss eine Methode schreiben

Wenn's für die Arbeit ist: Der Chef freut sich, wenn du gut getestete 
Std-Bibliotheks-Funktionen verwendest, statt deine teure Arbeitszeit mit 
Selbstimplementieren zu verschwenden.


Wenn's für die Schule ist: Wie geschrieben: Überlegs dir mit Bleistift 
und Papier.

[Karl H. (kbuchegg)]

Fang erst mal damit an, dir eine ORDENTLICHE Suchfunktion zu bauen. Das 
ist doch Unsinn, da den root Member der Klasse als Hilfsvariable 
heranzuziehen.



Das hier

  if(o <= root->val)
  {
    succ = root->left;
    pred->left = succ;
    //Element löschen; momentan ist das Element nur "ausgehängt"
  }
  else
  {
    succ = root->right;
    pred->right = succ;
    //Element löschen; momentan ist das Element nur "ausgehängt"
  }

ist ein wenig zu optimistisch. Mal dir die Situation auf


                             5
                            / \
                           /   \
                          3     8
                         / \
                        /   \
                       1     4

und du willst den Knoten 3 löschen. Dann musst du mit den BEIDEN 
Teilbäumen (der 1 UND der 4) etwas machen. Im Moment hängst du nur den 
linken Sohn um (die 1), aber die 4 (den rechten Sohn) lässt du unter den 
Tisch fallen.

Mal dir die Situation (auch mit noch komplizierteren Bäumen) auf! Wenn 
du sowas noch nie gemacht hast, ist es ziemlich unwahrscheinlich, dass 
du das im Kopf hinkriegst. Das sind nicht einfach nur 3 Anweisungen und 
gut ists. Aus einem binären Suchbaum etwas rauszulöschen ist deutlich 
komplizierter (und viel einfacher, wenn man Suchen und Löschen nicht 
voneinander trennt, sondern als rekursive Lösch-Funktion schreibt). Aber 
erst mal musst du wissen, wie überhaupt das korrekte Ergebnis aussieht. 
Also mal dir ein paar Bäume auf, nimm dir irgendeinen Knoten und 
überlege, wie der korrekte Baum ohne diesen Knoten aussehen muss. Und 
daraus entwickelst du dann deinen Algorithmus, wie du die Lösung nach 
Algorithmus IMMER und ZUVERLÄSSIG bekommst.

  if(o <= root->val)

wie kann denn hier der Fall eintreten, dass o nicht gleich root->val 
ist? Deine Suchfunktion hat dir ja genau den Knoten rausgesucht, für den 
gilt o IST GLEICH dem root->val. An dieser Stelle MUSS daher o gleich 
dem root->val sein. Was anderes ist gar nicht möglich. Es sei denn o ist 
überhaupt nicht im Baum vertreten.

[Klaus W. (mfgkw)]

willst du mal wieder die Noten bekommen? :-)

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:
> willst du mal wieder die Noten bekommen? :-)

dynamische Datenstrukturen sind meine Leidenschaft.

[Klaus W. (mfgkw)]

Deshalb musst du doch nicht wieder andrer Leute Hausaufgaben machen :-)

Bei meinen Leidenschaften darf ich auch nicht einfach andren Leuten das 
Spielzeug wegnehmen...

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:
> Deshalb musst du doch nicht wieder andrer Leute Hausaufgaben machen :-)


Ich versuch ja mich zurückzuhalten.
Aber so ein Code wie da oben ... das tut mir in der Seele weh. Stich mir 
doch gleich ein Messer ins Herz :-)

> Bei meinen Leidenschaften darf ich auch nicht einfach andren Leuten das
> Spielzeug wegnehmen...

Ich weiß, ich weiß.
Aber den wichtigsten Tip darf ich ihm schon geben. Den allerwichtigsten 
Tip. Nimm Papier und Bleistift und verschaff dir erst mal einen 
Überblick darüber wie eigentlich das Ergebnis auszusehen hat und was es 
auf dem Weg dorthin alles zu tun gibt.

[Klaus W. (mfgkw)]

Genau das ist es, was mir an ihm fehlt: er rotzt immer irgendwas hier 
hin und wartet ab, was ihm so präsentiert wird.
Wenn man lange genung blöd fragt, findet sich jemand, der einem die 
Arbeit abnimmt.

Erst denken und erst fragen, wenn man trotz Mühe nicht weiterkommt: 
Fehlanzeige.

Zumal es wirklich genug Info darüber gibt.
Aber selbst suchen wäre ja zuviel verlangt.

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:

> Erst denken und erst fragen, wenn man trotz Mühe nicht weiterkommt:
> Fehlanzeige.


Ich glaub eher es ist wirklich diese 'Papier/Bleistift - wer braucht das 
schon' Sache. So ungefähr weiß ich doch was es zu tun gibt: Knoten 
finden, Knoten aushängen, Knoten löschen. Was muss ich noch mehr wissen? 
Und für den Rest hab ich ja noch meinen Debugger.

Das, gepaart mit einer gewissen Überheblichkeit und die Sache ist 
perfekt: bei dyn. Strukturen fällt man damit auf die Schnauze. 
Unweigerlich. Und zwar richtig.


Ich mein: Binärbaum ist ja noch trivial. Interessanter wirds, wenn der 
dann auch noch balanziert sein soll :-)

[D. I. (Gast)]

Erstmal stellt sich die Frage um was für einen Baum es geht ;)

Heap, Suchbaum, Suffix-Trie?

Rot-Schwarz, AVL, oder einfach der Simple?

Der Kalle und seine dynamischen Datenstrukturen, immer wieder schön zu 
lesen :D

Und immer wieder schlägt man als gestandener Informatiker die Hände über 
dem Kopf zusammen, wie wenig Eigeninitiative die Fragenden zeigen.

Löschen aus nem Suchbaum mit 2 Kindern ist aber auch der schwierigste 
Fall bei der ganzen Sache. Das muss man zugeben

[Karl H. (kbuchegg)]

D. I. schrieb:

> Löschen aus nem Suchbaum mit 2 Kindern ist aber auch der schwierigste
> Fall bei der ganzen Sache. Das muss man zugeben

Zweifellos ist das nicht trivial.
Aber es ist relativ logisch und die anderen 3 Fälle kann man als 
Sonderfälle davon auffassen. Und: man lernt beim Nachdenken darüber ein 
paar Dinge über Suchbäume, die nicht so offensichtlich ins Auge 
springen. Plus einer nützlichen weiteren Baumoperation im Repertoir der 
Funktionen.

Am schwierigsten hab ich bei meinen Studien (damals während meines 
Studiums) es immer gefunden, eine Funktionsorganisation (welches sind 
die Funktionen, welche Aufgabe haben sie, was sollen die Argumente sein, 
was ist der Returnwert)  zu finden, so dass die Basis der Datenstruktur 
(hier die oberste Root) eben kein Sonderfall ist, sondern ganz natürlich 
mitgeht. Natürlich ohne den Hack, da ganz einfach ein kompletten Knoten 
anstelle eines Pointers zu verwenden. Ehrgeiz muss sein. Wen kümmerts 
schon, dass es 3 Uhr früh ist - da hab ich wenigstens meine Ruhe und 
kann mir ansehen, wohin es mich führt, wenn ich eine Änderung dergestalt 
mache, dass .....

[D. I. (Gast)]

Hehe jo,
und wenn man sich dann mit dem Standardzeug genug abgemüht hat, kann man 
übergehen zu den Kloppern wie Ukkonen in Linearzeit und -speicher :D

[Wegstaben V. (wegstabenverbuchsler)]

Karl Heinz Buchegger schrieb:
> Und für den Rest hab ich ja noch meinen Debugger.

Nanu, ein Forums-Mitglied mit Namen Debugger kenne ich gar nicht. Das 
muß wohl heißen "... hab ich noch meinen Buchegger" oder "... hab ich 
noch meinen Dannegger" ;-)))