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

Question

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

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

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

Answer 1

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

С другой стороны, эта недавняя статья(Герт Стёлтинг Бродал, Кристос Макрис и Костас Цихлас) делает : «Чисто функциональный худший случай Сортируемые списки с постоянным временем и возможностью катализации» .У них также есть O (logn) поиск, так что вы действительно можете пометить его как «сбалансированный», хотя я не читал подробности, только результаты.

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