Почему появилась эта статья

Итак, я работаю над тем чтоб регулярно решать задачи на LeetCode, обычно всё идёт по плану. Ты берешь одну задачу за другой, проходишь их, и чувствуешь себя вполне уверенно. Но иногда происходит сбой. В моем случае этим "сбоем" стали задачи с бинарными деревьями, которые мне выпадали два дня подряд. И каждый раз, когда я видел их, меня бросало в дрожь, ведь я далеко не эксперт в этой области. Конечно, можно было бы пойти другим путем и "загуглить" решение, но мне нужно было понять механику и структуру этих деревьев, чтобы не просто решать задачи, а действительно понимать их.

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

Что такое деревья и графы?

Итак, начнем с основ. Графы и деревья — это структуры данных, которые мы используем для представления различных реальных систем. В графе у нас есть узлы (или вершины) и ребра (связи между ними). Графы могут быть ориентированными, где ребра имеют направление, и неориентированными, где направление не имеет значения. Там еще есть нюансы, но не предмет обсуждения сегодня.

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

Виды деревьев

1. Бинарные деревья поиска (BST) - структуры, в которых левый потомок всегда меньше родителя, а правый — больше. Очень удобно для быстрого поиска данных.
2. AVL-деревья - самобалансирующиеся бинарные деревья поиска. Здесь высота левого и правого поддеревьев всегда различается не более чем на один.
3. Красно-черные деревья - опять самобалансирующиеся деревья, но здесь каждый узел имеет цвет — красный или черный (спасибо Кэп) — что помогает поддерживать баланс при вставке или удалении элементов.

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

DFS (Depth First Search)

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

Как это работает:

1. Инициализация: Начинаем с корневого узла, помещаем его в стек.
2. Обход: Извлекаем узел из стека, обрабатываем его, добавляем его потомков в стек.
3. Продолжение: Алгоритм повторяется, пока стек не станет пустым.

Три основных подхода для обхода дерева с DFS:

1. Преордер (pre-order): сначала обрабатывается узел, затем его левый потомок, потом правый.
2. Инордер (in-order): сначала левый потомок, затем узел, потом правый потомок. Этот метод часто используется для деревьев поиска, поскольку выводит значения в отсортированном порядке.
3. Постордер (post-order): сначала обрабатываются оба потомка, а затем родительский узел. Используется, когда важно сначала обработать все зависимости перед узлом (например, удаление узлов в файловой системе).

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def dfs_preorder(node):
    if node:
        print(node.value)  # Сначала узел
        dfs_preorder(node.left)  # Левый потомок
        dfs_preorder(node.right)  # Правый потомок

# Создаем бинарное дерево
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

dfs_preorder(root)  # Вывод: 1, 2, 4, 5, 3

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

Преимущества DFS:

1. Меньше памяти: DFS использует стек, который хранит только узлы на текущем пути. Это означает, что при работе с глубокими, но узкими структурами памяти потребуется меньше, чем для BFS.
2. Полный обход: Позволяет обойти все пути, что полезно для задач, где важно исследовать каждый возможный маршрут (например, задачи по нахождению всех возможных решений).

Недостатки DFS:

1. Не гарантирует кратчайший путь: В отличие от BFS, DFS не всегда находит кратчайший путь, так как алгоритм сначала погружается вглубь.
2. Риск переполнения стека: Для глубоких рекурсивных графов или деревьев существует риск переполнения стека, особенно при использовании рекурсии.

BFS (Breadth First Search)

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

Как это работает:

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

from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()  # Извлекаем узел
        print(node.value)  # Обрабатываем узел
        if node.left:
            queue.append(node.left)  # Добавляем левый потомок
        if node.right:
            queue.append(node.right)  # Добавляем правый потомок

# Создаем бинарное дерево
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

bfs(root)  # Вывод: 1, 2, 3, 4, 5

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

Преимущества BFS:

1. Нахождение кратчайшего пути: В невзвешенных графах BFS всегда находит кратчайший путь от начального узла до целевого, так как он исследует каждый уровень графа.
2. Поиск на уровне: Удобно, когда вам нужно обрабатывать все узлы на одном уровне перед тем, как двигаться дальше.

Недостатки BFS:

1. Память: Поскольку BFS использует очередь для хранения узлов на текущем уровне, он может потреблять много памяти, особенно в широких графах или деревьях с большим количеством узлов на каждом уровне.

Когда использовать DFS, а когда BFS?

Когда использовать DFS?

DFS лучше всего подходит для задач, где требуется исследовать все возможные пути. Например, если вы решаете задачу поиска всех решений в лабиринте или ищете узел в дереве, который находится на неизвестной глубине. Также DFS может использоваться для поиска циклов в графе или для построения зависимостей (например, при сборке проекта).

Пример из реальной жизни:

Представьте, что вы ищете своего друга на огромной вечеринке, и вам нужно обойти каждый угол, каждый коридор, чтобы его найти. Это и есть DFS — вы исследуете один путь до конца, прежде чем вернуться и попробовать другой.

Когда использовать BFS?

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

Пример из реальной жизни:

Допустим, вы ищете ключи, которые где-то потеряли дома. С BFS вы сначала проверяете все комнаты на первом этаже, затем переходите ко второму этажу — обрабатываете по уровням.

Послесловие

Честно говоря, я планировал сделать для этой статьи красивые картинки и анимации, чтобы наглядно показать, как работают DFS и BFS. Но, как это обычно бывает, ресурса на это не хватило — а еще ведь надо регулярно публиковаться! Поэтому пришлось оставить это на потом и сосредоточиться на теоретической части. В следующий раз, возможно, вернусь к этой теме с анимациями. Пока что придется довольствоваться текстом и примерами на Python. Как говорится, не все коту масленица! 😅