Привет, народ! Добро пожаловать в AVL Trees (упрощенный, названный в честь изобретателей Адельсона-Вельского и Ландиса). Сегодня мы рассмотрим логику и мою собственную реализацию Javascript для вставки значения в двоичное дерево поиска (BST), а затем, при необходимости, будем использовать более строгие правила дерева AVL для балансировки дерева.

Теперь ... что это значит?

Когда я впервые узнал о BST, я был очень взволнован, чтобы сделать свой собственный, и был сильно разочарован, когда узнал, что BST может быть совершенно бесполезным («вырожденным») при сортировке входных данных. Идеальное положение для дерева - иметь корень с равными левой и правой половинами, чтобы минимизировать время поиска, вставки и удаления.

Итак, я решил, что (отчасти) понял концепцию, я создал (базовое) дерево, мне (отчасти) нравятся эти изменяющиеся указатели ... почему бы не попробовать это на себе?

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

AVL Магия Дерева

Деревья AVL - это один из многих типов бинарных деревьев поиска со сбалансированной высотой, отсюда мы и пошли:

к этому:

К моему конструктору BST будут добавлены два разных свойства: ссылка на родительский узел и метод высоты. Высота дерева - это самый длинный путь от корневого узла до любого листового узла. В этом посте мы будем работать исключительно с вставкой узлов и вращением узлов при нарушении правил AVL.

Правила AVL

1. Дерево считается сбалансированным по высоте, если высоты его дочерних деревьев различаются не более чем на 1.

2. коэффициент баланса определяется как целое число в диапазоне [-1, 1], где -1 будет дополнительным узлом в правом дочернем дереве, а 1 - дополнительным узлом слева. дочернее дерево с нечетным количеством узлов.

3. Дерево считается несбалансированным, когда коэффициент балансировки выходит за пределы этого диапазона, и узлы подвергаются вращению, чтобы сбалансировать дерево. Существует 4 различных категории поворота: влево-влево, вправо-влево, вправо-вправо и вправо-влево.

4. Результирующая высота дерева тогда будет log2 (n), что даст время обхода O (log2 (n)).

Теперь, глядя на эти правила, вы можете задаться вопросом: Почему меня это волнует? Зачем прилагать все эти дополнительные усилия только для того, чтобы дерево больше походило на его тезку?

С меньшими наборами данных время поиска для обычного дерева и сбалансированного дерева аналогично, но когда ваши наборы данных становятся глубиной в тысячи узлов или даже десятки тысяч, внезапно диапазон вероятности в лучшем случае составляет O (lg n) и в худшем случае O (n) или обход связанного списка. Благодаря сбалансированному BST вы всегда можете гарантировать время поиска O (lg n) как в среднем, так и в наихудшем сценариях. Я люблю гарантии.

Визуальная логика

Давайте посмотрим на начальный пример создания BST из 20 в качестве корня (шаг 1), а затем вставки следующего: [15, 25, 10, 7]

Правила для BST следующие: если значение меньше или равно корню, перемещаться влево, иначе перемещаться вправо.

Первая вставка (шаг 2) разместит 15 слева от 20.

Эта вторая вставка (шаг 3) разместит 25 справа от 20.

Третья вставка (шаг 4) помещает 10 слева от 15.

Четвертая вставка (шаг 5) помещает 7 слева от 10.

Шаг 5 нарушил правило дерева AVL. Результирующая ситуация заставляет узлы вращаться. Когда корневой узел (15) неуравновешен, и его левая сторона длиннее другой. Вращение будет происходить с более длинной стороны - с левой стороны. Левый узел корня (10) известен как «узловой» узел. Этот узел будет определять, будет ли вращение правым или левым, в зависимости от того, имеет ли он коэффициент балансировки 1. Если он имеет коэффициент балансировки 1, то левая сторона длиннее правой, и эта ситуация известна как left-left, для левого узла в качестве точки поворота, и более длинная левая сторона, которая заставит вправо вращение. Корневой узел переместится в правую сторону узла поворота, а узел поворота будет напрямую присоединен к остальной части дерева. Если узел поворота имел правую сторону, он переместится влево от корневого узла.

Та же ситуация, но с зеркальным отображением, известна как вправо-вправо, вызывая поворот влево.

Два других сценария: влево-вправо и вправо-влево. Будет 2 результирующих поворота вместо одного. , как объяснено ниже:

