Изменения

Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>. [[Файл: Avltree1.jpg]] В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.