577
правок
Изменения
→Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.
Так как мы запускаем балансировку от высот деревьев <tex>(H - H_{1}) + (H_{1} - H_{2}) + (H_{2} - H_{3}) + /cdots + (H_{k - 1} - H_{k}) = H - H_{k} = O(\log{n})</tex>, где <tex>H_{t}, t = 1 /cdots k</tex> - высоты поддеревьев, которые мы вставили и после которых должны произвести балансировку.
