Удаление вершины по значению из бинарного дерева

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

Краткий алгоритм удаления конечной вершины из бинарного дерева:
1. Найдите в дереве вершину, которую надо удалить.
2. Если узел со значением, которое нужно удалить, является конечным (т.е. не имеет потомков), то удалите этот узел.

Сложность: O(log n)

Удаление вершины по значению из бинарного дерева

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

Краткий алгоритм удаления узла, который имеет левое ИЛИ правое поддерево:
1. Найдите в дереве вершину, которую надо удалить.
2. Если у узла есть только левое/правое поддерево, то заменить родителю удаляемого узла ссылку на левое/правое поддерево.

Сложность: O(log n)

Удаление вершины по значению из бинарного дерева

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

Краткий алгоритм удаления узла, который имеет как левое, так и правое поддерево:
1. Найдите в дереве вершину, которую надо удалить.
2. Если у узла есть и левое, и правое поддерево, найти наибольший (или наименьший) элемент в левом (или правом) поддереве.
3. Заменить значение удаляемого узла значением найденного элемента.
4. Удалить найденный элемент из левого (или правого) поддерева.

Сложность: O(log n)

Job Sequencing Problem

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

Алгоритм:
1. Сортируем работы по убыванию прибыли.
2. Создаем массив длиной равной максимальному сроку сдачи работ, заполняем его -1, чтобы отметить свободные слоты.
3. Проходимся по отсортированным работам:
- Для каждой работы ищем наибольший возможный слот с сроком сдачи до или равным текущему сроку сдачи работы.
- Если найден свободный слот, помещаем работу в этот слот и устанавливаем значение слота на индекс этой работы.
4. Восстанавливаем последовательность работ, проходясь по массиву слотов. Работы, у которых значение слота не равно -1, добавляем в итоговую последовательность.

Сложность: O(n log n)

Задача о дробном рюкзаке

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

Алгоритм:
1. Рассчитываем отношение стоимости к весу для каждого предмета.
2. Сортируем предметы по убыванию этого отношения.
3. Идем по отсортированному списку предметов и добавляем их в рюкзак до тех пор, пока рюкзак не станет полным или пока не закончатся предметы.
4. Если последний предмет не помещается полностью в рюкзак, добавляем его частично, пропорционально оставшемуся месту.
5. Возвращаем суммарную стоимость предметов в рюкзаке.

Сложность: O(n log n) времени, где n - количество предметов.

Центрированный тип обхода

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

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Прямой тип обхода

Прямой тип обхода является одним из трех базовых типов обхода бинарного дерева. Выполняет обработку узлов в следующем порядке: сначала сам узел, затем его левое поддерево и, наконец, правое поддерево.

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Обратный тип обхода

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

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Обход по порядку уровней бинарного дерева

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

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

Сложность: O(n), где n - количество узлов в дереве. В худшем случае каждый узел будет посещён один раз.

Обход границы на бинарном дереве

Метод обхода бинарного дерева, который проходит по границе дерева в определенном порядке.

Он включает следующие этапы:
1. Обход левой границы с вершины до левого листа, включая вершину.
2. Обход всех левых листьев сверху вниз.
3. Обход правой границы снизу вверх, исключая правый лист.
4. Обход всех правых листьев снизу вверх.

Сложность: O(n), где n - количество узлов в дереве. В худшем случае каждый узел будет посещен один раз.

Диагональный обход бинарного дерева

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

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

Сложность: O(n log n)

Метод скользящего окна

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

Алгоритм:
1. Инициализируем начало окна и конец окна.
2. Пока конец окна не достигнет конца последовательности данных, выполняем следующие шаги:
- Выполняем операции над элементами внутри текущего окна.
- Перемещаем окно вправо, увеличивая начало и конец окна на один элемент.
- Обновляем результат, если необходимо.
3. Возвращаем итоговый результат.

Сложность: O(n), где n - общее количество элементов в последовательности данных.

Задача о сумме подмножеств

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

Для каждого элемента есть две возможности:
1. Включите текущий элемент в подмножество и повторите операцию для остальных элементов с оставшейся суммой.
2. Исключить текущий элемент из подмножества и повторить операцию для остальных элементов.
3. Наконец, если сумма становится равной 0, выведите элементы текущего подмножества.

Сложность: O(n^2)

Раскраска графов

Алгоритм присвоения цветов вершинам графа таким образом, чтобы каждая пара смежных вершин имела разные цвета.

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

Сложность: O(n^2), где n - количество вершин в графе.

Гамильтонов цикл

