Включение в сбалансированное дерево

Преимущество AVL -деревьев состоит в их сбалансированности, которая поддерживается соответствующими алгоритмами вставки-удаления.

Процесс включения является почти таким же, как и для бинарного дерева поиска. Осуществляется рекурсивный спуск по левым и правым наследникам, пока не встретится пустое поддерево, а затем производится пробное включение нового узла в этом месте.

1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве.

2. Включить новый узел и определить новый показатель сбалансированности.

3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла.

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

Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balance равен 0). После включения в поддерево нового элемента узел стал перевешивать влево или вправо, в зависимости от того, в какое поддерево было произведено включение. Если элемент был включен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, - то 1.

Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer

Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.

Что умеет делать SeoHammer

— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.

SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.

Зарегистрироваться и Начать продвижение

До включения узла 55

После включения узла 55

Случай 2. Одно из поддеревьев узла перевешивает, и новый узел включается в более легкое поддерево. Узел становится сбалансированным.

До включения узла 55

После включения узла 55

Случай 3. Одно из поддеревьев узла перевешивает, и новый узел включается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balance выходит за пределы -1... 1. Чтобы восстановить равновесие, нужно выполнить поворот.

Повороты

Повороты необходимы, когда родительский узел P становится разбалансированным. Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному повороту двух или трех узлов. Кроме вращения ссылок, следует также изменить соответствующие показатели сбалансированности узлов.

Одинарный поворот вправо происходит тогда, когда родительский узел P и его левый потомок LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым наследником. Бывшее правое поддерево узла LC (ST) присоединяется к P в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла P. Поворот уравновешивает как родителя, так и его левого потомка.

Пример:

Исходное дерево	Показатели сбалансированности до поворота
После поворота	Попытка включить узел 5 в AVL -дерево нарушает AVL -условие для узла 30 и выводит его из равновесия. Одновременно левое поддерево узла 15 (LC) становится перегруженным. Для переупорядочения узлов вызывается одинарный поворот вправо. В результате родительский узел (30) становится сбалансированным, а узел 10 - перевешивающим влево.

Двойной поворот вправо происходит тогда, когда родительский узел (P) становится перевешивающим влево, а его левый потомок (LC) - перевешивающим вправо. NP - корень правого перевешивающего поддерева узла LC. Тогда в результате поворота узел NP замещает родительский узел.

Сервис онлайн-записи на собственном Telegram-боте

Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.

Для новых пользователей первый месяц бесплатно.

Зарегистрироваться в сервисе

Возможны два варианта:

Вставка узла в левое поддерево узла NP
Вставка узла в правое поддерево узла NP

Пример:

Попытка включить узел 25 разбалансирует корневой узел 50. В этом случае узел 20 (LC) приобретает слишком высокое правое поддерево и требует двойной поворот. Новым родительским узлом (NP) становится узел 40. Старый родительский узел становится его правым наследником и присоединяет к себе узел 45, который также переходит с левой стороны дерева.