returnpred;//in aufrufender Methode steht nun in Variable "root" der Zeiger auf das zu löschende Element
36
}
37
elseif(o<=root->val)
38
{
39
pred=root;
40
root=root->left;
41
42
SearchPred(pred,o);
43
}
44
else
45
{
46
pred=root;
47
root=root->right;
48
49
SearchPred(pred,o);
50
}
51
}
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?
std::set<object>searchtree;// Üblich: red-black-tree, also ein binärer Suchbaum
2
3
searchtree.insert(...);
4
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.
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
1
if(o<=root->val)
2
{
3
succ=root->left;
4
pred->left=succ;
5
//Element löschen; momentan ist das Element nur "ausgehängt"
6
}
7
else
8
{
9
succ=root->right;
10
pred->right=succ;
11
//Element löschen; momentan ist das Element nur "ausgehängt"
12
}
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.
1
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.
Deshalb musst du doch nicht wieder andrer Leute Hausaufgaben machen :-)
Bei meinen Leidenschaften darf ich auch nicht einfach andren Leuten das
Spielzeug wegnehmen...
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.
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.
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 :-)
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
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 .....
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" ;-)))
