基本的にマップのツリーであるデータ構造を探しています。各ノードのマップには、親ノードのマップの要素だけでなく、いくつかの新しい要素が含まれています。ここでのマップとは、STL のマップや Python の dict のような、キーと値を持つプログラミング マップを意味します。
たとえば、ルート ノードがある場合があります。
root = {'car':1, 'boat':2}
および 2 つの子で、それぞれが親マップに要素を追加します
child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}
その後、ノードで検索が実行されます。たとえば、child1['jet'] は 35 を返しますが、root['jet'] は見つからないというエラーを返します。
これを可能な限りスペース効率的にしたいと思います。つまり、結果のマップの完全なコピーを各ノードに保存したくありませんが、理想的にはルックアップは O(log N) であり、N はノードの総数です。ツリー全体ではなく、ノードの要素。
これに使用できるスマートハッシュ関数があるのではないかと考えていましたが、何も思いつきませんでした。
素朴なアプローチでは、新しく追加されたエントリを各ノードのマップに格納し、何も見つからない場合はツリーを上に移動します。木の深さに依存するので、私はこれが好きではありません。
