Вопрос вряд ли имеет прямую практическую ценность, но всё же...
Мне довольно долго казалось, что в АВЛ-деревьях правила выполнения поворотов совершенно жёсткие и не допускают разночтений (когда какой поворот выполнять).
Только что обнаружил, что в случае с удалениями это не всегда так. Пусть есть дерево:
5
3 8
7 9
(у корня 5 слева — лист 3, справа — поддерево с тремя вершинами).
Удаляя вершину 3, получаем ситуацию
5
8
7 9
к которой возможно применять хоть левый поворот, получая
8
5 9
7
хоть право-левый, получая
7
5 8
9
1) Правда ли это?
2) Есть ли ещё какие-то случаи, когда правила работы с АВЛ-деревьями допускают неоднозначность? (кроме только что упомянутого и кроме того, что при удалении можно брать либо наименьший элемент правого поддерева, либо наибольший элемент левого)