577
правок
Изменения
→Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.
Пусть мы пришли в поддерево, корень которого <tex>\leqslant x</tex>. В таком случае этот корень с левым поддеревом должен отойти в дерево <tex>T_{1}</tex>.Поэтому мы делаем следующее: удаляем корень, запоминая его значение. Таким образом мы имеем сбалансированное АВЛ-дерево (бывшее левое поддерево). Делаем новую вершину со значением бывшего корня правым листом самого правого листа и запускаем балансировку. Обозначим полученное дерево за <tex>tmpT</tex>.Если это было первое поддерево, у которого корень был <tex>\leqslant x</tex>, то больше мы ничего не делаем, это и есть <tex>T_{1}</tex>. Иначе нам нужно объединить его с уже построенным <tex>T_{1}</tex>. Для этого мы ищем в дереве <tex>T_{1}</tex> самое правое поддерево высоты равной высоте <tex>tmpT</tex>.
