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

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'] возвращает ошибку not found.

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

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