Реализация двоичного дерева поиска в Javascript
Сегодня мы создадим нашу собственную реализацию двоичного дерева поиска, но прежде, чем мы напишем одну строку кода, было бы неплохо сначала понять основы.
Что такое двоичное дерево?
Двоичное дерево - это структура данных, которая, как и связанный список, состоит из узлов.
Узел - это контейнер, в котором хранятся данные. В данном конкретном случае он хранит значение и два указателя, следовательно, binary (2). Каждый указатель будет ссылаться на другой узел, один будет идти влево, другой вправо и так далее, как показано на изображении ниже.
Все деревья начинаются с корня. Это первый узел. У этого узла нет родителей.
Вот несколько полезных терминов, представляющих интерес при работе с деревьями.
Edge: соединение между двумя узлами. (линия на рисунке выше)
Уровень: глубина обнаружения узла. Начинается с 1 от корня и увеличивается после каждого ребра.
Лист: узел, не имеющий дочерних элементов.
Высота дерева. Высота дерева - это количество ребер от корня до самого нижнего узла в дереве.
Идеальное дерево: дерево с одинаковым количеством узлов на каждом уровне. Деревья редко бывают идеальными в реальных приложениях.
Каждый узел в двоичном дереве может иметь два дочерних элемента (левый и правый), один (левый или правый) или ни одного (лист). .
Зачем использовать двоичное дерево поиска (BST)
Чтобы найти значения в дереве, требуется O (ч). Где h - высота дерева. Хотя это все еще быстрее, чем связанный список, мы можем добиться большего.
Двоичные деревья поиска имеют одно большое преимущество перед линейными структурами данных, такими как массивы и связанные списки, и даже перед нелинейными, такими как обычные деревья. BST можно искать за время log (n).
Как это вообще работает?
В обычном двоичном дереве любое значение может идти как влево, так и вправо. Но в BST значения должны быть упорядочены. При вводе нового значения мы начинаем со сравнения значения корня со значением, которое будет вставлено.
Если новое значение меньше значения корня, оно перемещается в левый узел, в противном случае - вправо. Если они равны, он может двигаться в любом направлении, но это зависит от программиста, который его реализует.
Это делается рекурсивно до тех пор, пока не будет достигнут листовой узел. Затем значение вставляется слева или справа в зависимости от последнего сравнения.
Например, значение 12 будет добавлено к предыдущему дереву. Давайте разберемся с этим.
- 12 больше, чем 10, → сдвинуть вправо
- 12 меньше 15 и равно 15, это листовой узел, → сдвинуть влево и прибавить 12
Теперь вы должны начать понимать, почему поиск значений в BST может быть намного быстрее, чем в любой линейной структуре данных.
Возможные недостатки
Что, если мы вставим значения по порядку? Если наше дерево пусто и мы хотим вставить 1, 2 и 3 в указанном порядке, наш BST превратится в прославленный связанный список, что сделает время поиска O (n). (как показано ниже)
Прежде чем мы начнем, отметим следующее
Единственное различие между машинописным текстом и javascript - это объявление типов переменных. В приведенных ниже фрагментах кода код написан на машинописном тексте, но его можно легко превратить в javascript, удалив определения типов.
Например
//in typescript
var addOne(num: number): number {
return num++;
}//in javascript
var addOne(num) {
return num++;
}
Не то чтобы мы этого не делали, давайте копнемся!
Время пачкать руки
Начнем с создания класса, который будет нашим узлом.
Мы видим, что узел имеет три свойства. Значение узла и двух указателей, левого и правого, одного типа.
По умолчанию у узла не будет потомков, отсюда и нулевые значения для обоих указателей.
Создание древовидного класса
Мы видим, что у этого класса есть только свойство root того же типа BinaryNode. Это свойство будет содержать первый узел в нашем дереве.
Вы также можете заметить, что он называется BinaryTreeR. R означает рекурсивный, потому что именно так мы будем реализовывать эту структуру данных.
Вставка значений
При вставке значений возможны два случая.
В рекурсивном методе мы начинаем двигаться вниз по дереву (начиная с корня), выбирая перемещение влево или вправо в зависимости от значения, которое мы хотим вставить.
Кроме того, перед этим мы должны убедиться, что наш корень не null, потому что это будет означать, что наше дерево пусто. В этом случае мы просто назначаем узел с новым значением корневому свойству дерева.
Здесь мы видим, что нашей рекурсивной функции требуется узел и значение, значение узла будет меняться в зависимости от узла, через который мы движемся.
Когда функция вызывается внутри самой себя, она обновляет параметр узла, таким образом, она может перемещаться по дереву.
Поиск узла
Прежде чем реализовывать метод удаления (подсказка: это самая сложная часть), давайте проверим, работает ли наш код вставки, реализовав метод, проверяющий, существует ли значение.
Этот способ довольно простой. Сначала он проверяет значение, сравнивает его с узлом, заданным в качестве параметра, и соответственно перемещается. если он нашел значение, он возвращает этот узел.
Последний босс: удаление ценностей
Прежде чем мы реализуем этот фрагмент кода, найдите минутку, чтобы придумать причину, по которой было бы трудно удалить узел из дерева. Это должно быть легко, правда? Мы могли бы просто найти его и удалить.
Что, если мы хотим удалить узел, у которого есть дочерний элемент, и что, если у этого дочернего элемента есть дополнительные дочерние элементы?
Удаление узла с детьми без размещения их также приведет к их удалению.
Если 5 человек свешиваются на веревке на утесе, и первый перережет веревку под ним, остальные упадут со скалы.
При удалении узла необходимо учитывать три случая.
Когда узел является листом
Это самый простой из всех, потому что мы можем просто удалить узел и покончить с ним.
Когда у узла есть один ребенок
Мы должны создать связь между дочерним и родительским целевым узлом.
Результат
Когда у узла есть оба потомка
Поскольку мы хотим удалить узел с двумя дочерними элементами, мы должны предпринять дополнительные шаги, чтобы наша структура оставалась упорядоченной. Для этого мы должны один раз переместиться вправо и найти наименьшие значения слева от этого узла. Затем мы должны прикрепить левый узел нашего целевого узла к наименьшему узлу справа от дерева.
Я знаю, это звучит очень запутанно, но вот несколько иллюстраций, чтобы облегчить понимание.
Допустим, мы хотим удалить узел 5 в этом примере дерева.
5 - наш целевой узел (тот, который мы хотим удалить)
Если мы просто удалим его, некоторые данные нашего дерева будут скомпрометированы. Это выглядело бы так.
Вместо этого мы хотим реализовать некоторые дополнительные шаги, чтобы убедиться, что наше дерево остается упорядоченным. Сначала мы перемещаемся вправо от целевого узла (5). Затем мы идем полностью влево, пока не дойдем до листового узла.
Теперь, когда мы нашли крайний левый узел (6) справа от 5, нам нужно переместить левый узел 5, чтобы он шел после 6, вот так.
Конечный результат не будет идеальным деревом, и он начинает больше походить на связанный список, но наше дерево поиска по-прежнему упорядочено правильно.
Результат
Теперь, когда понятно, как работает алгоритм удаления, давайте переведем его в код (сложная часть).
Ух ты! Это много кода. Не торопитесь, чтобы внимательно прочитать все это и попытаться связать это с тем, что мы только что узнали, визуально.
Мы также можем видеть, что есть особый случай, если узел, который мы хотим удалить, является корнем дерева.
Кроме того, в последнем случае вызывается метод с именем goLeft. Этот метод вернет крайнее левое значение, начиная с любого заданного узла.
Методы рефакторинга
Давайте закончим созданием новых методов, чтобы пользователю не приходилось ничего трогать при вставке или удалении узла. Пользователь должен иметь возможность вводить значение и добавлять или удалять его, не беспокоясь о том, с какого узла начинать или как что-то работает.
Мы используем фиктивную переменную для доступа к корню, потому что мы никогда не хотим напрямую обращаться к нему или изменять его. Если мы ошибаемся, мы можем удалить или изменить нашу ссылку на него, в основном потеряв все дерево в памяти.
Конечный результат
Это все на сегодня.
Следите за новостями о графиках!
