Поддержание порядка в списке в за раз

15

Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций:

  • singleton: создает список с одним элементом, возвращает указатель на него
  • insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент
  • delete: дает указатель на элемент, удаляет его из списка
  • minPointer: при наличии двух указателей на элементы в одном списке возвращает тот, что ближе к началу списка

Мне известны три решения этой проблемы, которые выполняют все операции за время амортизации . Все они используют умножение.О(1)

Можно ли поддерживать порядок в списке за амортизированное время, не используя арифметические операции вне ?О(1)AС0

jbapple
источник
Умножение только недавно (начиная с Pentium III) было в . Можем ли мы включить решения, которые используют умножение? AС0
AT
Я не думаю, что это правильно. Во-первых, я не думаю, что умножение в . Во-вторых, я не думаю, что конкретные машины, такие как Pentium III, о котором вы упоминаете, имеют какое-либо отношение к вопросу о том, происходит ли умножение в . Наконец, как показано в этом вопросе, я, очевидно, знаю о нескольких алгоритмах, основанных на умножении, для этой проблемы, поэтому добавление большего числа в новый «ответ» никоим образом не улучшит ситуацию. AС0AС0
Jbapple
Нашел где я об этом читал; речь шла о Pentium 4, а не III; и не реализовал умножение, вместо этого обошел его с помощью новой инструкции от этого процессора: М. Торуп, «О реализациях AC0 деревьев слияния и атомных куч», в материалах четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Филадельфия, Пенсильвания, США, 2003, с. 699–707.
AT

Ответы:

6

Да!

Используйте двухуровневую структуру, как описано в конце Раздела 2 статьи Дица и Слеатора. Для верхней структуры используйте дерево козла отпущения. Используя коэффициент баланса, который может быть реализован в (например, ), мы получаем результат.AС02

См. Также упражнение 8.12 из открытых структур данных и «Новый метод балансировки деревьев двоичного поиска» Роуры .

jbapple
источник