Ich suche nach einer Datenstruktur, die im Grunde genommen ein Baum von Karten ist, in der die Karte an jedem Knoten einige neue Elemente sowie die Elemente in der Karte des übergeordneten Knotens enthält. Mit map meine ich hier eine Programmierkarte mit Schlüsseln und Werten, wie map in der STL oder dict in Python.
Beispielsweise könnte es einen Wurzelknoten geben:
root = {'car':1, 'boat':2}
und 2 untergeordnete Elemente, die jeweils ein Element zur übergeordneten Zuordnung hinzufügen
child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}
Ich möchte, dass dies so platzsparend wie möglich ist, dh ich möchte nicht an jedem Knoten eine vollständige Kopie der resultierenden Karte speichern, aber im Idealfall wäre die Suche immer noch O (log N), wobei N die Gesamtzahl von ist Elemente am Knoten, nicht der gesamte Baum.
Ich dachte, vielleicht gibt es eine intelligente Hash-Funktion, die ich dafür verwenden könnte, konnte mir aber nichts einfallen lassen.
Der naive Ansatz würde darin bestehen, die neu hinzugefügten Einträge in einer Karte an jedem Knoten zu speichern und dann den Baum nach oben zu verschieben, wenn nichts gefunden wird. Ich mag das nicht, weil es von der Baumtiefe abhängt.
quelle
Antworten:
quelle
Beachten Sie für eine Untergrenze, dass selbst eine stechende Frage so schwer ist wie die des Vorgängers (siehe die Reduzierungen der farbigen Vorgängersuche). Da die obigen Papierreferenzen ein optimales Direktsummenverhalten für die Vorgängersuche zeigen, bedeutet dies, dass der oben beschriebene Algorithmus für jedes Verhältnis zwischen der Anzahl der Knoten und der Gesamtzahl der Schlüssel optimal ist.
quelle