AVL Rotation - какой узел вращать

Question

Я прочитал много источников о деревьях AVL, но не нашел никого, кто бы обращался к этой проблеме: когда дерево AVL становится неуравновешенным, какой узел следует сначала повернуть?

Предполагая, что у меня есть дерево:

10 
/\ 
    5 25 
    /
     20 

, и я пытаюсь добавить 15, как корень и его ребенок 25 будет несбалансированным.

10 
/\ 
    5 25 
    /
     20 
    /
    15 

я мог сделать поворот RR (или один оборот) 25, в результате чего в следующем дереве:

 10 
    /\ 
    5 20 
     /\ 
     15 25 

или вращения RL (двойное вращение) о корне, создавая следующее дерево :

20 
/\ 
    10 25 
/\  
5 15 

Я смущен, о какой повороте наиболее подходит здесь и в подобных случаях.

Answer 1

Правильное вращение здесь. Вращение должно выполняться как можно скорее (как низкое) по мере нарушения правила. Что для 25 здесь.

Высшие вращения сначала не обязательно нарушают правило, а во-вторых, становятся слишком сложными, хотя на первый взгляд это не так.