Was ist eine optimale Datenstruktur für einen Baum von Karten?

Question

Ich bin auf der Suche nach einer Datenstruktur, die im Grunde ein Baum von Karten ist, wo die Karte an jedem Knoten einige neue Elemente sowie die Elemente in den übergeordneten Knoten enthält Karte. Mit Karte meine ich eine Programmierkarte mit Schlüsseln und Werten, wie map in der STL oder dict in python.

Zum Beispiel könnte es ein Wurzelknoten sein:

root = {'car':1, 'boat':2} 

und 2 Kinder, die jeweils das Hinzufügen eines Elements an die Mutterkarte

child1 = {'car':1, 'boat':2, 'jet':35} 
child2 = {'car':1, 'boat':2, 'scooter':-5} 

Meine Suche wird dann auf den Knoten durchgeführt werden. So gibt beispielsweise child1 ['jet'] 35 zurück, aber root ['jet'] gibt einen nicht gefundenen Fehler zurück.

Ich möchte, dass dies so platzsparend wie möglich ist, dh ich möchte keine vollständige Kopie der resultierenden Karte an jedem Knoten speichern, aber im Idealfall wäre die Suche immer noch O (log N), N ist die Gesamtzahl der Elemente am Knoten, nicht der gesamte Baum.

Ich dachte vielleicht gibt es eine intelligente Hash-Funktion, die ich dafür verwenden könnte, aber konnte nichts finden.

Der naive Ansatz wäre, die neu hinzugefügten Einträge in einer Karte an jedem Knoten zu speichern und dann nach oben zu gehen, wenn nichts gefunden wird. Ich mag das nicht, weil es von der Baumtiefe abhängt.

Answer 1

Wie wäre es mit dem Erstellen einer Funktion, die hashmaps vergleicht, wird es true oder false zurückgeben, ob sie übereinstimmen, dies könnte ein wenig knifflige Ursache für die Reihenfolge der Schlüssel-Wert-Paare sein.

Verwenden Sie diese Funktion dann immer dann, wenn Sie dem Baum einen neuen Knoten (Karte) hinzufügen. Überprüfen Sie alle vorhandenen Knoten in der Baumstruktur und wenn die Hashmap bereits existiert, zeigen Sie einfach auf diese.

Dies kann eine Menge Verarbeitung für den Vergleich von Hashmaps erfordern, aber dies wird den meisten Platz sparen.

Hoffe, das hilft.

bearbeiten: Sie können möglicherweise eine Union auf den Karten und sehen, ob das Ergebnis die gleiche Länge zum Vergleich ist.

Answer 2

Was ich verstehe ist, dass Sie nach 'jet' suchen, und das wird Ihnen die gesamte Liste von child1.

Ihre primären Daten werden ein Baum sein. Sie behalten einen Verweis auf alle Daten auf dieser Ebene (zB 'jet':35, sowie einen Zeiger auf die Eltern.

Die Referenz wird durch eine andere Hash-Struktur. Dies wird den Schlüssel ('jet') auf einen Zeiger auf die Baum.

map['jet'] => {'jet':35, parent:root} 

die dann

map['jet'] => {'car':1, 'boat':2, 'jet':35}