Какова сложность конкатенации сбалансированных канатов?

Question

Я посмотрел на разные документы, и вот информация, которую я собрал:

• Внедрение SGI и C-шнуры не гарантируют конкатенацию времени O(1) для длинных веревок и ~log N глубины для более коротких.
• Различные источники противоречат друг другу. Википедия требует O(1) конкатенации. На этой странице говорится, что конкатенация имеет значение O(1), только когда один операнд мал, а O(log N) в противном случае.

Итак, какова временная сложность конкатенации? Когда выполняется точная перебалансировка, чтобы обеспечить сложность конкатенации при сохранении баланса дерева? Предполагаются ли некоторые конкретные модели использования, когда речь идет об этой сложности?

Answer 1

Статья в Википедии неясна, статья "Веревки: альтернатива струнам", которую она нигде не цитирует, претендует на такой сложный результат.

С другой стороны, в этой недавней работе (Gerth Stølting Brodal, Christos Makris и Kostas Tsichlas) написано: "Чисто функциональные наихудшие случаи, отсортированные по времени, отсортированные списки". У них также есть O(logn) поиск, так что вы действительно можете пометить его как "сбалансированный", хотя я не читал подробности, только результаты.

"Веревка" - это термин, который (относительно) распространен на практике, но не в исследованиях. Вместо этого я искал catenable queues (или списки), особенно исследования, проведенные такими людьми, как Тарджан, Окасаки, Каплан и другие, я думаю, что именно здесь ваш реальный ответ.