Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Algorithmen, Datenstrukturen und Klassendesign (https://www.delphipraxis.net/78-algorithmen-datenstrukturen-und-klassendesign/)
-   -   Binärer Suchbaum Knoten entfernen (https://www.delphipraxis.net/172233-binaerer-suchbaum-knoten-entfernen.html)

Fehlersucher 19. Dez 2012 18:58

Binärer Suchbaum Knoten entfernen
 
Hallo,

ich soll einen Teilalgorithmus schreiben, durch welchen ein Knoten aus einem binären Suchbaum entfernt wird.

Der zu entfernende Knoten hat lediglich ein Kind (linke Seite).

Der folgende Code ist Sprachcode um meinen Gedankengang zu veranschaulichen.
Delphi-Quellcode:
var hsuchbaumZWISCHEN, hsuchbaum : TBinärsuchbaum;
... // hier würden noch andere Teile der Prozedur stehen
hsuchbaumZWISCHEN := hsuchbaum.giblinkenBaum;
hsuchbaum.zerstoeren;
hsuchbaum.einfuegen(hsuchbaumZWISCHEN);
... // hier würden noch andere Teile der Prozedur stehen
Tja, nun ist der Code aber falsch, da hsuchbaum.zerstören unglücklicherweise den ganzen Baum zerstört.

Mein Teilalgorithmus ist ein Dreizeiler, aber damit es richtig funktioniert müsste es ein Fünfzeiler sein. :?

Ich habe bruchstückweise noch irgendwie folgendes mitbekommen:
- Es ist ok, wenn hsuchbaum (im Teilalgorithmus) ganz zerstört wird
- Man kommt mit der Zwischenvariable hsuchbaumZWISCHEN aus und braucht keine weitere Variable
- Irgendwie soll man glaube ich den hsuchbaumZWISCHEN verwenden und nach diesem ein Inhaltsobjekt einfügen, oder so

Ich habe gar keine Ahnung, wie man das in einem Fünfzeiler richtig machen soll.

Kann mir jemand (in Sprachcode) helfen?

Gruß

Zacherl 19. Dez 2012 19:19

AW: Binärer Suchbaum Knoten entfernen
 
Im Prinzip ist das Vorgehen ja folgendes:

1) Root Node des Knotens ermitteln
2) Betreffenden Knoten unlinken, indem das entsprechende Left oder Right Feld nil gesetzt wird
3) Je nach Aufgabenstellung die Korrektheit des binären Suchbaums wiederherstellen

Hierdurch entfernst du den Knoten und alle darunterliegenden SubNodes.

Aphton 19. Dez 2012 20:21

AW: Binärer Suchbaum Knoten entfernen
 
Liste der Anhänge anzeigen (Anzahl: 1)
Ich habe mir die Mühe gemacht es schrittweise Anhand eines Bildes erklärt :D Hoffe, dir wird nun klar, wie es funzt.

1. Ein sortierter Binärbaum ist gegeben
2. Der Knoten "25" soll entfernt werden
3. Entfernung des Knotens (left, right & parent merken!)
Weg A
4. Du ermittelst den linkesten Knoten vom rechten Teil (= 30)
Weg B
4. Du ermittelst den rechtesten Knoten vom linken Teil (= 10)
5. Dieser Knoten übernimmt nun einfach all die Werte vom zerstörten Knoten (left/right/parent).
6. Der Knoten, der bei 4 ermittelt wurde, wird im Anschluss mit derselben Routine auch zerstört

Btw. es ist egal, ob du Weg A oder Weg B gehst.
Vlt ist Punkt 6. nicht ganz klar - weil es sein kann, dass dieser Knoten einen Nachbarn hat, muss es nochmal ausgeführt werden.
Denk dir einfach, dass die Knoten 10 und 30 jeweils auch Kinder besitzen [10 besitzt 9 (left) und 30 besitzt 31 (right)]
Noch etwas - ich weiß nicht, wie weit ihr im Unterricht schon seid, aber Schritt 6 verlangt, dass der Algorithmus rekursiv ist!

