什麼是地圖樹的最佳數據結構

Question

我正在尋找一個數據結構，即基本上是一個地圖樹，其中每個節點的地圖包含一些新元素，以及其父節點中的元素地圖。通過這裏的地圖，我的意思是一個帶有鍵和值的編程地圖，如STL中的地圖或python中的字典。

例如，有可能是一個根節點：

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是該節點上的元素總數，而不是整個樹。

我想也許有一個聰明的哈希函數，我可能會用這個，但不能拿出任何東西。

幼稚的做法是將新添加的條目存儲在每個節點的地圖上，然後在沒有發現任何東西時向上移動樹。我不喜歡這個，因爲它取決於樹的深度。

Answer 1

如何創建一個函數來比較hashmaps，它會返回真或假，無論它們是否匹配，這可能是一個有點棘手的原因，因爲鍵和值對的排序。

然後，只要您將新節點（地圖）添加到樹中，就可以使用此函數。檢查樹中的所有現有節點，如果散列映射已經存在，只需將它指向那個節點。

這可能需要大量的處理來比較hashmaps，但這將節省大部分空間。

希望這會有所幫助。

編輯：您可能能夠在地圖上做一個聯盟，看看結果是否相同的長度進行比較。

Answer 2

我的理解是，您正在尋找'jet'，那會得到整個child1的列表。

您的主要數據將是一棵樹。您將保留對該級別的所有數據的引用（例如，'jet':35以及指向父級的指針

該引用將通過另一個散列結構進行映射，這會將鍵（'jet'）映射到指向樹。

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

然後可以擴展到

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