05 — Деревья (BST, Trie) и графы (ориентированные/неориентированные, матрицы смежности)

Двоичное дерево поиска (Binary search tree)

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

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

• У каждого узла не больше двух дочерних.
• Если новое значение меньше, оно становится левым дочерним либо дочерним левого дочернего.
• Если значение больше, оно становится правым дочерним или дочерним правого дочернего.

Как применяют двоичные деревья:

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

Префиксное дерево (Trie)

Другие названия этой структуры данных — Бор и нагруженное дерево. Данные в нём хранятся последовательно: каждый узел — это префикс, по которому находятся следующие узлы.

Как применяют префиксные деревья:

• Для хранения данных, которые нужно выдавать по цепочке. Например, слова для функции автозаполнения в телефоне: в зависимости от одной набранной буквы дерево выдаёт следующие.
• Для хранения данных, у которых есть повторяющиеся участки. Например IP-адресов.

Пример хранения слов в префиксном дереве. Звёздочки означают конец префикса.

Граф (Graph)

Граф — это более общий случай дерева. Иногда деревья называют ациклическими графами. Отличий у этих структур данных два:

• В графе возможны циклы, то есть «ребёнок» может быть «родителем» для того же элемента.
• Рёбра тоже могут нести смысловую нагрузку, то есть нужно сохранять их значения.

Графы бывают ориентированные и неориентированные. У первых рёбра между узлами имеют направление, так что порядок элементов важен. У вторых направлений нет, и элементы можно читать и обходить в любом порядке.

У ориентированных графов важен порядок элементов, у неориентированных ― элементы можно менять местами.

Графы часто представляют в виде матрицы смежности.

Здесь каждая строка или столбец — узел. 1 в ячейке означает, что между узлами есть связь, 0 — что связи нет. Если у связей, то есть рёбер графа, есть вес, он как раз может быть помещён в ячейку

Как применяют графы:

• Для хранения информации, связанной друг с другом сложными соотношениями.
• Для анализа соотносящейся друг с другом информации.
• Для построения маршрута из точки А в точку Б.

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