577
правок
Изменения
→Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше
[[Файл:АВВЛ2.jpg|525px||Рис. 2. Создание T'.]]
[[Файл:AVL3.jpg|1350px1250px||Рис. 3. Объединение T' и T1.]]
Далее действуем по алгоритму и в итоге получаем (рис. 4):
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>. Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья.
Алгоритм построения следующий: пусть мы пришли в поддерево <tex>S</tex> с корнем <tex>\leqslant x</tex>. Тогда сольем его с уже построенным на тот момент <tex>T_{1}</tex> (<tex>T_{1}</tex> пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево и <tex>S</tex> <tex>\leqslant x</tex> <tex>T_{1}</tex>). Но так как обычная процедура слияния сливает два АВЛ-дерева, а <tex>S</tex> не является корректным АВЛ-деревом, мы немного ее изменим.
