Werte aller Child-Nodes in einem Node referenzieren

dominik

Aktives Mitglied
Hi,

ich habe einen Baum, dessen Knoten (Nodes) eine Liste an HTML-Seiten (Pages) beinhalten. Diese Liste enthält alle Pages, die sich direkt im jeweiligen Node befinden.

Nun möchte ich aber nicht nur die Pages speichern, die sich direkt im Node befinden, sondern auch die Pages der Child-Nodes referenzieren:

1600430761592.png


Das Eintragen einer Page in ihrem jeweiligen Node funktioniert recht einfach: Beim Registrieren einer neuen Page wird deren Pfad im Baum aufgelöst, der entsprechende Node wird geladen und zu seiner Liste wird eine Referenz zur Page eingetragen.

Aber wie könnte ich die Page auch in die Liste aller Parent-Nodes eintragen? Gibt es effizientere Methoden, als den Baum "hochzulaufen", oder kennt ihr dafür irgendwelche Tricks? Physikalische Pointer stehen mir zur Verfügung.

Viele Grüße
Dominik
 
Hilf mir mal auf die Sprünge. Die einzelnen Nodes kennen doch bereits die Pages. Sie liegen im Tree darunter. Ich meine, was hast du vor? Wenn du jetzt noch mal alle Referenzen in eine zusätzliche Liste packst und in das Node legst, wo ist der Vorteil? Suchst du eine Seite, so rennst du dann über die Liste statt über den Tree. Hmm. Ich meine, ohne den kompletten Pfad ist das sowieso nie eindeutig. Du könntest sowohl unter fitness sagen wir mal ein preferred haben, als auch unter machines. Dann kennt dein root neben allen anderen noch preferred und noch mal preferred ;) Mit dem kompletten Pfad könntest du einen B-Tree anlegen, der automatisch genauso aussieht wie deine derzeitige Struktur (wenn du bspw den Slash durch '\xFF' ersetzt). Suchen ist dann O(log n) genau wie in einer sortierten Liste. Vielleicht hab ich aber auch einfach nur den Zweck nicht verstanden...
 
Zuletzt bearbeitet:
Die einzelnen Nodes kennen doch bereits die Pages. Sie liegen im Tree darunter. Ich meine, was hast du vor? Wenn du jetzt noch mal alle Referenzen in eine zusätzliche Liste packst und in das Node legst, wo ist der Vorteil?

Ich hätte mein eigentliches Vorhaben besser erklären müssen. Der Grund ist ziemlich banal: Wir sprechen hier von einer Verzeichnisstruktur mit HTML-Seiten, und die Liste von Referenzen auf andere Pages ist tatsächlich eine Übersichtsseite. Auf der Übersichtsseite möchte ich alle Pages sehen, die in diesem und in den darunterliegenden Nodes enthalten sind.

Eine bessere Durchsuchbarkeit erhoffe ich mir dadurch also nicht, vielmehr geht es darum, von einem gegebenen Node aus eine Übersicht über alle darunterliegenden Pages zu ermöglichen. :)
 
Und ein gemeinsam genutzter B-Tree hilft dir nicht? Du müsstest die Nodes nur jeweils "sich selbst" darin suchen lassen und löst dann den Subtree darunter auf. Das Node muss lediglich seinen eigenen Pfad kennen, statt aller Subnodes.
 
Ein gemeinsam genutzter B-Tree sieht auf den ersten Blick nach einer guten Idee aus, die mein Problem lösen könnte. Muss mich aber erstmal in Einfügeoperationen bei B-Trees einlesen und es kann aber gut sein, dass ich dafür mein schönes tree-Package etwas umschreiben muss :D Danke schonmal (y)
 
Wenn du schon einen Tree implementiert hast, reicht das doch vielleicht schon völlig aus. Muss ja kein B-Tree sein. Wie gesagt, wenn das Node seinen eigenen Pfad kennt, dann kannst du ihn auch gezielt in einem Tree herunterlaufen, ohne ihn als Key in einem B-Tree verwenden zu müssen. Das sollte sich IMO nicht signifikant unterscheiden. Kannst ja bspw. den Pfad als (natürlich unsortierte) Liste von Nodes dranhängen. Dann sparst du dir das Tokenizing. Minimalistisch gedacht reicht es sogar wenn jedes Node sein Parent kennt um den Pfad zu ermitteln. Ist dann quasi doppelt (in beide Richtungen) verlinkt, denn seine Children kennt das Node ja bereits. Das erzeugt ggf. etwas mehr Komplexität wenn du damit arbeitest, sollte so etwas wie ein Einfügen von Nodes aber vereinfachen.
 
Zurück
Oben Unten