Противоположная ситуация, если на шаге 5 было помещено 14 вместо 7.

Теперь узел 'pivot' имеет коэффициент балансировки -1, что вызовет левое вращение с использованием узла поворота в качестве корневого узла, а его правого узла в качестве стержень. После этого второе вращение будет вправо с исходным корневым узлом и новым узлом поворота. Оба этих поворота уже были определены выше. Зеркальное отображение приводит к повороту вправо-влево.

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

Теперь перейдем к Javascript.

Логика кодовой базы:

Чтобы определить высоту дерева, рекурсивная функция, определенная как BinarySearchTree.prototype.height, возвращает -1, если корень равен нулю, и в противном случае суммирует максимальную высоту левого и правого поддерева дерева +1. Код определяется ниже:

Имея доступный метод высоты, я могу затем определить коэффициент баланса каждого из моих последующих родительских узлов после вставки листового узла как разницу между ними, определяемую как BinarySearchTree.prototype.balanceFactor:

Часть 1: Вставка листового узла:

Блок кода метода прототипа insert принимает новое значение и выполняет рекурсивный вызов до тех пор, пока не попадет в узел без соответствующего правого / левого. После вставки узла он выполняет эту функцию на узле, который теперь имеет псевдоним root:

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

Часть 2: Налаживание процесса ротации:

Идея здесь в том, что узлы будут перемещаться либо влево, либо вправо (представьте для этого диагональную плоскость 45 градусов) в зависимости от состояния balanceFactor. Четыре поворота учитывают возможные положения несбалансированных ситуаций: первые два определяют, есть ли в несбалансированной ситуации дополнительные узлы слева или справа, а затем рассматривают ту же ситуацию для назначенного узла поворота.

Обратите внимание: поскольку balanceFactor равен ›0 или‹ 0, автоматически будет дочерний узел с обеих сторон, поэтому нет необходимости проверять, существует ли левый или правый корень.

Часть 3: Вращающиеся узлы:

Теперь, когда мы смогли установить направление вращения, мы можем выполнить само вращение. Я создал пример метода rightRotate, чтобы быть понятным, но поскольку существует зеркальный метод для leftRotate, я также реализовал обобщенный метод rotateChoice, который учитывает обе ситуации. Сегодня мы рассмотрим метод rightRotate для ясности.

Здесь нам нужно понять, что BST имеет в своем конструкторе следующее:

И обратите внимание, что для поворота BST требуется узел pivot в дополнение к узлу root из первой части нашего выступления.

Давайте пройдемся по рабочему процессу.

Мы находимся на шаге 5 вставки в дерево, и мы достигли нашего первого несбалансированного сценария: мы вставили 7 в дерево, но теперь balanceFactor нашего дерева выходит за пределы допустимого диапазона. Когда мы выполняем checkAndRotateRoots вверх по дереву от листового узла, мы находим следующее:

7 имеет баланс высоты 0, 10 имеет баланс высоты 1, а 15 имеет баланс высоты 2, что нарушает правило на левой стороне.

Итак, 15 нам нужно будет выполнить rotate.

Теперь мы должны проверить узел поворота, то есть дерево слева 15 (10), баланс высот которого указывает на дополнительный узел слева. Это приводит к 1 повороту: ситуация влево-влево приводит к правому повороту корня в соответствии с наша диаграмма.

А теперь самое интересное: ротация и переназначение! Вот как выглядит эта конкретная ветвь по отдельности:

Как мы видим, между каждым узлом есть несколько ссылок, с которыми мы должны быть осторожны при отключении и повторном подключении ссылок.

Чтобы выполнить поворот вправо, корневой узел (15) переместится вправо, а его поворотный узел (10) займет его место. Это восстановит следующее:

Родитель поворотного узла теперь будет родительским узлом (20), а новый левый родительский узел будет старым поворотным узлом. Правый узел поворота будет старым корневым узлом, а родительский узел старого корневого узла будет узловым узлом или новым корневым узлом. Левый старый корневой узел теперь будет нулевым. Если бы у нового корневого узла изначально был правый дочерний элемент, он стал бы левым старым корневым узлом. Это заботится обо всех включенных отношениях.

Это показано ниже:

То же самое относится и к повороту влево. Для поворотов влево-вправо и вправо-влево каждый из двух поворотов применяет одну и ту же логику.

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

Спасибо, дайте мне знать, если у вас возникнут вопросы!

Сара

Источники: