地图树的最佳数据结构是什么
我正在寻找一种数据结构，它基本上是一棵地图树，其中每个节点的地图都包含一些新元素，以及其父节点地图中的元素。这里的映射是指带有键和值的编程映射，例如 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 是节点上的元素，而不是整个树。
我在想也许可以使用一个智能哈希函数来实现此目的，但无法想出任何东西。
最简单的方法是将新添加的条目存储在每个节点的映射中，如果没有找到任何内容，则向上移动树。我不喜欢这个，因为它取决于树的深度。
I'm looking for a data structure, that is basically a tree of maps, where the map at each node contains some new elements, as well as the elements in its parent node's map. By map here I mean a programming map with keys and values, like map in the STL or dict in python.
For example, there might be a root node:
root = {'car':1, 'boat':2}
and 2 children, each adding an element to the parent map
child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}
My searches will then be performed on the nodes. So for example child1['jet'] returns 35, but root['jet'] returns a not found error.
I would like this to be as space efficient as possible, ie i don't want to store a complete copy of the resulting map at each node, but ideally the lookup would still be O(log N), N being the total number of elements at the node, not the entire tree.
I was thinking perhaps there is a smart hash function I might use for this, but couldn't come up with anything.
The naive approach would be storing the newly added entries in a map at each node and then move up the tree if nothing is found. I don't like this because it depends on the tree depth.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如何创建一个比较哈希图的函数，无论它们是否匹配，它都会返回 true 或 false，这可能是键和值对排序的一个有点棘手的原因。
然后，每当您向树添加新节点（映射）时，请使用此函数。检查树中所有现有的节点，如果哈希图已经存在，则让它指向该节点。
这可能需要大量处理来比较哈希图，但这将节省大部分空间。
希望这有帮助。
编辑：您也许可以在地图上进行并集，看看结果是否具有相同的长度以进行比较。
How about creating a function that will compare hashmaps, it will return true or false whether they match, this might be a bit tricky cause of ordering of the key and value pairs.
Then use this function whenever you are adding a new node (map) to the tree. Check all the existing nodes in the tree and if the hashmap already exists, just have it point to that one.
This can require a lot of processing for comparing hashmaps but this will conserve most space.
Hope this helps.
edit: You may be able to do a Union on the maps and see if the result is the same length for comparison.
据我所知，您正在寻找
'jet'，这将为您提供child1的整个列表。您的主要数据将是一棵树。您将保留对该级别所有数据的引用（例如
'jet':35，以及指向父级的指针。该引用将通过另一个哈希结构。这将映射键 (
'jet') 到指向树的指针，然后可以将其扩展为
What I understand is that you are looking for
'jet'and that will get you the entire list ofchild1.Your primary data will be a tree. You will keep a reference to all data at that level (eg
'jet':35, as well as a pointer to the parent.The reference will be through another hash structure. This will map the key (
'jet') to a pointer to the tree.Which can then be expanded to