Объяснение деревьев, двоичных деревьев поиска, графиков и хэш-таблиц на основе псевдокода.
Дерево: дерево может быть определено рекурсивно как структура данных, имеющая корневой узел с 0 или более дочерними узлами. Каждый дочерний узел имеет 0 или более дочерних узлов и так далее. Эта структура используется в HTML / DOM, поскольку все элементы на веб-странице происходят от корневого элемента ‹html›, который разветвляется в дерево. Деревья не линейны, а имеют иерархическую структуру. Для поиска узлов в дереве (что требуется при добавлении или удалении узлов) необходимо пройти или посетить все узлы в нем.
- Конструктор: конструктор дерева должен принимать корневые данные в качестве аргумента. Эти корневые данные назначаются новому узлу, который затем устанавливается как корневой узел дерева. Кроме того, конструктор узла должен установить дочерние элементы узла как пустой массив и данные как аргумент конструктора.
- TraverseDF: это алгоритм, который может служить основой для большинства других методов дерева (добавление, удаление и т. д.). Он принимает обратный вызов в качестве аргумента и выполняет обратный вызов после посещения каждого узла. Посещенный узел передается в качестве аргумента обратного вызова.
1. Создайте новую функцию, которая принимает узел в качестве аргумента.
2. Рекурсивно вызовите новую функцию, которая была только что создана для каждого из дочерние элементы данного узла с помощью цикла for. Этот порядок обхода называется в глубину.
3. Выполните предоставленный обратный вызов с исходным узлом, который был передан в качестве аргумента.
4. Немедленно выполните эту новую функцию, передав корневой узел дерева (this.root) в качестве аргумента.
Двоичное дерево поиска: двоичные (поисковые) деревья считаются подмножеством древовидной структуры данных. В то время как узлы в обычных деревьях могут иметь любое количество дочерних элементов, узлы в двоичных деревьях имеют не более двух дочерних элементов. Потомки двоичного дерева обычно обозначаются как левый и правый. Двоичные деревья часто используются с алгоритмами поиска или сортировки, главным образом потому, что они могут уменьшить временную сложность таких алгоритмов до O (log (n)). Метод сортировки при добавлении нового узла показан в псевдокоде ниже.
- Конструктор: конструктор двоичного дерева должен принимать корневые данные в качестве аргумента. Эти корневые данные назначаются новому узлу, который затем устанавливается как корневой узел дерева. Кроме того, конструктор узла должен установить для двух дочерних узлов узла (left и right) значение null и data в качестве аргумента конструктора.
- Insert: обратите внимание, что этот псевдокод написан специально для вставки узла с числовыми данными. Узлы с меньшими номерами в качестве данных идут в левой части дерева, а узлы с большими номерами - в правой. insert должен принимать один аргумент, который является узлом, который должен быть добавлен к дереву.
1. Создайте новую функцию insertNode, которая принимает два аргумента: rootNode и newNode.
2. Если newNode.data ‹RootNode.data, проверьте, является ли rootNode.left нулевым. Если это так, установите rootNode.left как newNode.
3. Если rootNode.left не равен нулю, затем запустите insertNode рекурсивно, установив первый аргумент (первоначально rootNode) как rootNode.left и сохранив newNode в качестве второго аргумента.
4. Если newNode.data ›rootNode.data, проверьте, имеет ли rootNode.right значение null. Если это так, установите rootNode.right как newNode.
5. Если rootNode.right не равен нулю, затем запустите insertNode рекурсивно, установив первый аргумент (первоначально rootNode) как rootNode.right и сохранив newNode в качестве второго аргумента.
6. Немедленно запустите insertNode, передав this.root (корневой узел всего дерева) в качестве первого аргумента и аргумента метода вставки в качестве второго аргумента.
График: граф состоит из одного или нескольких узлов, соединенных друг с другом ребрами. В этом смысле деревья можно рассматривать как подмножество графов. Как и в случае с деревьями, узлы также содержат информацию или данные. Однако в графе любой узел может быть связан с любым другим узлом, поэтому такие понятия, как «родительский» и «дочерний», не существуют при рассмотрении графа. Графики могут представлять социальные сети, транспортные маршруты, торговые соглашения и т. Д. Края графа могут быть направленными или ненаправленными.
Обратите внимание, что для простоты я не упомянул о создании другого класса узла (хотя это вполне нормально).
- Конструктор: создайте класс графа, который принимает в качестве параметра указанное количество узлов. Задайте numNodes как заданное количество узлов и adjacencyList как объект карты (использование карты вместо обычного объекта позволяет сохранять узлы как ключи). Этот объект покажет, какие узлы с какими подключены на графике. Обратите внимание, что если граф плотный, матрица смежности может быть более подходящей для просмотра ребер.
- addNode: добавляет узел к графу. Просто добавьте данный узел в качестве ключа к adjacencyList и пустой массив в качестве значения. Этот пустой массив покажет, к каким другим узлам он подключен.
- addEdge: этот метод принимает два узла, которые уже есть на графе, в качестве аргументов и добавляет между ними «ребро». Для этого возьмите adjacencyList и используйте узлы в качестве ключей для доступа к их спискам подключенных узлов. Используйте метод push array, чтобы вставить каждый узел в список подключенных узлов другого узла.
Хеш-таблица. Хеш-таблица, похожая на двоичное дерево, часто используется с алгоритмами поиска, поскольку для выполнения поиска в хеш-таблице требуется гораздо меньше времени, чем в других ассоциативных массивах. Способ уменьшения сложности таких алгоритмов заключается в реализации функции хеширования. Функция хеширования преобразует ключ в числовой индекс, чтобы можно было мгновенно определить местоположение данных, на которые указывает ключ. Хотя перекрывающиеся значения индекса между двумя ключами могут замедлить процесс поиска, это все же намного быстрее, чем проверка каждого значения в массиве.
- Конструктор: создайте класс хэш-таблицы, который имеет размер ограничение и пустой массив с именем storage в качестве двух элементов данных. Предел размера должен определяться аргументом конструктора.
- Хеш-функция. Простая хеш-функция для буквенно-цифровых клавиш использует коды ASCII. В частности, индекс, в котором хранятся данные, определяется с помощью следующего - (сумма кодов ASCII для ключа) mod (ограничение размера хеш-таблицы).
- Поиск: после добавления данных в хеш-таблицу с помощью заданной хеш-функции наступит момент, когда данные необходимо будет получить снова. Функция поиска, которая используется для этой цели, принимает в качестве аргумента единственный ключ.
1. Индекс, соответствующий данному ключу, находится с помощью хэш-функции.
2. Если соответствующие данные не соответствуют существуют в этом конкретном индексе (т. е. если storage [index] не определен), вернуть false.
3. В противном случае перебрать пары ключ-значение, присутствующие в этом конкретном индексе, через цикл. Если ключ для одной из этих пар совпадает с ключом, указанным в качестве аргумента, верните соответствующее значение в паре. (Предполагается, что в хеш-таблице используется отдельная цепочка, а не открытая адресация.)