Edit: @Zacherl
Er meinte, es soll nur ein Knoten entfernt werden. Alle darunterliegenden Subnodes müssen erhalten bleiben!

Furtbichler 19. Dez 2012 20:33

AW: Binärer Suchbaum Knoten entfernen
 
Zitat:

Zitat von Fehlersucher (Beitrag 1196110)
Ich habe gar keine Ahnung, wie man das in einem Fünfzeiler richtig machen soll.

Du hast fast alles richtig gemacht. Du benötigst aber den Vorgänger vom hSuchbaum, um dort dann den ZwischenBaum einzuhängen

Fehlersucher 21. Dez 2012 11:23

AW: Binärer Suchbaum Knoten entfernen
 
@ Aphton:
Danke für die Beschreibung. Aber dies scheint mir zu viel zu sein. Es wurden eigentlich keine Abstände gezählt (man brauchte ja auch keine weitere Variable).

@ Furtbichler:

Zitat:

Du hast fast alles richtig gemacht. Du benötigst aber den Vorgänger vom hSuchbaum, um dort dann den ZwischenBaum einzuhängen
Aber dann bräuchte ich doch eine weitere Variable. Eigentlich sollte ich ja nur mit einer Variablen auskommen.

Könntest du mir einen Teilalgorithmus (als Sprachcode) zur Orientierung geben?

Gruß

Zacherl 21. Dez 2012 15:36

AW: Binärer Suchbaum Knoten entfernen
 
Zitat:

Zitat von Aphton (Beitrag 1196115)
Edit: @Zacherl
Er meinte, es soll nur ein Knoten entfernt werden. Alle darunterliegenden Subnodes müssen erhalten bleiben!

Da bin ich mir nämlich nicht so sicher, wie ich die Aufgabe verstehen darf :D

@Fehlersucher:
Deinem Code oben entnehme ich, dass du ZWISCHEN entfernen willst. Da du ZWISCHEN mit Suchbaum.getLinken() ermittelst, ist Suchbaum selbst folglich die Root Node von ZWISCHEN. In diesem Falle setzt du einfach Suchbaum.left auf nil und zerstörst den vorher ermittelten ZWISCHEN.
Hierbei nochmal der Hinweis, dass dann auch alle Unterknoten von ZWISCHEN gelöscht werden. Willst du das verhindern und trotzdem die Korrektheit des Baums beibehalten, musst du dich an Aphtons Algorithmus halten.

Fehlersucher 21. Dez 2012 20:34

AW: Binärer Suchbaum Knoten entfernen
 
Nein, ZWISCHEN wollte ich nicht entfernen.
ZWISCHEN ist meine Zwischenvariable.

Gruß

Zacherl 22. Dez 2012 17:05

AW: Binärer Suchbaum Knoten entfernen
 
Dann nochmal ein Paar Fragen, um Klarheit zu bekommen:

1) Enthält deine TSuchbaum Klasse eine Funktion getRoot() / getParent() bzw. irgendeine Funktion, die dir die übergeordnete Node zurückgibt?
2) Willst du wirklich nur einen Knoten entfernen und die Elemente, die sich darunterbefinden beibehalten oder sollen die Unterknoten der entfernten Node auch zerstört werden?

Fehlersucher 2. Jan 2013 14:12

AW: Binärer Suchbaum Knoten entfernen
 
Entschuldigung, dass ich so spät schreibe. Hatte einige Zeit nicht mehr reingeguckt.


1) Nein, TSuchbaum enthält keine derartigen Klassen
2) Es soll nur ein Knoten entfernt werden, alle Unterknoten sollen beibehalten werden.

Es ist natürlich fraglich, wie ich die Unterknoten jetzt richtig an den Baum hänge.

Könnte mir jemand Sprachcode etc. zeigen?

