Вопрос вряд ли имеет прямую практическую ценность, но всё же...
Мне довольно долго казалось, что в АВЛ-деревьях правила выполнения поворотов совершенно жёсткие и не допускают разночтений (когда какой поворот выполнять).
Только что обнаружил, что в случае с удалениями это не всегда так. Пусть есть дерево:
5
3 8
7 9
(у корня 5 слева — лист 3, справа — поддерево с тремя вершинами).
Удаляя вершину 3, получаем ситуацию
5
8
7 9
к которой возможно применять хоть левый поворот, получая
8
5 9
7
хоть право-левый, получая
7
5 8
9
1) Правда ли это?
2) Есть ли ещё какие-то случаи, когда правила работы с АВЛ-деревьями допускают неоднозначность? (кроме только что упомянутого и кроме того, что при удалении можно брать либо наименьший элемент правого поддерева, либо наибольший элемент левого)
.
Как бы в данном конкретном случае можно применить два вида балансировок. Я пока не уверен, что в общем случае можно делать и так, и так.
А вообще виды балансировок детерминированы в зависимости от балансов вершин. http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
Как я понял, по указанному адресу всего лишь утверждается: "делать так — правильно". Но не_утверждается "против любого другого способа существует контрпример".
Если я как препод буду заявлять студентам "раз ты при diff[a]=-2, diff[b]=0, diff[c]=0 использовал большой левый поворот вместо малого левого — ты категорически не прав, иди переделывай", то я буду прав или буду сам дурак?
Ну вроде бы все очевидно: можно говорить, что студент не прав, только в том случае, если после его поворота испортилось главное свойство АВЛ-дерева.
А по поводу жесткости правил... Понятно, что они не являются таковыми. Например, в обозначениях, которые приняты по ссылке выше, если (diff[a] = -2, diff[b] = 0, diff[c] = 0), то мы можем применить как малое, так и большое левое вращение (это можно легко проверить, нарисовав высоты, и посмотрев, не нарушается ли основное правило по поводу разности поддеревьев).
Как сказал однажды Капун: "Пиши так, чтобы работало на тестах"
можно говорить, что студент не прав, только в том случае, если после его поворота испортилось главное свойство АВЛ-дерева
Точно ли?
Утрируя в противоположную сторону, рассмотрим ситуацию: пусть задание было сформулировано "сократить дробь
и объяснить процесс". Пусть был дан правильный ответ 
, а в качестве аргументации было сказано "зачеркнём шестёрки". По-Вашему, надо сказать, что решение правильно?
И, да, вопрос о том, что делать, когда это всё проверяется не тестами, а руками.
Up-ну эту старую тему, т.к. вопрос всё ещё интересует.