Мотивация

«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их взаимосвязях».

Линус Торвальдс

Введение

Дерево

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

Файловая система, профиль организации

Бинарное дерево

Бинарное дерево — это особый тип дерева, в котором максимальное количество дочерних узлов равно двум.

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

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

Общий термин

Path = Конкретный способ/узлы для доступа с одного узла на другой.

Tree-Traversal = Посещение всех узлов определенным образом.

root = Первый узел Дерева.

Key = значение каждого узла.

level = Определенная поломка дерева.

Прежде чем двигаться дальше

если вам нужна правильная документация, перейдите по ссылке ниже.



DataDoc
Простое руководство по изучению структуры данныхraufr.github.io



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

Выполнение

Прежде чем внедрять древовидную структуру данных, необходимо понять основные операции и методы javascript.

Наше двоичное дерево поиска имеет некоторые дополнительные функции.

  1. Insert = вставить данные в узел
  2. Travers = узлы обхода для доступа к значениям
  3. Поиск = поиск внутри узлов
  4. Удалить = удалить узел/узлы

Базовая структура

Объект Node будет содержать всю конкретную информацию об отдельном узле, который принимает 3 аргумента dat, left, right.

Также простая функция show() будет отображать значение внутри узла.

Нам также нужна функция конструктора.

Вставлять

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

Алгоритм операции вставки:

  1. root node === current node

2. if (datavalue in inserted node > datavalue of current node) set the new current node as left child, else skip step 4

3. if (left child value === null) insert the value and exit, else go on

4. current node == right child

5. if (value of right child === null ) insert new node and exit, else go on

Траверс

Есть три вида траверса.

  1. inOrder = Посетите все узлы в порядке возрастания по значению ключа узла
  2. preOrder = Будет посещать через порядок узлов (корень => родитель => дети => левый => правый)
  3. postOrder = Посетим (левый дочерний элемент =› root, а затем правый дочерний элемент =› root )

Поиск

В бинарном дереве поиска может быть три типа поиска.

  1. Минимальное значение
  2. Максимальное значение
  3. Конкретное значение

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

Удалять

Удаление узла из дерева намного сложнее, чем любая другая операция.

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

Если удаленный узел является конечным узлом, указатель родительского узла должен иметь значение null.

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

Функция найдет наименьшее значение поддерева, затем использует значение и удалит узел.

Вот и все!

Я знаю, что он в значительной степени переполнен, но не слишком скучайте, потому что знать и реализовывать двоичное дерево поиска действительно весело.

Как реализовать

Просто скопируйте и вставьте полный код в файл .js и используйте его как модуль.

Полный код

Спасибо за ваше время.!