При вставке узла в AVL-дерево в зависимости от того, в какую часть дерева до-
бавляется узел, существует четыре варианта балансировки. Методы перебаланси-
рования называются правым и левым вращением, вращением влево-вправо и впра-
во-влево. Сокращено они обозначаются R, L, LR и RL.
Предположим, что вы добавляете новый узел к AVL-
дереву и оно теперь разбалансировано в узле X, как по-
казано на рис. 7.4. На рисунке изображены только узел X
и два его дочерних узла, остальные части дерева обозначе-
ны треугольниками, так как нет необходимости их рассмат-
ривать.
Новый узел может быть вставлен в любое из этих че-
тырех поддеревьев, изображенных в виде треугольников
ниже узла X. Когда вы помещаете новый узел в один из
этих треугольников, необходимо использовать соответ-
ствующий сдвиг для перебалансирования дерева. Но если
вставка нового узла не нарушает упорядоченность дере-
ва, балансировка не нужна. Рис. 7.4. Анализ разбалансированного AVL-дерева
Опубликовал Kest
October 23 2009 07:48:48 ·
0 Комментариев ·
8421 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
