DS с JS — Деревья

Деревья похожи на деревья 🌳 в природе с одним небольшим отличием — деревья, которые мы собираемся изучать, перевернуты вверх ногами.

Деревья представляют собой нелинейные структуры данных. Это не структура один за другим, классифицируемая как линейная структура данных. Массивы, стеки, очереди или связанные списки являются линейными структурами данных. В деревьях у нас могут быть такие элементы, как ветки, настоящие ветки деревьев — где угодно!

Эта гибкость приводит к необходимости создать словарь для деревьев и научиться их классифицировать. Мы рассмотрим очень специфическое и известное бинарное дерево и реализуем его на JavaScript.

Построение нашего словаря для деревьев

Мы понимаем node из Связанных списков. В Singly Linked List узел имеет value и pointer к следующему узлу. Последний узел в (одинарно/двукратно) связанном списке указывает на null. Дерево также состоит из узлов. Но, как вы могли догадаться, они расположены не друг за другом.

Теперь, когда мы понимаем самый фундаментальный элемент дерева — node, давайте создадим словарь для деревьев.

1. Корневой узел. верхний узел, на который не указывают узлы. Это начало дерева.
2. Link/Edge: ссылка или соединение от одного узла к другому. Или подключение от родительского к дочернему узлу.
3. Родительский узел: узел, связывающий или ссылающийся на другой узел.
4. Дочерний узел: узел, у которого есть родительский узел.
5. Родственные узлы: дочерние узлы, имеющие одного и того же родителя.
6. Лиственный узел: узел, у которого нет дочернего узла.

Теперь вот несколько. твистеры для дерева:

1. Корневой узел не имеет родительского узла.
2. Дочерний узел имеет только один родительский узел.
3. Родительский узел может иметь ноль или любое количество дочерних узлов.
4. Все узлы являются дочерними элементами корневого узла.
5. Для n узлов существуют n-1 связи или ребра, независимо от того, как мы их расположим.
6. Дерево — это рекурсивная структура данных, потому что деревья состоят из поддеревьев.

Это много информации всего из нескольких словарей! Добавим к этому списку еще два.

Глубина и высота

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

• Глубина узла – это количество ребер, ведущих к узлу от корневого узла.
• Высота узла – это максимальное количество ребер от узла до самого дальнего конечного узла.

Используя глубину и высоту, мы можем определить, сбалансировано дерево или нет.

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

Другой способ взглянуть на эту классификацию — использовать уровни, как показано на изображении.

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

Использование в режиме реального времени

Но где мы видели деревья? Ну, чтобы назвать несколько…

• Наследство (помните генеалогическое древо!)
• Файловая структура проекта или файловая система в вашей системе
• git-bisect — использует бинарный поиск, чтобы найти фиксацию, которая привела к ошибке.
• DOM — это древовидная структура данных.
• Онлайн-шахматы с компьютером — компьютер использует древовидную структуру данных для принятия решения. На основании того, какой ход лучше, компьютер принимает решение.
• Комментарии в Фейсбуке.
• Абстрактные синтаксические деревья.

В информатике абстрактное синтаксическое дерево (AST) или просто синтаксическое дерево — это древовидное представление абстрактной синтаксической структуры исходного кода. написан на языке программирования. Каждый узел дерева обозначает конструкцию, встречающуюся в исходном коде. Код разбивается машиной на абстрактный синтаксис, который представляет собой древовидную структуру данных.

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

Есть много типов деревьев — мы можем начать задаваться вопросом о многих способах расположения узлов в дереве. Но для начала остановимся на самом популярном — Binary Tree.

Бинарные деревья

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

let binary_tree_node = {
  value: 1,
  left: null,
  right: null
};

Здесь node имеет значение и указатели максимум на двух дочерних узлов — left и right узлов.

Представление двоичного дерева с использованием массива

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

Чтобы представить бинарное дерево массивом, мы упорядочиваем значения узлов в массиве слева направо, начиная с корневого узла и двигаясь вниз по уровням, пока не достигнем последнего крайнего правого листового узла.

Если узла нет, то в массиве его можно оставить пустым, что означает, что он заполнен либо null, либо undefined.

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

Классификация бинарного дерева

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

• Полное бинарное дерево имеет узлы с 0 или 2 дочерними узлами.
• Полное бинарное дерево имеет листовые узлы на последнем уровне, и узлы заполняются слева направо.
• Идеальное бинарное дерево имеет 2 дочерних узла для всех уровней, и все конечные узлы находятся на одном уровне.
• Вырожденное или патологическое дерево — это дерево, в котором каждый узел имеет только 1 дочерний узел.

Имея в виду приведенные выше определения, мы можем сказать

• Все совершенные бинарные деревья являются полными бинарными деревьями.
• Все полные бинарные деревья являются сбалансированными бинарными деревьями.

Мы хотим иметь идеальное бинарное дерево для наилучшей производительности, так как при каждом выборе ветви мы вдвое уменьшаем количество узлов, оставшихся для прохождения. Это означает, что уменьшение вдвое каждого хода дает временную сложность O(log N).

Допустим, у нас есть бинарное дерево с 10 узлами, и мы хотим перейти от корневого узла к любому из конечных узлов. Как вы думаете, сколько шагов нам нужно?

Чтобы добраться до любого узла на уровне 2, нам нужно 2 шага, аналогично, чтобы добраться до любого узла на уровне 3, нам нужно 3 шага и так далее. Количество шагов такое же, как и уровень, и это верно для всех деревьев. Но с каждым уровнем мы удаляем большую часть узлов. Например, к тому времени, когда мы находимся в Узле 4, мы устранили Узлы 3, 6, 10, 5 и 9, половину узлов!

Но чем это полезно? Если узлы расположены случайным образом, как это поможет в обходе дерева? Как узнать, какой путь выбрать при поиске узла?

На все эти открытые вопросы можно ответить, приведя структуру к расположению узлов, широко известную как двоичное дерево поиска.

Бинарное дерево поиска

Ссылки и дополнительная литература

• «Как не попасть в тупик перед деревьями | Середина"
• «Разница между двоичным деревом, двоичным поиском и двоичным деревом поиска | Переполнение стека"