(P5) Remove - ohne Eltern

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

(P5) Remove - ohne Eltern

Beitrag von ^Lara^ »

hej,
nur ne kleine frage....
ich überlege mir gerade, ob ich remove auch ohne eltern hinbekommen kann?!
habt ihr eltern benutzt?
(nur damit ich mich nicht in eine idee verrenne..)

lg lara

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

Beitrag von tgp »

Geht auch ohne - evtl. sind dann halt die "Kinder" nicht null, sondern deren Schlüssel und Daten.

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

Beitrag von ^Lara^ »

ich hoffe ihr könnt mir weiterhelfen.
ich habe noch verständnisprobleme zu this. und objekten...

angenommen ich hab diesen baum:

4711
|
30
|
7

ich will 30 löschen!

ich suche den baum durch bis ich 30 gefunden habe. mein "zeiger" (this.key) ist jetzt bei 30.
und nun wollte ich mir eine methode aufrufen die 4711 und 7 übergeben bekommt und den zeiger von 4711 auf 7 "umstellt".
mein problem ist nun, dass ich ohne ein elternobjekt, nicht mehr auf 4711 zugreifen kann und bei 4711 das linke Kind auf 7 setzen kann.
ich kann ja nicht wieder von der wurzel an nach dem key suchen.. weil mein this. noch auf die 30 zeigt...
ich hoffe ihr könnt mich verstehen.
ich hab noch nie zuvor mit objekten gearbeitet, deswegen bin ich sehr konfus.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Du hast gerade das Problem gefunden, das auftritt, wenn man keine Verweise auf Parent speichert. :)
Im Prinzip musst du bei deiner Suche tatsächlich immer einen Verweis auf das Parent behalten, eben weil du es von der 30 nicht mehr gewinnen kannst. Würde dann in etwa so funktionieren:
Du setzt zu Beginn parent = null und node = root (also 4711). Dann vergleichst du das zu suchende Objekt mit node, wenn sie übereinstimmen, enthält node das zu löschende Objekt und parent die Parent-Node. Wenn sie nicht übereinstimmen, setzt du parent = node und node = dem entsprechenden eigenen Kind, je nachdem, ob das gesuchte Objekt größer oder kleiner ist.
Lästig wird das halt insofern, als du ja unter Umständen beim Löschen eine zweite Node finden musst und von dieser ebenfalls den Parent behalten musst. Deswegen finde ich es eleganter, einen Verweis auf den Parent in jeder Node selbst zu speichern. Aber funktionieren tut es auch ohne, wie geschildert.

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

Beitrag von tgp »

Ich seh da kein Problem - wenn man bei 30 angekommen ist, setzt man einfach den Schlüssel, die Daten und die Kindverweise von 7 einfach auf die entsprechenden Variablen von this.
Auch in den anderen Fällen kommt man ohne parent-Verweis aus.

EisNerd
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 18. Nov 2005 19:54
Wohnort: Heppenheim

Beitrag von EisNerd »

noch einfacher ist einfach die daten aus dem kind in den parent zu kopieren und dann das kind zu löschen und wenn kein kind da ist einfach die daten auf null zusetzen.
... und morgen gehts weiter.

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Beitrag von yourmaninamsterdam »

So ein Daten kopieren sollte man aus Designgründen in Java allerdings nicht zwingend bevorzugen, sondern zu möglichst unveränderbaren Objekten greifen.

secretmojo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 31. Jan 2007 19:30

Beitrag von secretmojo »

tgp hat geschrieben:Ich seh da kein Problem - wenn man bei 30 angekommen ist, setzt man einfach den Schlüssel, die Daten und die Kindverweise von 7 einfach auf die entsprechenden Variablen von this.
Auch in den anderen Fällen kommt man ohne parent-Verweis aus.
gute Idee! Darauf bin ich leider nicht gekommen.
yourmaninamsterdam hat geschrieben:So ein Daten kopieren sollte man aus Designgründen in Java allerdings nicht zwingend bevorzugen, sondern zu möglichst unveränderbaren Objekten greifen.
welche Designgründe meinst du denn genau?

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

secretmojo hat geschrieben:
yourmaninamsterdam hat geschrieben:So ein Daten kopieren sollte man aus Designgründen in Java allerdings nicht zwingend bevorzugen, sondern zu möglichst unveränderbaren Objekten greifen.
welche Designgründe meinst du denn genau?
Es gibt da in C++ so ein zweideutiges Wortspiel: "Only friends may touch your private things". Da kann man Klassen als Freunde definieren, die dann auf private-Felder zugreifen dürfen. Wo ich das gelesen habe, stand aber auch, dass es auf ein "Problem im Design des Programmes" hindeutet, wenn man diese Friends-Sitcom da benötigt.

