Проектирование небольших сопоставимых объектов

Question

Введение

Предположим, у вас есть список пар ключ / значение:

(0,a) (1,b) (2,c)

У вас есть функция, которая вставляет новое значение между двумя текущими парами, и вам нужно дать ей ключ, который сохраняет порядок:

(0,a) (0.5,z) (1,b) (2,c)

Здесь новый ключ был выбран как среднее между средним числом ключей ограничивающих пар.

Проблема в том, что в вашем списке могут быть миллионы вставок. Если все эти вставки расположены близко друг к другу, вы можете получить такие ключи, как 2^(-1000000), которые нелегко хранить в любом стандартном или специальном числовом классе.

Проблема

Как разработать систему для генерации ключей, которая:

• Дает правильный результат (больше / меньше, чем) по сравнению со всеми остальными клавишами.
• Занимает только O(logn) память (где n - количество элементов в списке).

Мои попытки

• Сначала я попробовал разные классы чисел. Как дроби и даже полиномиум, но я всегда мог найти примеры, когда размер ключа будет расти линейно с количеством вставок.
• Затем я подумал о сохранении указателей для ряда других клавиш и сохранении отношения «меньше / больше, чем», но для этого всегда требуется минимум 1036 * памяти и времени для сравнения.

Дополнительная информация : в идеале алгоритм не должен прерываться при удалении пар из списка.

Answer 1

Я согласен со снеговиком. Дерево было бы идеальным в этом случае. Красно-черное дерево предотвратит дисбаланс вещей. Однако если вам действительно нужны ключи, я уверен, что вы не сможете добиться большего успеха, чем использование среднего значения ключей по обе стороны от значения, которое вам нужно вставить. Это увеличит длину ключа на 1 бит каждый раз. Я рекомендую периодически перенормировать ключи. Каждый x вставляет или всякий раз, когда вы обнаруживаете, что ключи генерируются слишком близко друг к другу, перенумеруйте все с 1 на n.

Edit: Вам не нужно сравнивать ключи, если вы вставляете по позиции вместо ключа. Функция сравнения для красно-черного дерева просто использует порядок в концептуальном списке, который совпадает с порядком в дереве. Если вы вставляете в позицию 4 в списке, вставьте узел в позиции 4 в дереве (используя упорядочение). Если вы вставляете после определенного узла (например, «а»), это то же самое. Возможно, вам придется использовать собственную реализацию, если какой-либо язык / библиотека, которую вы используете, требует ключ.

Answer 2

Не думаю, что вы можете избежать получения ключей размера O (n) без переназначения ключа во время работы.

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

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