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

Я ищу структуру данных, то есть в основном дерево карт, где карта в каждом узле содержит несколько новых элементов, а также элементы в карте своего родительского узла. Под картой здесь я подразумеваю карту программирования с ключами и значениями, например карту в STL или dict в python.

Например, может быть корневой узел:

root = {'car':1, 'boat':2}

и 2 ребенка, каждый из которых добавляет элемент на родительскую карту

child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}

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

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

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

Вы не сказали, что такое запросы, но я предполагаю, что query () принимает узел и ключ и хочет получить соответствующее значение (или ноль, если такого значения не существует). В этом случае, я думаю, что в целом вы не можете сделать лучше, чем хранить отдельную карту в каждом узле. Рассмотрим, например, дерево гусениц, в котором к каждому узлу пути подключен один узел, который разветвлен (всего 2n узлов). Укорени это на одном конце пути. Теперь предположим, что размер юниверса для ключей равен m. Для каждого разветвленного узла v и каждого из m возможных ключей этот ключ может существовать или не существовать в v, и оба будут соответствовать вашему ограничению поддерева. Итак, есть$2^{mn}$ возможности того, существует ли каждый ключ на каждом узле ветвления, поэтому вам нужно mn битов пространства только для хранения необходимой информации.

Прежде всего, я думаю, что вы подразумеваете под «картой», под словарем TCS подразумевается «словарь». Во-вторых, я не понимаю фразу "в идеале поиск все равно будет$O(\log N)$", поскольку в словаре поиск занимает O (1) времени с различными хеш-таблицами. В-третьих, вы не указали, является ли проблема статической или динамической; я предполагаю статическую.

Оптимальная сложность для этой проблемы $\Theta($поиск предшественника), например $O(\lg\lg N)$используя ван Эмде Боаса. Это оптимально, если ваш размер слова$\Theta(\lg n)$; см. http://people.csail.mit.edu/mip/papers/pred/pred.pdf для оптимальных границ предшественника.

Правильный способ решения проблемы - создать одну глобальную хеш-таблицу и работать с иерархией отдельно для каждого ключа в таблице. За один ключ$x$мы знаем узлы, где он появляется. Рассмотрим обход дерева по порядку. Узлы, где$x$появляется определить интервалы в этом порядке. Чтобы определить, является ли$x$ находится в хеш-таблице некоторого узла $v$, вы должны спросить, $v$наносит удар любому сегменту, как определено выше. Это легко сделать с помощью поиска предшественников, где мы строим таблицу предшественников для всех конечных точек интервала.

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