Hat jemand vielleicht allgemeinen Sprachcode für eine Löschprozedur von Knoten?

Gruß

Aphton 2. Jan 2013 15:38

AW: Binärer Suchbaum Knoten entfernen
 
Ich versteh nicht, warum du mich ignorierst...
Programmieren sollte es dir keiner!

-.-

Zacherl 2. Jan 2013 17:14

AW: Binärer Suchbaum Knoten entfernen
 
Zitat:

Zitat von Fehlersucher (Beitrag 1197340)
Hat jemand vielleicht allgemeinen Sprachcode für eine Löschprozedur von Knoten?

http://de.wikipedia.org/wiki/Bin%C3%...m#L.C3.B6schen

Fehlersucher 3. Jan 2013 10:17

AW: Binärer Suchbaum Knoten entfernen
 
@ Aphton

Das habe ich nicht. Am 21. Dezember schrieb ich bereits:
Zitat:

@ Aphton:
Danke für die Beschreibung. Aber dies scheint mir zu viel zu sein. Es wurden eigentlich keine Abstände gezählt (man brauchte ja auch keine weitere Variable).
@ Zacherl

Danke für den Link.
In dem Beispiel hat der Knoten, welcher gelöscht wird 2 Kinder. Mein Knoten hat nur ein Kind.
Kann man einfach Teile des Codes aus dem Beispiel vernachlässigen?

Ich habe mich wirklich einige Zeit mit dem Problem beschäftigt, komme einfach aber nicht auf die Lösung.

Gruß

Zacherl 3. Jan 2013 17:29

AW: Binärer Suchbaum Knoten entfernen
 
Zitat:

Zitat von Fehlersucher (Beitrag 1197437)
In dem Beispiel hat der Knoten, welcher gelöscht wird 2 Kinder. Mein Knoten hat nur ein Kind.
Kann man einfach Teile des Codes aus dem Beispiel vernachlässigen?

Da hast du glaube ich nicht ganz richtig gelesen.

Zitat:

Zitat von Wikipedia
Fall A: Zu löschender Knoten hat höchstens ein Kind.

Ist der Knoten ein Blatt (Knoten ohne Kinder), dann wird beim Löschen einfach der Knoten entfernt. Hat der zu löschende Knoten genau ein Kind, wird dieses an die Stelle des zu löschenden Knotens gesetzt.

Fall B: Zu löschender Knoten hat zwei Kinder.

[..]


Furtbichler 4. Jan 2013 08:32

AW: Binärer Suchbaum Knoten entfernen
 
Fehlersucher hat im Unterricht nicht richtig aufgepasst
Zitat:

Zitat von Fehlersucher (Beitrag 1196110)
Ich habe bruchstückweise noch irgendwie folgendes mitbekommen...Irgendwie soll man glaube ich ...Ich habe gar keine Ahnung,

Ich habe eine Lösung, allerdings benötige ich leider 6 Zeilen (man könnte aber 5,4 oder 3 daraus machen). :stupid:

Fehlersucher 5. Jan 2013 11:30

AW: Binärer Suchbaum Knoten entfernen
 
@ Zacherl

Zitat:

Da hast du glaube ich nicht ganz richtig gelesen.
Doch, ich beziehe mich aber auf den Code, welcher weiter unten gegeben ist.

@ Furtbichler

Zitat:

Fehlersucher hat im Unterricht nicht richtig aufgepasst
Das haben wir im Unterricht noch nicht gemacht ...

Zitat:

Ich habe eine Lösung, allerdings benötige ich leider 6 Zeilen (man könnte aber 5,4 oder 3 daraus machen).
Zeig mal :-D

Gruß

Furtbichler 5. Jan 2013 12:02

AW: Binärer Suchbaum Knoten entfernen
 
Zitat:

Zitat von Fehlersucher (Beitrag 1197723)
Zeig mal :-D

:mrgreen:


Alle Zeitangaben in WEZ +1. Es ist jetzt 22:55 Uhr.

Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz