Я ищу структуру данных, которая в основном представляет собой дерево карт, где карта в каждом узле содержит несколько новых элементов, а также элементы в карте своего родительского узла. Под картой здесь я подразумеваю карту программирования с ключами и значениями, например карту в STL или dict в 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'] возвращает ошибку not found.
Мне бы хотелось, чтобы это было как можно более эффективным с точки зрения пространства, то есть я не хочу хранить полную копию полученной карты на каждом узле, но в идеале поиск по-прежнему должен быть O (log N), где N будет общее количество элементов в узле, а не все дерево.
Я думал, что, возможно, есть интеллектуальная хеш-функция, которую я мог бы использовать для этого, но ничего не смог придумать.
Наивный подход будет хранить вновь добавленные записи на карте в каждом узле, а затем перемещаться вверх по дереву, если ничего не найдено. Мне это не нравится, потому что это зависит от глубины дерева.