- Зачем нужно знать структуры данных и чем они полезны
- Stack
- Queue
- Linked list
- Set
- Map
- Tree Data Structure
- B-Tree
- R-Tree
- Binary Tree
- Red-Black Tree
- AVL Tree
- Splay-Tree
- Binary search tree
- Balancing tree
- Heap
- Graph
Хорошо подобранная структура данных позволяет эффективно манипулировать этими данными. Эффективно манипулировать - это про минимум занимаемой памяти, максимум скорости и производительность, масштабируемость, определенная логика, поведение, удобно, гибко, понятно ...
"Никлаус Вирт написал книгу "Алгоритмы + структуры данных = программы."
- Stack
- Queue/Deque
- Linked list
- Set
- Map (Hash Table)
- Binary search tree
- Red-Black Tree
- Trie
- Graph
LIFO (last-in, first-out) "Последним вошел - первым вышел"
Чем полезен Stack?
Особенности поведения Stack.
- Для реализации рекурсии.
- Корректность выражения со скобками.
- Перевернуть слово — поместите все буквы в стопку и вытащите их. Из-за порядка стека LIFO буквы будут расположены в обратном порядке.
- В компиляторах — компиляторы используют стек для вычисления значения выражений типа
2 + 4 / 5 * (7 - 9)путем преобразования выражения в префиксную или постфиксную форму. - В браузерах — кнопка «Назад» в браузере сохраняет в стопке все URL-адреса, которые вы посещали ранее. Каждый раз, когда вы посещаете новую страницу, она добавляется поверх стека. При нажатии кнопки «Назад» текущий URL-адрес удаляется из стека и открывается доступ к предыдущему URL-адресу.
Сложность алгоритма для операции push и pop занимают постоянное время, т. е. O(1).
Способы реализации Stack:
- Стек через
Array, фиксированного размера, поискO(n), доступ по индексуO(1), удалениеO(n) - Стек через
Vec, безразмерный, поискO(n), доступ по индексуO(1), удалениеO(n) - Стек через
Linked list, безразмерный, поискO(n), для двунаправленного поискO(n/2), возможность разбивать/объединять
FIFO (first-in, first-out) "Первым пришел - первым ушел»"
Сложность алгоритма для операции push занимают постоянное время, т. е. O(1).
Затратная операции pop за O(n) если реализация через Vec придется сдвигать элементы.
Чем полезна Queue?
- Queue необходима для решения низкоуровневых задач, таких как планирование заданий CPU,
- Для моделирования реальной очереди - например, запросов на техническую поддерку, которые необходимо обрабатывать последовательно.
- Для управления потоками в многопоточных средах.
- Для генерации значений.
- Для создания буферов.
Способы реализации Queue:
- Queue через
Vec - Queue через
Linked list
BinaryHeap max/min-heap Куча является максимально эффективной реализации очереди с приоритетом.
Linked list - содержит в каждом елементе данные и указатель на следующий елемент.
Вставка O(1), удаление O(1), поиск O(n)
Чем полезен Linked list?
- Вам нужно много разбивать или объединять большие списки.
- Вы делаете потрясающую параллельную работу без блокировки.
- Для построения более сложных структур данных.
- Для реализации файловых систем.
- Для формирования хэш-таблиц.
- Для выделения памяти в динамических структурах данных.
В большинстве случаев 99% вам следует просто использовать Vec (стек массивов),и остальные 1% времени вам следует использовать VecDeque
Linked list прекрасная структура данных с несколькими замечательными вариантами использования, но те случаи использования являются исключительными, а не обычными.
В функциональном языке Односвязные списки — ваш основной инструмент управления потоком управления, но они действительно плохой способ хранить кучу данных и запрашивать их.
Плюсы:
- динамический размер
- операция вставки/удаления в начало быстрее чем у динамического массива т.е. вектора (у вектора удаление
O(n)из-за перестановки элементов) - Сила
Linked listзаключается в возможности разорвать цепочку и снова присоединиться к ней. Linked listрешает проблему массивов фиксированной размерности тем что может динамически расширятся.Linked listрешает проблему динамических массивов тем что нет необходимости сдигать элементы справа.
Минусы:
- поиск/доступ по индексу за
O(n)(в худшем случае), для двунаправленногоO(n/2)из-за точки входа из головы или хвоста
Разновидности
- Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.
1->2->3->4->NULL
- Двунаправленный, две ссылки, связанные с каждым узлом, одним из опорных пунктов на следующий узел и один к предыдущему узлу.
NULL<-1<->2<->3->NULL
- Круговой, все узлы соединяются, образуя круг. В конце нет NULL. Циклический связанный список может быть одно-или двукратным циклическим связанным списком.
1->2->3->1
Данные хранятся группой, их нельзя структурировать и в некоторых случаях нельзя сортировать.
Зато с ними можно работать как с классическими математическими множествами: объединять union, искать пересечения intersection, вычислять разность difference и смотреть, является ли одно множество подмножеством другого is_superset.
Чем полезен Set?
- Для поддержания множества уникальных элементов.
- Для хранения данных, которые не нужно сортировать.
- Для сравнения, объединения наборов данных и других операций с ними.
Её ещё называют ассоциативным массивом или словарём.
Данные здесь хранятся в паре «ключ/значение», причем каждый ключ уникален, а вот значения могут повторяться.
Вставка O(1), удаление O(1), поиск O(1) и O(n) в худшем случае. Но есть один недостаток, Hash Table имеют накладные расходы по памяти, храня хеш ключа.
Функцию хеширования можно выбрать самую производительную, но это дает возможность для вреда атаки HashDoS.
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение играет роль индекса. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива.
Чем полезен Hash Table
- требуется поиск и вставка c постоянным временем
O(1) - криптографические приложения
- необходимы данные индексирования
- Для создания баз, в которых нужно хранить уникальное соответствие между двумя множествами значений. Их помещают в ключ, и структура проверяет, чтобы ключ не повторялся
Эффективность хеширования зависит от:
- Функции хеширования
- Размера хэш-таблицы
- Метода борьбы с коллизиями (метод цепочек и метод двойного хеширования)
Почему древовидная структура данных?
Другие структуры данных, такие как массивы, связанный список, стек и очередь, представляют собой линейные структуры данных, в которых данные хранятся последовательно. Для выполнения какой-либо операции с линейной структурой данных временная сложность увеличивается с увеличением размера данных. Но это неприемлемо в современном вычислительном мире.
Различные древовидные структуры данных обеспечивают более быстрый и простой доступ к данным, поскольку это нелинейная структура данных.
Двоичное дерево является упорядоченным ориентированным деревом.
Node
Node — это объект, который содержит ключ или значение и указатели на его дочерние узлы.
Последние узлы каждого пути называются листовыми узлами или внешними узлами, которые не содержат ссылки/указателя на дочерние узлы.
Node, имеющий хотя бы дочерний Node, называется внутренним узлом.
Edge
Или Ребро это связь между любыми двумя узлами.
Root
Это самый верхний Node дерева.
Высота Node
Высота Node — это количество ребер от Node до самого глубокого листа (т. е. самый длинный путь от Node до листового узла).
Глубина Node
Глубина Node — это количество ребер от корня до Node.
Высота дерева
Высота дерева — это высота корневого Node или глубина самого глубокого Node.
Degree of a Node
Degree of a Node — это общее количество ветвей этого узла.
Forest
Совокупность непересекающихся деревьев называется Forest.
Виды Tree
- Binary Tree
- AVL Tree
- B-Tree
Применение
Binary search tree (BST)используются для быстрой проверки наличия элемента в наборе или нет.Heap— это разновидность дерева, которое используется для сортировки кучи.- Модифицированная версия дерева под названием
Triesиспользуется в современных маршрутизаторах для хранения информации о маршрутизации. - Большинство популярных баз данных используют
B-деревьяиT-деревья, которые являются вариантами древовидной структуры, для хранения своих данных. - Компиляторы используют синтаксическое дерево/префиксное дерево
Trieдля проверки синтаксиса каждой написанной вами программы.
В Rust std::collections::BTreeMap реализован на основе B-Tree
Основной недостаток В-деревьев состоит в отсутствии для них эффективных средств выборки данных (то есть метода обхода дерева), упорядоченных по свойству, отличному от выбранного ключа.
B-дерево – это структура хранения данных, являющаяся разновидностью дерева поиска. Особенностями В-деревьев является:
сбалансированность, ветвистость, отсортированность логарифмическое O(log n) время работы всех стандартных операций (поиск, вставка, удаление). Сбалансированность означает, что все листы находятся на одинаковом расстоянии от корня. В отличие от бинарных деревьев В-деревья допускают большое число потомков для любого из узлов. Это свойство называется ветвистостью. Благодаря ветвистости, В-деревья очень удобны для хранения крупных последовательных блоков данных, поэтому такая структура часто находит применение в базах данных и файловых системах.
С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц памяти, то есть каждому узлу дерева соответствует блок памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.
Порядок(m) В-дерева – это максимальное число потомков для любого узла. Кроме узлов в дереве присутствует ещё одна сущность – ключи. Именно в них и содержится вся полезная информация. Каждый узел дерева можно представить в виде упорядоченной последовательности ”потомок1; ключ1; потомок2; ключ2; … потомок(N-1); ключ(N-1); потомокN”. Важно заметить, что ключи располагаются между ссылками на потомков и, таким образом, ключей всегда на 1 меньше. В организации В-дерева можно выделить несколько ключевых правил:
Каждый узел содержит строго меньше m (порядок дерева) потомков. Каждый узел содержит не менее m/2 потомков. Корень может содержать меньше m/2 потомков. У корневого узла есть хотя бы 2 потомка, если он не является листом. Все листья находятся на одном уровне и содержат только данные (ключи). Но это не значит что ключи находятся только в листьях. Ключи во внутреннем узле окружены указателями или смещениями записей, отсылающими к ключам, которые либо все больше, либо все меньше окруженного ключа. Например, все ключи, меньшие 22, адресуются левой ссылкой, все большие - правой. Для простоты здесь не показаны адреса записей, связанные с каждым ключом.
B-деревья разветвляются на ветви K-2K (для заданного числа K), а не на 2, как это типично для бинарных деревьев. В остальном они ведут себя очень похоже на двоичное дерево поиска. Преимущество этого заключается в сокращении операций доступа, что особенно полезно, когда данные хранятся во вторичном хранилище или в удаленном месте. Таким образом, мы можем запрашивать данные более крупными порциями, и к тому времени, когда мы закончим обработку предыдущего запроса, наш новый запрос будет готов к обработке. Эта структура часто используется при реализации баз данных, поскольку они имеют большой доступ к вторичному хранилищу.
B+ дерево — структура данных на основе B-дерева, сбалансированное n-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B+ дерево состоит из корня, внутренних узлов и листьев, корень может быть либо листом, либо узлом с двумя и более потомками.
Изначально структура предназначалась для хранения данных в целях эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем; применение связано с тем, что в отличие от бинарных деревьев поиска, B+ деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.
Построение B+-дерева может требовать перестройки промежуточной структуры, это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от t до 2t, где t — степень (или порядок) дерева. При попытке вставить в узел 2t+1-й ключ возникает необходимость разделить этот узел, в качестве ключа-разделителя сформированных ветвей выступает t+1-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+-дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей k. Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.
R-дерево (R-trees) — древовидная структура данных (дерево). Она подобна B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами (широтой и долготой). Типичным запросом с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения».
Типы двоичного дерева:
- Полное двоичное дерево
- Идеальное двоичное дерево
- Дегенеративное или патологическое дерево
- Перекошенное двоичное дерево
- Сбалансированное двоичное дерево (АВЛ-дерево (AVL Tree), Красно-чёрное дерево, splay-деревья)
- Двоичное дерево поиска (Binary Search Tree)
- Двоичная куча (Binary Heap)
- Матричное дерево
- Дерево Фибоначчи
- Суффиксное дерево
Идеальное двоичное дерево
Идеальное двоичное дерево - это тип двоичного дерева, в котором каждый внутренний узел имеет ровно два дочерних узла, а все конечные узлы находятся на одном уровне.
Сбалансированное двоичное дерево
Это тип двоичного дерева, в котором разница между высотой левого и правого поддерева для каждого узла равна 0 или 1.
Операции с деревом работают за O(h), где h — максимальная глубина дерева (глубина — расстояние от корня до вершины). В оптимальном случае, когда глубина всех листьев одинакова, в дереве будет n=2^h вершин. Значит, сложность операций в деревьях, близких к оптимуму будет O(log(n)). К сожалению, в худшем случае дерево может выродится и сложность операций будет как у списка.
Существуют способы реализовать дерево так, чтобы оптимальная глубина дерева сохранялась при любой последовательности операций. Такие деревья называют сбалансированными. К ним например относятся красно-черные деревья, AVL-деревья, splay-деревья, и т.д.
Сбалансированное двоичное дерево
Двоичное дерево поиска
В информатике, бинарное дерево поиска (BST), также называемое упорядоченным или отсортированное двоичное дерево.
Применение:
- Приложения двоичного дерева
- Для легкого и быстрого доступа к данным
- В алгоритмах маршрутизатора
- Для реализации структуры данных кучи
- Синтаксическое дерево
Разновидность сбалансированного двоичного дерева в котором стоимость поиска гарантированно O(log N).
Все основные операции с красно-черным деревом можно реализовать за O(h), то есть O(log N), так же высота дерева не более O(2 log N)
Левостороннее красно-черное дерево - это 2-3-4 дерево.
Левостороннее красно-черное дерево (Left-leaning Red-Black Tree) — это вариация классического красно-черного дерева, предложенная Робертом Седжвиком в 2008 году. Эта вариация упрощает структуру дерева, делая его более понятным и легким в реализации. Основная идея заключается в том, чтобы представить три вида узлов вместо двух, как в классическом красно-черном дереве. Три вида узлов: красные, черные и черные с левым красным потомком.
Необходимость
При использовании бинарного дерева поиска, заполняя его рандомными или еще хуже данных по возростанию, дерево вырождается в список с поиском за O(N). Поддержка бинарного дерева поиска в сбалансированном виде является более затратной чем в самобалансирующих структур данных.
Красно-черные деревья самобалансируются при добавлении/удалении елементов, поддерживая время O(log N) для операций вставки, поиска, кроме поиска диапазона.
Свойства Левостороннего красно-черного дерева:
- Красный узел не может быть сыном красного узла,а черный узел может быть сыном и красного и черного
- Все красные связи направлены влево,а черные могут в обе стороны
- У красного узла потомки черные и его родитель черный
- Корень дерева черный
- (идеально сбалансированно в черном цвете) количество черных связей от корня до листа, одинаково для любого листа
- у узла не может быть два красных потомка
- красный узел может быть только слева
Добавление узла:
- новый узел всегда красный, после добавления его балансируют, проверяют не нарушилось ли локальное свойство и при нарущении выполняют операцию поворота и возможно смену цвета и так далее до корня
4 ситуации при добавлении узла (не более трех на каждом шаге):
- если родитель черный (мы поднимаемся проверять выше?)
- если красная связь справа то следует выполнить левый поворот
- если и левое и правое поддерево красные, то выполнить операцию смены цвета, поменять на черный,а родителя на красный
- если родитель красный и его родитель красный, то выполним правый поворот и операцию смены цвета
Левостороннее красно-черное дерево, из этого следует, что красные ноды могут лежать только слева (обратный случай требует балансировки)
Для реализации этого вида сбаласированных деревьев, нужно в каждом узле хранить дополнительно 1 бит информации (цвет). Иногда это вызывает большой overhead из-за выравнивания. В таких случаях предпочтительно использовать структуры без дополнительных требований к памяти.
Красно-черные деревья широко используются — реализация set/map в стандартных библиотеках, различные применения в ядре Linux (для организации очередей запросов, в ext3 etc.)
Красно-черные деревья тесно связаны с B-деревьями. Можно сказать, что они идентичны B-деревьям порядка 4 (или 2-3-4 деревьям). Красно-черные деревья — одни из наиболее активно используемых на практике самобалансирующихся деревьев. Они так называются из-за наличия на узле дополнительного поля, в котором размещается цвет узла. В качестве стандартных цветов используют обычно красные и черные узлы, а сам цвет узла используется во время балансировки.
Так как красно-черные деревья самобалансирующиеся, то среднее и худшее время поиска тоже составляют O(logN). А операции вставки и удаления узла могут потребовать поворот поддерева.
Помимо особенностей работы с листовыми узлами к свойствам красно-черного так же относят:
Корень красно-черного дерева черный
Две красные вершины не могут идти подряд ни на одном пути. Оба потомка каждого красного узла — черные
Для каждой вершины, в каждом исходящем из нее пути, одинаковое число черных вершин
Иногда при работе с узлами красно-черного дерева используют черную высоту — количество черных вершин на исходящих из нее путях, не включая саму исходную вершину.
Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить. Новый узел всегда добавляется как лист, поэтому оба его потомка являются пустыми узлами и предполагаются черными. После вставки красим узел в красный цвет. Далее смотрим на предка и проверяем, не нарушается ли свойства дерева, которые описали выше. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.
Сбалансированность этих деревьев хуже, чем у АВЛ-деревьев. При этом затраты на поддержание состояния сбалансированности и потребление памяти меньше, а операцию поиска можно выполнять одновременно с выполнением перестроения дерева.
Благодаря этим преимуществам сфера применения красно-черных деревьев существенно шире. Так, например, в стандартной библиотеке шаблонов языка C++ STL и TreeMap в Java применяются именно красно-черные деревья.
Сбалансированность красно-черного дерева деревьев хуже, чем у АВЛ-деревьев. При этом затраты на поддержание состояния сбалансированности и потребление памяти меньше, а операцию поиска можно выполнять одновременно с выполнением перестроения дерева.
Red-black tree implementation notes
Красно-чёрное дерево (удалить)
Операции набора и массовые операции
Левостороннее красно-черное дерево - удаление
Красно-черное дерево - удаление
Красно-черное дерево - удаление
Красно-черное дерево - удаление
Red Black Tree Implementations
Left Leaning Red Black Tree Visualisation
Left Leaning Red Black Tree Visualisation Tools
Red Black Tree Visualisation Tools
Red Black Tree Visualisation DOT Tools
Red Black Tree Visualisation Tools
Накладывает на дерево следующее ограничение: у любой вершины высоты левого и правого поддеревьев должны отличаться не более чем на 1.
Реализация, как и у красно-черного дерева, основана на разборе случаев и достаточно сложна для понимания (хотя имхо проще красно-черного) и имеет сложность O(log(n)) на все основные операции. Для работы необходимо хранить в каждой вершине разницу между высотами левого и правого поддеревьев. Так как она не превосходит 1, достаточно использовать 2 бита на вершину.
АВЛ-деревья отличаются от идеально сбалансированных. АВЛ-дерево считается сбалансированным, если для каждого узла дерева высота его правого и левого поддеревьев отличаются не более чем на единицу. Если модификация структуры узлов приводит к нарушению сбалансированности дерева, то необходимо выполнить его балансировку.
Не накладывает никаких ограничений на структуру дерева. Более того, в процессе работы дерево может оказаться полностью разбалансированным!
Основа splay-дерева — операция splay. Она находит нужную вершину (или ближайшую к ней при отсутствии) и «вытягивает» ее в корень особой последовательностью элементарных вращений (локальная операция над деревом, сохраняющая свойство порядка, но меняющая структуру). Через нее можно легко выразить все оснавные операции с деревом. Последовательность операций в splay подобрана так, чтобы дерево «магически» работало быстро.
Зная магию операции splay, эти деревья реализуются не легко, а очень легко, поэтому они тоже очень популярны в ACM ICPC, Topcoder etc.
Ясно, что в таком дереве нельзя гарантировать сложность операций O(log(n)) (вдруг нас попросят найти глубоко залегшую вершину в несбалансированном на данный момент дереве?). Вместо этого, гарантирается амортизированная сложность операции O(log(n)), то есть любая последовательность из m операций с деревом размера n работает за O((n+m)*log(n)). Более того, splay-дерево обладает некоторыми магическими свойствами, за счет которого оно на практике может оказаться намного эффективнее остальных вариантов. Например, вершины, к которым обращались недавно, оказываются ближе к корню и доступ к ним ускоряется. Более того, доказано что если вероятности обращения к элементам фиксированы, то splay-дерево будет работать асимптотически не медленней любой другой реализации бинарных деревьев. Еще одно преимущество в том, что отсутствует overhead по памяти, так как не нужно хранить никакой дополнительной информации.
Дерево — это структура, данные в которой данные находятся в Nodes. У каждого Node могут быть один или несколько дочерних и только один родитель.
Вставка O(LogN), удаление O(LogN), поиск O(LogN)
Свойства дерева поиска:
- оба поддерева — левое и правое — являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше либо равны, нежели значение ключа данных самого узла X;
- у всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных самого узла X.
Чем полезно Binary search tree
- Для быстрого поиска данных.
- Для хранения данных в отсортированном виде с возможностью быстро их добавлять и удалять.
Деревья двоичного поиска позволяют иметь двоичный поиск для быстрого поиска, добавления и удаления элементов данных и могут использоваться для реализации динамических наборов и таблиц поиска. Порядок узлов в BST означает, что каждое сравнение пропускает примерно половину оставшегося дерева, поэтому весь поиск занимает время, пропорциональное двоичному логарифму количества элементов, хранящихся в дереве. Это намного лучше, чем линейное время, необходимое для поиска элементов по ключу в (несортированном) массиве, но медленнее, чем соответствующие операции с хеш-таблицами.
Основное преимущество двоичных деревьев поиска перед другими структурами данных состоит в том, что связанные алгоритмы сортировки и алгоритмы поиска, такие как обход по порядку (Симметричный/In-order), могут быть очень эффективными.
Двоичные деревья поиска - это фундаментальная структура данных, используемая для построения более абстрактных структур данных, таких как наборы, мультимножества и ассоциативные массивы.
Способы обхода дерева
Обход означает посещение всех узлов дерева. «Обход в глубину» или «Поиск в глубину» - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных.
(Поиск в глубину Depth-First Search DFS - На каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу — узлу на том же уровне. Реализуется за счет использованием рекурсии, или с использованием стека)
Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.
DFS применяется в алгоритме нахождения компонентов сильной связности в ориентированном графе.
Для обхода в глубину существует рекурсивная реализация без стека, рекурсивная реализация со стеком и итеративная реализация со стеком.
-
В симметричном порядке
In-order(слева направо) — инфиксная форма, левое поддерево → корень → правое поддерево. -
В обратном порядке
Post-order(снизу вверх) — постфиксная форма, левое поддерево → правое поддерево → корень. -
В прямом порядке
Pre-order(сверху вниз) — префиксная форма, корень → левое поддерево → правое поддерево.
(Поиск в ширину Breadth-first — обход узлов дерева по уровням. Реализуется за счет использования очереди)
- В ширину: от корня и далее
Для бинарных деревьев поиска симметричный обход проходит все узлы в отсортированном порядке. Если мы хотим посетить узлы в обратно отсортированном порядке, то в коде рекурсивной функции симметричного обхода следует поменять местами правого и левого потомка.
Поиск в ширину (Breadth-First Search BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).
BFS применяется для нахождения кратчайшего пути в графе, в алгоритмах рассылки сообщений по сети, в сборщиках мусора, в программе индексирования – пауке поискового движка.
Mетоды прохождения деревьев: рекурсия, очередь, стек
Рекурсивное определение бинарного дерева определяет эту структуру как корень с двумя поддеревьями, которые идентифицируются полями левого и правого указателей в корневом узле. Сила рекурсии проявляется в методах прохождения деревьев. Каждый алгоритм прохождения дерева выполняет в узле три действия: заходит в узел и рекурсивно спускается по левому и правому поддеревьям. Спустившись к поддереву, алгоритм определяет, что он находится в узле, и может выполнить те же три действия. Спуск прекращается по достижении пустого дерева (указатель == NULL). Различные алгоритмы рекурсивного прохождения отличаются порядком, в котором они выполняют свои действия в узле. Мы изложим симметричный и обратный методы, в которых сначала осуществляется спуск по левому поддереву, а затем по правому.
class BinaryTreeNode {
traverseRecursive(node) {
if (node != null) {
console.log(`node = ${node.val}`);
traverseRecursive(node.left);
traverseRecursive(node.right);
}
}
traverseWithStack() {
let stack = [];
stack.push(this);
while (stack.length > 0) {
let currentNode = stack.pop();
console.log(`node = ${currentNode.val}`);
if (currentNode.right != null) {
stack.push(currentNode.right);
}
if (currentNode.left != null) {
stack.push(currentNode.left);
}
}
}
traverseWithQueue() {
let queue = [];
queue.push(this.root);
while (queue.length > 0) {
let currentNode = queue.shift();
console.log(`node = ${currentNode.val}`);
if (currentNode.left) {
queue.push(currentNode.left);
}
if (currentNode.right) {
queue.push(currentNode.right);
}
}
}
}
Симметричный метод поиска в глубину
Симметричный метод In-order прохождения начинает свои действия в узле спуском по его левому поддереву. Затем выполняется второе действие - обработка данных в узле. Третье действие - рекурсивное прохождение правого поддерева. В процессе рекурсивного спуска действия алгоритма повторяются в каждом новом узле.
In-order обход используется как раз когда нам надо проверять в начале детей и только потом подыматься к родительским узлам.
Обратный метод поиска в глубину
При Post-order обратном прохождении посещение узла откладывается до тех пор, пока не будут рекурсивно пройдены оба его поддерева. Порядок операций дает так называемое LRN (left, right, node) сканирование.
- Прохождение левого поддерева.
- Прохождение правого поддерева.
- Посещение узла.
Post-order обход используется когда нам нужно начать-так сказать с листов и завершить главным узлом — тоесть разложить дерево на то, как оно строилось.
Прямой метод поиска в глубину Pre-order определяется посещением узла в первую очередь и последующим прохождением сначала левого, а потом правого его поддеревьев.
Pre-order стоит использовать именно тогда, когда вы знаете что вам нужно проверить руты перед тем как проверять их листья.
_4_
_3_ _9_
_1_ _7_ 10
2 6 8
Прямой/Pre-order: 4 3 1 2 9 7 6 8 10
Симметричный/In-order: 1 2 3 4 6 7 8 9 10
Обратный/Post-order: 2 1 3 6 8 7 10 9 4
Breadth-First Search: 4 3 9 1 7 10 2 6 8
Какой из методов использовать?
- если вы знаете что решение где-то не далеко от вашей ноды — то лучше использовать обход в ширь, чтоб не закапываться глубоко в дерево
- если дерево очень глубокое, а решение редки — то лучше все таки попробовать поиск в ширь
- если дерево очень широкое, то можно попробовать поиск в глубь, потому как поиск в ширь может забрать слишком много времени.
Идеальная сбалансированность — это свойство дерева, при котором все его уровни, иногда кроме последнего, полностью заполнены. Дерево с максимально возможной высотой (а) называется разбалансированным или вырожденным деревом. Оно не отличается от двусвязного списка, значит, теряет свое основное преимущество — скорость поиска.
Состояние идеальной сбалансированности в дереве трудно поддерживать. Любое добавление или удаление узла в сбалансированном дереве может привести к ситуации, когда дерево выйдет из идеально сбалансированного состояния. В таком случае скорость поиска будет значительно деградировать после каждой вставки или удаления узла.
Чтобы вернуть дерево в сбалансированный вид, его перестраивают после каждой манипуляции с составом узлов.
Стоит обратить внимание на АВЛ-деревья и красно-черные деревья, они являются максимально балансированными типами деревьев.
Ребалансировка деревьев осуществляется при помощи специальных механизмов — методов вращения. Вращения бывают двух видов: левое и правое.
Вращение вправо выполняется за три шага:
- Текущий корень поддерева (D) заменяется на левый дочерний узел (B)
- Предыдущий корень (D) становится правым дочерним узлом для (B)
- Предыдущее правое поддерево узла (B) становится левым поддеревом для (D)
Вращение влево выполняется аналогично:
- Текущий корень поддерева (D) заменяется на правый дочерний узел ©
- Предыдущий корень (D) становится левым дочерним узлом для ©
- Предыдущее левое поддерево узла © становится правым поддеревом для (D)
Hands-On-Data-Structures-and-Algorithms-with-Rust
...
Куча является максимально эффективной реализации очереди с приоритетом. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких как алгоритм Дейкстры на d-кучах и сортировка методом пирамиды.
Двои́чная ку́ча, пирами́да, или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия:
Значение в любой вершине не меньше, чем значения её потомков.
Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
Последний слой заполняется слева направо без «дырок».
Данные в нём хранятся последовательно: каждый узел — это префикс, по которому находятся следующие узлы.
Чем полезен Trie
- Разновидность дерева для строк, быстрый поиск. Словари. Т9.
- Для хранения данных, которые нужно выдавать по цепочке. Например, слова для функции автозаполнения в телефоне: в зависимости от одной набранной буквы дерево выдаёт следующие.
- Для хранения данных, у которых есть повторяющиеся участки. Например IP-адресов.
Граф — это более общий случай дерева. Иногда деревья называют ациклическими графами.
По такому принципу устроены социальные сети: Nodes (узлы) — это люди, а Edges (рёбра) — их отношения.
Storage O(V+E), Add Vertex O(1), Add Edge O(1), Remove Vertex O(V+E), Remove Edge O(E), Query O(V)
Отличий у этих структур данных два:
- В графе возможны циклы, то есть «ребёнок» может быть «родителем» для того же элемента.
- Рёбра тоже могут нести смысловую нагрузку, то есть нужно сохранять их значения.
Чем полезен Graph
- Для хранения информации, связанной друг с другом сложными соотношениями.
- Для анализа соотносящейся друг с другом информации.
- Для построения маршрута из точки А в точку Б.
Графы бывают:
simple(простые)nonsimple with multiple edges(многогранные)nonsimple with loop(петля)
Edges графов бывают:
Directed(ориентированные) У ориентированных рёбра между узлами имеют направление, так что порядок элементов важен.
Edges Directed графов бывают:
-
Unweighted- без весов, все ребра равнозначные -
Weighted- с весами, ребра имеют вес -
Undirected(неориентированные). У неориентированных направлений нет, и элементы можно читать и обходить в любом порядке.
Данные у графа могут быть:
- sparse (разреженным) - когда мало связей между узлами
- tight (плотным) - когда узлы с множетсвом связей
Размер графа это количество edges,а порядок графа это количество nodes.
Реализации графов
-
Матрица смежности - двумерная матрица размера
n x n, где каждой вершине соответсвует ячейка сязи равной 1 если есть связь или 0 если нет. Чтобы обозначить вес каждой связи, используют числа больше единицы. Не еффективна при разреженном графе, может быть неэффективна по памятиO(n^2)и сложности выполнения операций. Матрицы смежности очень эффективны для проверок — нужно считать и сравнить всего одну ячейку. Но что, если мы хотим для заданной вершины иметь возможность быстро пройтись по всем её соседям? Здесь ничего быстрееO(n)не получится. Tight (плотные) графы, имеющие большое количество ребер, следует хранить при помощи матриц смежности -
Список смежности - Список смежности можно представить как перечень элементов, где слева находится один узел, а справа — все остальные узлы, с которыми он соединяется. Здесь асимптотика по памяти и времени считывания
O(n+m), так как мы храним суммарно2mребер иnвекторов. Sparse (разреженные) графы, имеющие малое количество ребер, оптимальнее хранить при помощи списков смежности
Planar graph (планарный) - если его можно разложить на плоскости так, чтобы его ребра не пересекались в точках, отличных от вершин.
Bipartite graph (двудольный) - если его вершины которого можно разделить на два множества таких, что ребра соединяют только вершины из разных множеств.
Общие алгоритмы обхода для просмотра рёбер и вершин графа
- Поиск в ширину (breadth-first search) – обход по уровням
- Поиск в глубину (depth-first search) – обход по вершинам
Алгоритмы для графов
Dijkstra's algorithm (Алгоритм Дейкстры) поиск кратчайшего пути Алгоритм A* Поиск в глубину Поиск в ширину Найти все кратчайшие пути от вершины Поиск всех путей Поиск самого длинного пути Найти Эйлерову цепь Найти Эйлеров цикл Найти Гамильтонов цикл Найти Гамильтонову цепь Алгоритм Флойда - Уоршелла Поиск минимального основного дерева Раскраска графа Упорядочить граф Поиск максимального потока Проверка изоморфности графов Максимальная клика (Max Clique) Расчитать степень вершин Поиск радиуса и диаметра графа Визуализация на основе весов Найти компоненты связности Матрица смежности Матрица инцидентности Матрица расстояний
Существует множество различных способов получения параллельного алгоритма решения задачи (распараллеливание имеющегося последовательного алгоритма или разработка нового параллельного алгоритма). Возможно, для осуществления распараллеливания алгоритм решения задачи придется заменить или модифицировать (например, устранить некоторые зависимости между операциями). Одним из методов, который позволяет извлечь из задачи большего параллелизма является метод раскраски графа. Представим задачу следующим образом: объекты — некие вычисления, между которыми надо разделить вычислительные ресурсы, способные работать параллельно друг другу. Какие-то вычисления могут выполняться в параллели друг другу, какие-то — нет. Соответственно, вершинная раскраска графа несовместимости вычислений и представляет собой искомое распределение. Основная цель раскраски графа — назначить цвет каждому узлу в графе так, чтобы никакие два соседа не имели одинакового цвета и в то же время использовать как можно меньше цветов.
(Задачи, которые можно решить с помощью графов)[https://graphonline.ru/wiki/%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8%D0%9A%D0%BE%D1%82%D0%BE%D1%80%D1%8B%D0%B5%D0%9C%D0%BE%D0%B6%D0%BD%D0%BE%D0%A0%D0%B5%D1%88%D0%B8%D1%82%D1%8C%D0%A1%D0%9F%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E%D0%93%D1%80%D0%B0%D1%84%D0%BE%D0%B2]
Поиск кратчайшего пути
Например алгоритм Дейкстры находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Стоит отметить, что этот алгоритм не работает с графами, где есть циклы с отрицательным весом дуг.
Алгоритм Беллмана — Форда может искать кратчайший путь в графах и с отрицательным весом дуг, но он медленнее, чем алгоритм Дейкстры.
Например, Алгоритм поиска A* часто используется в компьютерных играх. Так как в алгоритме А* используется эвристическое правило, он не всегда найдёт самый короткий пусть, но найдёт близкий к самому короткому. Алгоритм поиска A* работает быстрее алгоритма Дейкстры.
Алгоритм Дейкстры идеально подходит для ситуаций, когда вы заранее не знаете конечную точку. Он вычисляет кратчайшее расстояние от исходной точки до всех остальных вершин в графе. Это делает его идеальным для задач, где важно знать расстояние до всех точек, а не только до конечной точки. Сложность O(V^2+E)
С другой стороны, алгоритм A* является более целенаправленным и эффективным для задач, когда известна конечная цель. Он использует эвристику для оценки расстояния до конечной точки и стремится минимизировать количество обрабатываемых вершин.
Алгоритм Дейкстры, будучи жадным алгоритмом, строит кратчайший путь, но не всегда делает это наиболее эффективным образом. Он обрабатывает все вершины в графе, что может привести к излишнему использованию ресурсов, особенно в больших графах.
Алгоритм A*, используя эвристическую функцию, обходит только те вершины, которые, как предполагается, приведут к цели. Это может значительно уменьшить количество обрабатываемых вершин и увеличить производительность, особенно в больших графах.
Алгоритм Дейкстры может быть более эффективным в отношении использования памяти, поскольку он не требует хранения всех вершин в открытом списке, как это делает алгоритм A*.
Алгоритм A*, с другой стороны, может требовать значительного объема памяти, особенно в больших графах, поскольку он должен отслеживать все открытые вершины. Это может быть проблематичным в областях с ограниченными ресурсами памяти.
Основная цель раскраски графа — назначить цвет каждому узлу в графе так, чтобы никакие два соседа не имели одинакового цвета и в то же время использовать как можно меньше цветов.
Поиск максимального потока
Алгоритмы поиска максимального потока находят максимальный поток из источника в сток. С помощью этого алгоритма можно решить задачи максимальной пропускной способности трубопровода или дорожной сети или компьютерной сети.
Поиск минимального остовного дерева
Алгоритм ищет дерево минимального веса в графе, которое бы соединяло все вершины. Этот алгоритм можно применять для дорожной или компьютерной сети, где вы хотите оптимизировать стоимость.
Предположим, имеются 7 компьютеров и разные способы проложить локальную сеть. Используя алгоритм поиска минимального остовного дерева, можно легко посчитать, где стоит проложить кабель, чтобы понадобилось минимальное количество кабеля.
Распределение рабочих
В распоряжении имеются N работников и M различных типов работ. Разные работники могут выполнять разные типы работ. Необходимо распределить работников, чтобы максимальное количество из их было занято.
Для решения строим граф, где соединяем работников с теми работами, которые они могут выполнять. Создаём псевдоисток, который соединяется со всеми работниками и сток, с которым соединены все типы работ. После этого ищем максимальный поток от истока к стоку.
Популярность веб-сайтов
Для составления рейтингов веб-сайтов поисковые системы часто учитывают, на какие сайты больше всего ссылаются другие сайты. Для этого можно составить граф, где каждая дуга определяет ссылку одного сайта на другой. Если размер вершин сделать зависимым от количества входящих дуг, то самые популярные сайты будут самыми большими. Для этой цели Граф Онлайн предлагает алгоритм "Визуализация на основе весов".
Теория 6 рукопожатий
Существует социологическая теория, которая гласит, что два любых человека на Земле разделены не более чем пятью уровнями общих знакомых. Таким образом можно говорить о шести уровнях связей. В графе вершинами является человек, а дугой - факт его знакомства с другим человеком. После этого необходимо найти кратчайший путь от одного человека до другого. Длина пути покажет через сколько рукопожатий знакомы эти два человека.
Рекомендация друзей
Социальные сети умеют рекомендовать пользователям людей, которых они возможно знают. Простейший алгоритм рекомендаций можно реализовать с помощью социального графа. Если запустить поиск в ширину из вершины интересующего нас человека, то он составит отсортированный список. Если пойти по этому списку с начала и рекомендовать людей, за исключением друзей, то самые первые из них могут быть знакомы пользователю.
Самый быстрый способ
Предположим, что что-то можно сделать разными способами. Например, добраться от дома до работы мы можем разными способами: поехать на машине, пойти пешком или воспользоваться самокатом. Все эти действия можно представить в виде графа, где дугами будет являться продолжительность определённых действий. Для поиска самого быстрого способа необходимо найти кратчайший путь между начальной и конечной вершиной.
Graphs in Rust: An Introduction to Petgraph
Самая быстрая и энергоэффективная реализация алгоритма BFS на различных параллельных архитектурах
