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