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

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

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

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

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

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

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

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

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

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

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

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

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

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

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