Я прочитал много источников о деревьях 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
Я запутался, какое вращение является наиболее подходящим здесь и в подобных случаях.