Пожалуйста, помогите мне понять LR rotaoin в дереве AVL

Question

Сегодня я изучал деревья AVL в Data Structures, но застрял в понимании поворотов LR и RL. Вращения LL и RR довольно интуитивно понятны и легко запоминаются, но мне кажется, что вращение LR и RL не соответствует здравому смыслу, поэтому мне трудно запоминать их. Должны ли эти вращения быть переполнены или есть какой-либо способ их понять? Книга, которую я читаю (Data Structures от Seymoure Lipschutz) говорит, что вращение LR представляет собой комбинацию вращения RR с последующим вращением LL. Но я не могу подключить его. Вот картина изображена в этой книге:

Между вторым изображением и конечного изображения, что происходит, объясните, пожалуйста, если это возможно с этой картиной. Я думаю, что если я пойму LR, тогда автоматически поймет RL, поскольку оба являются зеркальным отображением друг друга.

Answer 1

Вы не понимаете этого, потому что это неверно, как показано на рисунке. Это не четкое двоичное дерево поиска. 37 не может быть правильным (большим) ребенком 76, потому что он меньше.

Начальная вставка

└── 44 
    ├── (L) 30 
    │ ├── (L) 16 
    │ └── (R) 39 
    │  └── (L) 37 
    └── (R) 76 

После левого поворота на (30): (39) повернется в его родителей [30] место, (39) ребенка с [37] становится 30-х детей.

└── 44 
    ├── (L) 39 
    │ └── (L) 30 
    │  ├── (L) 16 
    │  └── (R) 37 
    └── (R) 76 

После правого поворота на (39): (39) находится в верхней части дерева и (44), становится его право ребенка.

└── 39 
    ├── (L) 30 
    │ ├── (L) 16 
    │ └── (R) 37 
    └── (R) 44 
     └── (R) 76