577
правок
Изменения
→Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше
Корень дерева <tex>\leqslant x</tex>, поэтому он со всем выделенным поддеревом должен отойти в дерево <tex>T_{1}</tex>. По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево <tex>tmpT</tex> (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был <tex>\leqslant x</tex>, <tex>tmpT</tex> становится <tex>T_{1}</tex>. Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень <tex>> x</tex>. Следовательно, строим из него и его правого поддерева <tex>T_{2}</tex> и спускаемся в левое поддерево. Снова корень <tex>\leqslant x</tex>. Строим новое <tex>tmpT</tex> и объединяем его с уже существующим <tex>T_{1}</tex> (рис. 3).
[[Файл:AVL3.jpg|900px|thumb|leftright|Рис. 3. Объединение tmpT и T1.]]
Далее действуем по алгоритму и в итоге получаем (рис. 4):
[[Файл:End.jpg|350px|thumb|right|Рис. 4. АВЛ-деревья после разделения.]]