Гамильтонов цикл — это цикл в графе, который посещает каждый узел ровно один раз и возвращается в начальный узел.

Алгоритм:
1. Начните с любого узла, отметьте его как посещенный и добавьте его в путь.
2. Если все узлы посещены и текущий узел имеет ребро к начальному узлу, верните путь как гамильтонов цикл.
3. Если не все узлы посещены, рекурсивно исследуйте непосещенных соседей. Для каждого непосещенного:
а. Отметить соседа как посещенного.
б. Добавьте соседа в путь.
в. Рекурсивно исследуйте этот новый путь.
4. Если рекурсивное исследование не приводит к гамильтонову циклу, вернитесь назад, удалив последний узел из пути и пометив его как непосещенный.
5. Продолжите процесс, выбрав другого непосещенного соседа текущего узла и исследовав его.
6. Если все соседи исследованы и ни один из них не ведет к гамильтонову циклу, вернитесь дальше, удалив текущий узел из пути и пометив его как непосещенный.

Сложность: O(N!), где N — количество вершин.

Подсчет инверсий

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

Алгоритм:
1. Создайте функцию merge, которая подсчитывает количество инверсий при слиянии двух половин массива.
⁃ Создайте два индекса i и j, i — индекс первой половины, а j — индекс второй половины.
⁃ Если a[i] больше, чем a[j], то происходят инверсии (mid – i), поскольку левый и правый подмассивы отсортированы, поэтому все оставшиеся элементы в левом подмассиве (a[i+1], a[i +2] … a[mid]) будет больше, чем a[j].
2. Создайте рекурсивную функцию, чтобы разделить массив пополам и найти ответ, суммируя количество инверсий в первой половине, количество инверсий во второй половине и количество инверсий путем слияния двух.

Сложность: O(N^2)

Выпуклая оболочка с использованием алгоритма Джарвиса

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

Алгоритм:
1. Инициализируйте p как крайнюю левую точку.
2. Делаем следующее, пока не возвращаемся к первой (или крайней левой) точке:
⁃ Следующая точка q — это точка такая, что тройка (p, q, r) направлена ​​против часовой стрелки для любой другой точки r.
⁃ Чтобы найти это, мы просто инициализируем q как следующую точку, а затем проходим через все точки.
⁃ Для любой точки i, если i больше против часовой стрелки, т. е. ориентация (p, i, q) против часовой стрелки, то мы обновляем q как i.
⁃ Нашим окончательным значением q будет точка, расположенная крайним против часовой стрелки.
⁃ next[p] = q (сохраните q как следующее из p в выходной выпуклой оболочке).
⁃ p = q (установите p как q для следующей итерации).

Сложность: O(m * n), где n — количество входных точек, а m — количество выходных точек или точек оболочки (m <= n).

Выпуклая оболочка с использованием алгоритма «разделяй и властвуй»

Алгоритм:
1. если в наборе всего 3 или меньше точек, вычислите и верните их выпуклую оболочку напрямую.
2. Разделить: найти точку с наименьшей координатой X (а в случае ничьей — наименьшую координату Y) и точку с наибольшей координатой X (а в случае ничьей — наибольшую координату Y). . Эти две точки вместе с линией, соединяющей их, делят набор точек на верхнее и нижнее подмножество.
3. Рекурсия: рекурсивно найти выпуклые оболочки верхнего и нижнего подмножеств. Эти две выпуклые оболочки представляют собой части выпуклой оболочки выше и ниже разделительной линии.
4. Слияние: объедините верхнюю и нижнюю выпуклые оболочки, чтобы получить окончательную выпуклую оболочку.

Сложность: O(n*log n)

Касательные между двумя выпуклыми многоугольниками

Чтобы найти касательные между двумя выпуклыми многоугольниками, вы можете выполнить следующие общие шаги.

Алгоритм:
1. Убедитесь, что полигоны отсортированы против часовой стрелки.
2. Определите вершину в каждом многоугольнике, ближайшую к другому многоугольнику. Эти вершины являются потенциальными отправными точками касательных линий.
3. Для каждой из вершин, определенных на шаге 2, вычислите касательные линии от этой вершины к другому многоугольнику.
4. Убедитесь, что каждая рассчитанная касательная не пересекает внутреннюю часть ни одного многоугольника.
5. Сохраните эти касательные, они являются касательными между двумя многоугольниками.

Сложность: O(n1 log (n1) + n2 log(n2))

Динамическая выпуклая оболочка

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

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

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

Сложность: O(n*q), где q — количество добавляемых точек.