577
правок
Изменения
→Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше
===Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше===
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>. Предположим, что корень нашего дерева <tex>\leqslant x</tex>. Тогда все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{21}</tex>.
