AVL Дерево вращения. Разные возможности

Question

AVL Дерево вращения. Разные возможности

У меня есть вопрос относительно вставки в дереве AVL. Я заметил, что в некоторых случаях, например, после вставки элемента родитель и его потомок нарушают условие AVL. Например, здесь https://www.youtube.com/watch?v=EsgAUiXbOBo, мин. 12:50, когда после 1 был вставлен, оба 4 и 3 нарушают условие AVL. У меня вопрос, на каком узле мы должны делать ротацию. Ближайший к корню (в данном случае это сам корень) или тот, который находится дальше всего от корня, как бы мы получили два разных дерева в этих случаях? Или это так или иначе?

-1

c tree avl-tree

Источник

user2986649 23 апр '14 в 11:31

1 ответ

Другие вопросы по тегам c tree avl-tree

user1370600 23 апр '14 в 11:54 2014-04-23 11:54 · Answer 1 · 2014-04-23 11:54

Вращение начинается снизу (вставленный узел).

Рассмотрим балансировку всех узлов до P (включительно). Таким образом, поддерево P идеально сбалансировано. Мы идем к родителю Р (Q). Поддерево Q проверяется и (в конце концов) вращается. Дерево результатов (корень мог измениться, если было выполнено вращение) идеально сбалансировано. Продвиньтесь снова.