Внимательный читатель, услышав слово «дерево» неизбежно вспомнил бы и два других — «логарифм» и «балансировка». И, как всегда, чтобы достичь заветной логарифмической асимптотики придется все таки балансировать наше дерево. Действительно, при нынешнем способе слияния строк внутренняя структура дерева будет похожа скорее на «лестницу», например такую, как на рисунке ниже:
Чтобы этого избежать, будем при каждом объединении строк проверять сбалансированность результата и при необходимости пересобирать все дерево, балансируя его. Хорошее условие сбалансированности — длина строки должна быть не меньше (h+2) — го числа Фибоначчи. Обоснование этого условия а также пара дополнительных модификаций операции склейки были даны Боэмом, Аткинсоном и Плассом в их работе Ropes: an Alternative to Strings
