Binäre Bäume (Pascal) < Pascal < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:06 Do 07.04.2005 | | Autor: | LaAlemanita |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Ich habe ein kleines Problem. Wir besprechen in unserem Informatikgrundkurs gerade binäre Bäume und sollen jetzt Porzeduren zum Löschen einzelner Daten schreiben. So weit so gut....ich habe jetzt eine Prozedur geschrieben, die die Zeiger des RECORDS wieder auf NIL setzt, also die auf dem Zeiger gespeicherten Daten löscht. Das ist ja bei den einfachsten Fällen nötig, also wenn das letzte bzw. erste Element gelöscht werden muss, an dem keine andere Elemente mehr dranhängen. Auch kontne ich eine Prozedur schreiben, die den Zeiger auf ein anderes RECORD zeigen lässt, das ist ja für Fälle nötig, wenn noch ein anderer Datensatz an dem Zeiger hängt. Jetzt komm ich aber nicht weiter. Ich schaffe es nicht, eine Prozedur zu schreiben, für den Fall dass das Oberste Element (also an dem alle anderen dranhängen) gelöscht werden soll. Ich weiß nicht, wie ich es anstellen kann, ein neues oberstes Element zu ermitteln, am obersten hängen ja so gut wie immer zwei Datensätze. Welches davon wird nun oberstes? Und wie rück ich dies in einer Prozedur aus? Für Hilfestellungen wäre ich echt dankbar,
liebe Grüße,
Barbara
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:42 Do 07.04.2005 | | Autor: | Lizard |
Ich hab zwar keine Erfahrung mit Pascal, aber die generelle Vorgehensweise ist doch, wenn ich mich recht erinnere, einfach den linken Unterbaum zu nehmen und ganz links unten am rechten Unterbaum einzufügen, oder? Das sähe dann so aus:
4
/ [mm] \backslash
[/mm]
3 5
/ [mm] \backslash
[/mm]
1 2
wird zu
5
/
3
/ [mm] \backslash
[/mm]
1 2
Sollte eigentlich hinkommen, aber vielleicht antwortet ja noch jemand ein bißchen ausführlicher auf die Frage ;)
|
|
|
| |
|
Mh, so weit war ich auch schon mal, ich bekomme nur immer Probleme wenn ich z.B. diesen "Baum" habe:
f
/ [mm] \
[/mm]
c k
/ \ / [mm] \
[/mm]
a e h o
Welches wird dann mein neuer Buchstabe (soll ja alphabetisch geordnet bleiben)? Und was mache ich mit den Buchstaben die dadran hängen? Und wie setzte ich das ganze in pascal um?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:34 Fr 08.04.2005 | | Autor: | Lizard |
> Mh, so weit war ich auch schon mal, ich bekomme nur immer
> Probleme wenn ich z.B. diesen "Baum" habe:
>
> f
> / [mm]\backslash[/mm]
> c k
> / \ / [mm]\backslash[/mm]
> a e h o
>
> Welches wird dann mein neuer Buchstabe (soll ja
> alphabetisch geordnet bleiben)? Und was mache ich mit den
> Buchstaben die dadran hängen? Und wie setzte ich das ganze
> in pascal um?
Hmm, wie kommst du darauf, daß es da eine alphabetische Ordnung geben muß? Die einzige Ordnungseigenschaft von Binärbäumen ist die, daß im linken Unterbaum eines Knotens mit Beschriftung $x [mm] \in \IN$ [/mm] nur Knoten mit Beschriftung kleiner (gleich) $x$ vorkommen, und im rechten Unterbaum nur Knoten mit Beschriftung größer (gleich) $x$.
Wenn du im Beispiel den Unterbaum am Knoten $c$ nimmst, und den an den Knoten $h$ hängst, ist dies gewährleistet - wenn diese Eigenschaft vorher auch schon für den gesamten Baum gehalten hat. Insofern sehe ich nicht ganz dein Problem, zumindest solange du nicht darauf bestehst, daß du beim "Lesen" des Baums von links nach rechts die richtige alphabetische Reihenfolge erhältst. Allerdings gilt durchaus die Aussage, daß alle Buchstaben im linken Unterbaum eines Knotens (z.B. $k$ oder $h$) im Alphabet vor diesem Buchstaben kommen, und alle Knoten in einem rechten Unterbaum im Alphabet nachher kommen - sollte das also gemeint gewesen sein, gibt es da keine Probleme.
Die Buchstaben, die bei einem zu versetzenden Baum "daran" hängen, werden mit umgepflanzt, weil du eben den ganzen Unterbaum verschiebst. Dazu genügt es, die Referenz (oder wie das in Pascal eben heißt), die von $h$ auf dessen linkes Kind zeigt, auf den schon vorher erstellten Knoten $c$ verweisen zu lassen, denn "ab da" stimmt ja alles wieder (d.h. in $c$ und dessen Unterbäumen sind die Referenzen alle richtig gesetzt). Wie das konkret geht, weiß vielleicht jemand anders, deshalb habe ich ja auch bloß eine "Mitteilung" und keine "Antwort" geschrieben.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:06 Sa 09.04.2005 | | Autor: | bazzzty |
> > Welches wird dann mein neuer Buchstabe (soll ja
> > alphabetisch geordnet bleiben)? Und was mache ich mit den
> > Buchstaben die dadran hängen? Und wie setzte ich das ganze
> > in pascal um?
>
> Hmm, wie kommst du darauf, daß es da eine alphabetische
> Ordnung geben muß? Die einzige Ordnungseigenschaft von
> Binärbäumen ist die, daß im linken Unterbaum eines Knotens
> mit Beschriftung [mm]x \in \IN[/mm] nur Knoten mit Beschriftung
> kleiner (gleich) [mm]x[/mm] vorkommen, und im rechten Unterbaum nur
> Knoten mit Beschriftung größer (gleich) [mm]x[/mm].
Wenn man einen solchen Baum vor sich hat, daß liefert ein in-order-Durchlauf der Blätter eine sortierte Ausgabe. Wenn man die Wurzel eines Teilbaumes löscht, läßt sich deshalb diese Eigenschaft am leichtesten erhalten, wenn man das Blatt, was in so einer Ausgabe direkt vor oder nach der Wurzel käme, als neue Wurzel auswählt, also im Beispiel e oder h (als Ersatz für f. Damit läßt sich jedes Löschen auf das Löschen eines Blattes zurückführen.
Zum Nachdenken (bei einer Implementierung) bleibt aber trotzdem noch: Wie bekomme ich dieses Element (schnell), ohne den ganzen Baum zu traversieren, auch wenn der Baum nicht balanciert ist?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:35 Sa 09.04.2005 | | Autor: | Lizard |
Hallo,
> Wenn man einen solchen Baum vor sich hat, dann liefert ein
> in-order-Durchlauf der Blätter eine sortierte Ausgabe. Wenn
> man die Wurzel eines Teilbaumes löscht, läßt sich deshalb
> diese Eigenschaft am leichtesten erhalten, wenn man das
> Blatt, was in so einer Ausgabe direkt vor oder nach der
> Wurzel käme, als neue Wurzel auswählt, also im Beispiel e
> oder h (als Ersatz für f. Damit läßt sich jedes Löschen auf
> das Löschen eines Blattes zurückführen.
Ah ja, du hast natürlich Recht... mein Ansatz wäre zwar nicht falsch gewesen, aber deiner ist sicherlich effektiver, wenn man auf eine geeignete Datenstruktur zurückgreift (und auch eleganter, der Baum wird nicht so stark debalanciert). Ist also wohl besser, es so zu machen!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:45 Sa 09.04.2005 | | Autor: | SEA |
Hallo !
Ich glaube, du hast beim Löschen deines Baumes einen Fehler gemacht!
Es reicht nähmlich nicht zu, die Zeigervariablen auf "nil" zu setzen!!!
Dadurch wird nur der Zeiger auf eine Null-Adresse gesetzt aber der Speicher nicht wieder für andere Daten freigegeben.
Nun bin ich mir aber nicht sicher, ob ich dein Problem richtig verstanden habe:
Willst du das oberste sowie alle daran hängenden Elemente löschen?!
Wenn Ja:
Hierzu ist eine rekursive Prozedur nötig, die den ganzen Baum abklappert und von hinten die Daten löscht (Befehl: dispose()). Normalerweise wird somit auch der Anker (das oberste Element) entfernt.
Ich hoffe ich konnte dir etwas helfen ...
Wenn du deinen Quelltext hier nocheinmal postest, kann ich dich evtl. noch etwas besser unterstützen 
Tschü
|
|
|
|
