Какая оптимальная структура данных для дерева карт

Question

Я ищу структуру данных, которая является в основном деревом карт, где карта на каждом узле содержит некоторые новые элементы, а также элементы в родительском узле карта. По карте здесь я имею в виду карту программирования с ключами и значениями, например, карту в 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'] возвращает не найденную ошибку.

Я бы хотел, чтобы это было как можно более эффективно, т. Е. Я не хочу хранить полную копию результирующей карты на каждом узле, но в идеале поиск по-прежнему будет O (log N), N - общее количество элементов в узле, а не все дерево.

Я думал, что есть умная хэш-функция, которую я мог бы использовать для этого, но ничего не мог придумать.

Наивный подход будет хранить вновь добавленные записи на карте на каждом узле, а затем перемещаться по дереву, если ничего не найдено. Мне это не нравится, потому что это зависит от глубины дерева.

Answer 1

Как создать функцию, которая будет сравнивать хешмапы, она вернет true или false, соответствуют ли они, это может быть немного сложной причиной упорядочения пар ключ и значение.

Затем используйте эту функцию всякий раз, когда вы добавляете новый узел (карту) в дерево. Проверьте все существующие узлы в дереве, и если hashmap уже существует, просто укажите его.

Это может потребовать много обработки для сравнения хешмапов, но это сохранит большую часть пространства.

Надеюсь, это поможет.

Редактировать: Вы можете сделать Союз на картах и ​​посмотреть, будет ли результат такой же длины для сравнения.

Answer 2

Я понимаю, что вы ищете 'jet', и это даст вам полный список child1.

Вашими основными данными будут дерево. Вы сохраните ссылку на все данные на этом уровне (например, 'jet':35, а также указатель на родительский.

Ссылка будет через другую структуру хэша. Это отобразит ключ ('jet') указателю на дерево.

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

, который затем может быть расширена до

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