data-structures - 什么是地图树的最佳数据结构

Question

我正在寻找一种数据结构，它基本上是一棵地图树，其中每个节点的地图都包含一些新元素，以及其父节点地图中的元素。这里的映射是指带有键和值的编程映射，例如 STL 中的 map 或 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 是总数节点上的元素，而不是整个树。

我在想也许我可以使用一个智能哈希函数，但想不出任何东西。

天真的方法是将新添加的条目存储在每个节点的映射中，然后如果找不到任何内容，则向上移动树。我不喜欢这个，因为它取决于树的深度。

Answer 1

创建一个比较哈希图的函数怎么样，无论它们是否匹配，它都会返回真或假，这可能是键和值对排序的一个有点棘手的原因。

然后在向树添加新节点（地图）时使用此功能。检查树中的所有现有节点，如果哈希图已经存在，只需让它指向那个节点。

这可能需要大量处理来比较哈希图，但这将节省大部分空间。

希望这可以帮助。

编辑：您可以在地图上进行联合，看看结果是否相同长度进行比较。

Answer 2

我的理解是您正在寻找'jet'，这将为您提供完整的child1.

您的主要数据将是一棵树。您将保留对该级别所有数据的引用（例如'jet':35，以及指向父级的指针。

引用将通过另一个哈希结构。这会将键 ( 'jet') 映射到指向树的指针。

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

然后可以扩展到

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