Knoten in einer Baumstruktur eindeutig idendifizieren?
-
du könntest minimal charakteristika von knoten suchen. d.h. die minimal eindeutige nachbarschaft. allerdings muss das bei jedem einfügen eines knotens für alle knoten erneut berechnet werden. und das einzige, was das spart, wäre ein wenig speicherplatz.
wenn du nen binären baum verwendest, ist die pfadoption noch speichersparender. dann reicht nämlich ein bit pro ebene (0 = links, 1 = rechts, oder andersrum ^^).
die frage ist, wofür du die eindeutige identifizierung als bestandteil eines knotens benötigst. davon ausgehend kann man sich dann ne sinnvolle lösung ausdenken.
-
Es geht darum Knoten objelte einer std::list mit std:find zu suchen..
Über die Addressierung hab ich noch probleme, da die adressierung nich mehr eindeutlig ist (vll. weil das Objekt in die bei psuh_back kopiert wird) und so ne andere adresse hat..
-
nicht nur vielleicht, das ist so. wenn du nen objekt in nen container stopfst, wird es kopiert. du könntest natürlich ne adresse (pointer) in den container stecken, die wird dann zwar auch kopiert, verweist aber weiterhin auf das korrekte objekt.
d.h. du könntest eine identitätssuche machen (gleiche adresse -> dasselbe objekt). pointer in einer liste zu verwalten will aber wohl überlegt sein. ein wenig unbedarft verwandt und schon hast du speicherlecks ohne ende.
-
was wäre demnach die bessere lösung? über Adressen, oder über deie Pfad- INT64 Version?
-
Wenn es dir darum geht, den lokal angelegten Knoten mit seiner im Baum abgelegten Kopie gleichzusetzen, dürfte der Pfad auch nicht weiterhelfen (der lokale Knoten hängt nicht im Baum, hat also auch keinen Pfad, auf dem er im Baum gefunden werden kann). Da mußt du schon eine eigene ID definieren und mitführen.
Wenn du nur die Knoten miteinander vergleichen willst, die IM Baum stecken, sollte die Adresse vollkommen ausreichen (und soweit ich deine Baumstruktur noch im Kopf habe, ist sowieso jeder Knoten eindeutig erreichbar).
-
Hallo CStoll.. ich mach jetzt wieder eine neue Version der Baumstruktru,, diesmal sind alle Knoten ind der gleichen liste! wenn ich einen neuen Knoten einfüge, kann ich ahnad der UINT64Pfad daten die postion in der Liste suche an der der neue knoten rein muss.. im moent klappt das ganze sogar.. 
-
BorisDieKlinge schrieb:
Hallo CStoll.. ich mach jetzt wieder eine neue Version der Baumstruktru,, diesmal sind alle Knoten ind der gleichen liste!Und wozu genau brauchst du den Identitätsvergleich? Vergleichst du immer zwei Listenelemente? (wenn ja, reicht der Adressvergleich völlig aus) Oder vergleichst du Listenelemente mit lokal gespeicherten Kopien?
-
nehmen wir an ich hab die Baum struktur
-------- 0------
-------/--\-----
------1----2----
----/ | \-------
---11-12-13-----dann werden diese knoten so gepeicehrt:
0,1,11,12,13,2
will ich nun noch ein kind zum 1 hinzufügen..
muss ich den bereich von 1 -2 travestieren, und vor dem 2 einfügen..
damit ich weil unbabhäng vom knoten name, wann die 2 kommt (Knoten gleicher ebene) muss ich die ebene vergleichen können..
mit adresse geht so was nich..
-
BorisDieKlinge schrieb:
nehmen wir an ich hab die Baum struktur
0 / \ 1 2 / | \ 11 12 13dann werden diese knoten so gepeicehrt:
0,1,11,12,13,2
Ich würde die Knoten vermutlich in Level-Order ablegen (hat den Vorteil, daß Brüder immer direkt hintereinander in der Liste stehen):
0,1,2,11,12,13
Dazu hat jeder Knoten einen Iterator zum Vater, einen auf seinen ersten Sohn und einen hinter seinen letzten Sohn.
will ich nun noch ein kind zum 1 hinzufügen..
muss ich den bereich von 1 -2 travestieren, und vor dem 2 einfügen..
da mußt du überhaupt nichts großartig travarsieren - du nimmst den end_of_children-Iterator von Knoten 1 und fügst den neuen Knoten vor diesem ein.
mit adresse geht so was nich..
Du kannst natürlich auch die list-Iteratoren als Pseudo-Adressen verwenden
-
ohjw CStoll du bringst mich immer wieder auf neue gedanken.. so werd ich nie fertig;)
Meine Struktor funktioniert bisher super.. jetzt schon wieder umkrempeln dauert wieder ewig...
EGAL: hab das gefühl deine Version ist schneller.. beim travestieren und Knoten /löschen/ändern. etc.
ich versuchs mal mit der Level-Order Liste:) danke