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

I ' Мы просмотрели разные статьи и собрали собранную мной информацию:

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

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