Простые сбалансированные деревья с O (1) concat?

12

В чисто функциональном худшем случае отсортированные списки с возможностью прокрутки по постоянному времени, Brodal et al. представить чисто функциональные сбалансированные деревья с O (1) сцеплением и O (lg n) вставкой, удалением и поиском. Структура данных несколько сложна.

Существует ли более простое сбалансированное дерево поиска с O (1) сцепленным, функциональным или нет?

jbapple
источник

Ответы:

5

Вы можете тривиально создать структуру данных с амортизированным O (1) временем конкатенации, просто заново вставив все из одного дерева в другое при конкатенации (которая имеет O (n log n)), точно так же, как это было использовано при построении этого дерева в первое место, поэтому общее время по-прежнему O (n log n)), но это обман.

В худшем случае O (1) авторы утверждают, что это была открытая проблема для любой структуры данных, поэтому я не думаю, что вы найдете простой ответ.

Александр Пассос
источник
1
Я не уверен, что Бродал и соавт. означало, что это была открытая проблема даже в эфемерной обстановке. Вы говорите о предложении в аннотации, которое ссылается на "открытую проблему, поставленную Капланом и Тарьяном"? Если так, я думаю, из контекста этой статьи ясно , что K & T говорили, что вопрос был открыт в чисто функциональной структуре.
jbapple
Я скачал статью, но в ней четко говорится, что «Они [K & T] спросили, может ли операция объединения быть реализована за O (1) наихудшее время даже в эфемерной обстановке, поддерживая при этом поиск и обновления в логарифмическом времени».
Blaisorblade
Хороший вопрос, Блейзорблэйд. Я пропустил это предложение.
Jbapple
nO(nlogn)O(nlog2n)
4

Я скачал упомянутую вами статью, и она отвечает «нет», по крайней мере, во время публикации статьи. Это по двум причинам:

  1. бумага требуется для правильного обзора связанных работ, и они делают это во введении, с кратким описанием на рис. 1, которое говорит «нет». По крайней мере, если это было опубликовано на авторитетной конференции, но это выглядит так (Brodal упоминается пару раз в «Чисто функциональных структурах данных» К. Окасаки, ссылка на эту тему).

    Тем не менее, они упоминают в тексте алгоритм с временем поиска O (log n log log n) и конкатенацией за O (1) времени, набросанный в статье K & T из STOC '96. Это может быть интересно для вас.

    • открытая задача K & T, которую они решают, касается словарей с O (1) конкатенацией и O (log N) поиска / вставки / удаления, даже для эфемерных структур.

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

Если бы вопрос имел практическое значение (но не предполагалось), я считаю, что постоянные факторы более важны, чем разница между O (1) и O (log N) (как обсуждалось во введении Седжвика в алгоритмы), поэтому вам нужно искать только ориентиры для варианта использования вашего приложения.

Blaisorblade
источник
ESOP - это авторитетная конференция, если вы это имели в виду.
Чарльз Стюарт
Это был мой вопрос, но для ESA, где опубликована статья, а не ESOP (возможно, вы это имели в виду). Я не был уверен, что смогу положиться на звание конференции. Эта неофициальная рейтинговая страница предполагает, что ЕКА также заслуживает уважения: www3.ntu.edu.sg/home/assourav/crank.htm
Blaisorblade