Есть ли какая-либо структура данных карты, которая позволяет быстро объединять?

Question

Существуют ли структуры картографических данных, которые имеют как минимум O(log n) вставку, удаление, доступ и объединение?

Большинство самобалансирующихся бинарных деревьев , таких как AVL-деревья и красно-черные деревья , обладают большинством этих свойств, но я считаю, что они имеют O(n log n) сращивание. Существуют ли структуры данных с более быстрым объединением?

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

Answer 1

Вам нужно дерево для произвольных типов ключей, для которых определено только сравнение, или будет нормально, если оно будет работать только с типами, которые имеют двоичное представление фиксированного размера (int, long, float, double, ... )? Если последнее имеет место, то двоичное основополагающее дерево - это структура данных, которая имеет очень эффективное слияние (O (1), если вам повезет, O (N) в худшем случае).

См. Быстрое слияние целочисленных карт Криса Окасаки и Эндрю Гилла для деталей структуры данных.

Библиотека коллекций Scala содержит реализацию для ints и longs . Все другие типы примитивов java могут быть переведены в int или long, например используя java.lang.Double.doubleToLongBits для Double.

Answer 2

Я бы посмотрел на деревья. Вы, вероятно, в конечном итоге оплатите стоимость слияния по пути, но вы сможете добавить еще одно дерево и отложить стоимость на потом.