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

Опять же, я не могу не подчеркнуть, насколько полезным был курс Удеми Кольта Стила на протяжении всего учебного процесса. Есть много ресурсов, но я перекликаюсь с его стилем преподавания и чувствую, что он разбивает эти сложные предметы на удобоваримые части.

Какие деревья? Дерево - это набор узлов в отношениях родитель / потомок. Если вы следите за этой серией, то знаете, что связанный список - это набор узлов, где узел состоит из значения и указателя на следующий узел. Если вы посмотрите на изображение выше, дерево состоит из корня (также родительского узла), родительских узлов и дочерних узлов. Узлы, у которых есть один и тот же родительский элемент, называются одноуровневыми, а узлы без дочерних узлов (фактически конечная точка дерева) называются листовыми узлами. Только один узел может считаться «корнем» дерева, и его узлы не могут указывать друг на друга. В развернутом виде мы можем увидеть, как график выглядит как нисходящая древовидная структура, которая разветвляется по мере добавления новых узлов.

Некоторые из реальных примеров древовидных структур данных включают DOM, объекты JSON, файловую систему вашего компьютера, сетевую маршрутизацию и этот список можно продолжить. Мы собираемся иметь дело с особым типом дерева, которое обычно встречается в информатике, - двоичным деревом поиска. Если вы посмотрите на первое изображение в самом верху статьи, вы увидите пример BST. Одной из особенностей BST является то, что он может иметь 0, 1 или два узла, но не более. Деревья могут иметь родителей с несколькими дочерними узлами 3, 4, 5 и т. Д., Но в этот момент другая структура данных может быть более предпочтительной.

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

Для реализации класса BST нам потребуются узлы, корень в качестве начального значения и два метода: вставить и найти. См. Следующие изображения для реализации функций insert и find. Вы можете найти полную реализацию класса BST здесь.

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

BigO двоичных деревьев поиска

Мы собираемся завершить эту статью анализом временной сложности BST. Когда дело доходит до вставки и поиска, BigO BST - это O (log n). BigO - это обобщенная мера, поэтому для средних и наихудших сценариев вставка и поиск в BST очень эффективны. Поскольку мы удваиваем количество входов (n), количество шагов увеличивается только на 1 (глубина BST). Если вам нужно хранить данные в упорядоченном порядке и постоянно добавлять в коллекцию, а также читать из нее, то BST, возможно, ваш лучший выбор. При работе с BST опасайтесь односторонних / несбалансированных структур, эффективность падает до O (n), поскольку то, что вы в основном создали, представляет собой связанный список.

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

Больше контента на plainenglish.io