Hier ist es so ähnlich: Ich denke die Designphilosophie ist auch dann nicht gerade die beste, wenn man anfangen muss, bei komplexeren Operationen von /außen/ anfängt, /in/ einem anderen Objekt rumzumurksen - selbst wenn es der gleichen Klasse angehört (bzw. in Java halt nur dann, denn anders bekommt man ja keinen Direktzugriff auf die private Felder ;) ).
Es mag Ausnahmen geben, wo es gar nicht anders geht, und vielleicht sogar welche, wo es Sinn macht. Und ich muss mich jetzt outen, ich hab es auch so gemacht, dass ich die Daten und den key auf den neuen Knoten umgesetzt habe, einfach weil es schneller ging *g*.
Ich halte dies ehrlich gesagt auch für eine Situation, in der es kein Verstoß gegen das Designprinzip des information hiding (oder wie auch immer das hieß ^^) ist, weil man ja am eigenen Sub-Baum arbeitet und nicht an irgendeinem Baum, der sonstwo herumgeistert und den man so ruinieren könnte.
Also zumindest ist es /vertretbar/, weil die Änderungen ja überschaubar sind und man keine super-komplexe Operationen vornimmt.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Beitrag von yourmaninamsterdam »

Ich empfehle zu diesem Zweck "Effective Java" (http://java.sun.com/docs/books/effective/).

Konkret zu diesem Thema: Item 13 - "Favour Immutability".

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

Ich hab mal das Item 13 im Netz ergoogelt.. weiß nur nicht, ob ich nur einen Auszug gelesen habe oder das volle Item 13.
Mal letzteres angenommen: Wie soll ich mir z.B. eine physikalische Simulation vorstellen, in der die Objekte alle immutable sind? Statik pur, oder? Und selbst wenn man das mit der Dynamik irgendwie hinbekommt...
...nehmen wir mal ein Beispiel aus einer Spiel-Engine: Ein Auto z.B. wird an einer bestimmten Stelle gespawned, am Anfang einer Rallye also am Start.
Jetzt baut man als Spieler irgendwie vollkommen Mist und fährt nach dem dem Start in die Böschung und landet auf dem Kopf - d.h. man möchte nun natürlich gerne automatisch wieder auf die Mitte der Straße zurückgesetzt werden. Sprich das Programm /muss/ doch von /außen/ die Position des Autos neu setzen. Wie soll ich mir das mit immutablen Objekten vorstellen?
Also ich glaube nicht, dass man jedes nur erdenkliche Problem auf einfache Art und Weise ohne setter-Methoden (die bei Immutables ja ausgelassen werden /sollten/) implementiert bekommt.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Beitrag von yourmaninamsterdam »

Das Item besagt "Favour Immutability", nicht "Never Ever Do Anything But Immutability".
In der Problematik mit den Baumknoten sieht es nunmal so aus: Die Lösung, alle Daten der Kinsobjekte in das Elternobjekt zu kopieren macht INHALTLICH das Objekt zu einem anderen (erhält programmiertechnisch aber das alte Objekt).
Das ist unnötig, denn das gewünschte Objekt liegt bereits vor und ist tendenziell statisch.

Die Koordinaten eines Autos in einem Videospiel sind (nicht nur tendenziell) völlig unstatisch. Obwohl man die Bewegung eines Autos sicherlich besser modelliert, indem man eine move() Methode implementiert, anstatt eine setLocation().
Die von dir beschriebene Situation erfordert sicherlich irgendeine Art von Eingriff.
Ist aber wirklich nur bedingt auf Baumknoten zu übertragen.

Das Prinzip "Favour Immutability" sagt nur, dass man aus Deigngründen Unveränderbarkeit vorziehen sollte, wenn man es machen kann. Wenn Daten nunmal in ihrer Natur veränderbar sind, dann ist das nunmal so.

Bei einem Projekt vom Umfang eines Binärsuchbaum ist es letztenendes relativ egal.
In dem konkreten Fall hier ist die Lösung des Kopierens von Daten nunmal sehr schmutzig.
Bei überschaubaren Problemen funktioniert das sicherlich trotzdem einwandfrei. Aber man sollte sich so ein Wissen nicht als Standardverfahren aneignen.

Antworten

Zurück zu „Archiv“