マップのツリーの最適なデータ構造

Question

私はデータ構造を探しています。基本的にマップのツリーです。各ノードのマップには新しい要素がいくつか含まれています。地図。ここの地図では、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（ログN）ツリー全体ではなくノードでの要素の合計数。

おそらく私はこれに使うスマートハッシュ関数があると思っていましたが、何も思い付きませんでした。

単純なアプローチは、新しく追加されたエントリを各ノードのマップに格納し、何も見つからなければツリーを上に移動することです。私は木の深さに依存するので、これは好きではありません。

Answer 1

ハッシュマップを比較する関数を作成すると、一致するかどうかにかかわらずtrueまたはfalseが返されます。これは、キーと値のペアの順序が少し複雑になることがあります。

新しいノード（マップ）をツリーに追加するときは、この関数を使用します。ツリー内の既存のノードをすべて確認し、ハッシュマップがすでに存在する場合は、それを指し示すようにしてください。

これは、ハッシュマップを比較するために多くの処理が必要になることがありますが、これはほとんどの領域を節約します。

これが役に立ちます。

編集：マップ上でユニオンを実行し、結果が比較のために同じ長さであるかどうかを確認することができます。

Answer 2

私が理解しているのは、'jet'を探しており、それがchild1のリスト全体を取得するということです。

プライマリデータはツリーになります。そのレベルのすべてのデータへの参照を保持します（例：'jet':35）。親へのポインタと同様に

参照は別のハッシュ構造を介して行われます。これにより、キー（'jet'）ツリー。

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

その後、私は理解していない

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