www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Pascal" - Binäre Bäume (Pascal)
Binäre Bäume (Pascal) < Pascal < Programmiersprachen < Praxis < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Pascal"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Binäre Bäume (Pascal): Frage
Status: (Frage) reagiert/warte auf Reaktion Status 
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

        
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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 ;)

Bezug
                
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:36 Fr 08.04.2005
Autor: LaAlemanita

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?

Bezug
                        
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.


Bezug
                                
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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?

Bezug
                                        
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!


Bezug
        
Bezug
Binäre Bäume (Pascal): Rückfrage
Status: (Mitteilung) Reaktion unnötig Status 
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ü

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Pascal"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de