Жду новый пост

Серия «Алгоритмы и структуры golang»

Hello my Dudes

Бинарное дерево - это структура данных, которая представляет собой иерархическую коллекцию элементов, называемых узлами (nodes). Каждый узел имеет значение и может иметь до двух дочерних узлов, называемых левым и правым потомками (left and right children). Узел, который не имеет родителя, называется корнем (root) дерева. Узел, который не имеет потомков, называется листом (leaf) дерева.

Бинарные деревья могут быть использованы для решения различных задач, связанных с поиском, сортировкой, классификацией и вычислением данных. Например, бинарное дерево поиска (binary search tree) - это бинарное дерево, в котором для каждого узла выполняется условие: все значения в левом поддереве меньше значения узла, а все значения в правом поддереве больше или равны значению узла. Бинарное дерево поиска позволяет быстро находить, добавлять и удалять элементы по заданному ключу.

В голанг нет встроенного типа для бинарных деревьев, но их можно реализовать с помощью структур (structs) и указателей (pointers). Для создания бинарного дерева в голанг нужно определить тип узла и тип дерева:

Для добавления элемента в бинарное дерево поиска нужно написать функцию, которая принимает указатель на дерево и значение, которое нужно добавить. Функция должна найти подходящее место для нового узла в дереве и связать его с родителем:

Для поиска элемента в бинарном дереве поиска нужно написать функцию, которая принимает указатель на дерево и значение, которое нужно найти. Функция должна вернуть указатель на узел, содержащий искомое значение, или nil, если такого узла нет в дереве:

Для удаления элемента из бинарного дерева поиска нужно написать функцию, которая принимает указатель на дерево и значение, которое нужно удалить. Функция должна найти узел, содержащий удаляемое значение, и заменить его подходящим узлом из поддеревьев:

Могут быть косяки, не судите строго. У меня через 20 минут созвон (я их очень не люблю).

Линейный поиск имеет временную сложность O(n), где "n" - это количество элементов в списке. В худшем случае алгоритм может проверить все элементы, поэтому его производительность ухудшается с ростом размера списка.

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

Бинарный поиск

Бинарный поиск (Binary Search) - это эффективный алгоритм поиска элемента в отсортированном списке, массиве или коллекции. Он использует стратегию "разделяй и властвуй", что позволяет быстро находить искомый элемент.

Описание алгоритма:

1. Начните с определения границ поиска. Установите начальную границу (left) в начало списка и конечную границу (right) в его конец.

2. Найдите средний элемент между начальной и конечной границей.

3. Сравните средний элемент с искомым значением.

4. Если средний элемент совпадает с искомым значением, возвращаем его индекс (или значение, в зависимости от реализации).

5. Если средний элемент больше искомого значения, обновите конечную границу (right) на позицию перед средним элементом и перейдите к шагу 2.

6. Если средний элемент меньше искомого значения, обновите начальную границу (left) на позицию после среднего элемента и перейдите к шагу 2.

7. Повторяйте шаги 2-6 до тех пор, пока не будет найден искомый элемент или пока начальная граница (left) не станет больше конечной границы (right).

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

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

Прыжковый поиск

Прыжковый поиск (Jump Search) - это алгоритм поиска элемента в отсортированном списке, массиве или коллекции. Он использует идею деления интервала на блоки и прыжки через эти блоки для быстрого приближения к искомому элементу.

Описание алгоритма:

1. Задайте размер прыжка (jump size). Обычно он выбирается как квадратный корень из общего количества элементов в списке.

2. Начните с первого элемента списка.

3. Сравните текущий элемент с искомым значением.

4. Если текущий элемент равен искомому значению, верните его индекс (или значение, в зависимости от реализации).

5. Если текущий элемент больше искомого значения или достигнут конец списка, перейдите к следующему шагу.

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

7. Повторяйте шаги 3-6 до тех пор, пока текущий элемент не станет больше искомого значения или вы превысите границы списка.

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

9. Если элемент найден, верните его индекс (или значение, в зависимости от реализации).

10. Если элемент не найден, верните -1 (или другое значение, указывающее отсутствие элемента).

Прыжковый поиск имеет временную сложность O(√n), где "n" - количество элементов в списке. Он более эффективен, чем линейный поиск, но менее эффективен, чем бинарный поиск. Однако прыжковый поиск особенно полезен, когда список имеет равномерное распределение данных и доступ к элементам осуществляется за постоянное время.

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

В общем: да прибудет с вами сила.

Постепенно цикл буду дополнять.