Объяснение алгоритмов обхода дерева с примерами на Python

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

  • Корневой узел: каждое дерево имеет один узел, обозначенный как корневой узел, который является узлом наверху дерева и является узлом, не имеющим родительских узлов.
  • Родительский узел: родительский узел — это предшествующий ему узел, и каждый узел, кроме корневого, имеет один родительский узел.
  • Дочерний узел. Дочерний узел — это следующий за ним узел. В зависимости от типа дерева каждый узел может иметь различное количество дочерних узлов.

Типы древовидных структур данных

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

  1. Двоичное дерево. Двоичное дерево – это дерево, в котором каждый узел может иметь не более двух дочерних узлов, как следует из названия "бинарное".
  2. Двоичное дерево поиска (BST). BST — это частный случай двоичного дерева, в котором узлы упорядочены по их значениям. Для каждого родительского узла левый дочерний узел имеет меньшее значение, а правый дочерний узел — большее значение. Эта структура ускоряет поиск и, следовательно, полезна для алгоритмов поиска и сортировки.
  3. Кучи: куча – это специальная древовидная структура данных. Существует два типа куч: i) минимальная куча – это древовидная структура, в которой каждый родительский узел меньше или равен своему дочернему узлу; ii) максимальная куча — это древовидная структура, в которой каждый родительский узел больше или равен своему дочернему узлу. Этот тип структуры данных удобен для реализации приоритетных очередей, где элементы имеют приоритет по весу. Обратите внимание, что в Python есть встроенная библиотека heapq с функциями для выполнения различных операций со структурой данных кучи.

Алгоритмы обхода дерева

После рассмотрения распространенных типов древовидных структур данных ниже приведены некоторые распространенные примеры алгоритмов обхода дерева и их реализации в Python.

Поиск в ширину (BFS)

Поиск хлеба в первую очередь (BFS) — это распространенный алгоритм, используемый для обхода двоичного дерева поиска (BST) или графа в систематическом порядке. Он начинается с корневого узла на уровне 0 и посещает узлы по одному, двигаясь горизонтально от одной стороны к другой, пока не будет найден нужный узел или не будут посещены все узлы. Алгоритм сначала ищет вширь, а затем углубляется, отсюда и название «хлебный поиск».

Временная сложность BFS равна O(n), потому что размер дерева определяется длиной поиска элемента, а каждый узел посещается один раз. Ниже приведена реализация на Python:

def bfs(graph, source):
   """Function to traverse graph/ tree using breadth-first search
   Parameters:
   graph (dict): dictionary with node as key and 
                 list of connected nodes as values.
   source (str): source node to start from, usually 
                 the root node of the tree.
   Returns:
   bfs_result (list): list of visited nodes in order.
   """
   # Define variables
   bfs_result = []
   queue = []
   # Add source node to queue
   queue.append(source)
   while queue:
     # Visit node at front of queue
     node = queue.pop(0)
     # Check if we have visited this node before
     if node not in bfs_result:
        # Mark node as visited
        bfs_result.append(node)
        # Add all neighbor nodes to queue
        for neighbor in graph.get(node, []):
           queue.append(neighbor)
   return bfs_result

Поиск в глубину

Поиск в глубину (DFS) — это еще один вариант алгоритма обхода дерева, в котором он также начинается с корневого узла, но перемещается вниз по ветви и идет так далеко вниз по ветви, как только может. Если нужный узел не находится в этой ветви, он возвращается и выбирает другую ветвь, чтобы спуститься. Алгоритм делает это до тех пор, пока не будет найден нужный узел или не будут посещены все узлы. Алгоритм сначала исследует ветвь (вглубь), прежде чем перейти к другой ветви, отсюда и название «поиск в глубину».

Временная сложность DFS также равна O(n) по тем же причинам, что и BFS. Ниже приведена реализация на Python:

def dfs(graph, source):
   """Function to traverse graph/ tree using depth-first search
   Parameters:
   graph (dict): dictionary with node as key and 
                 list of child nodes as values.
   source (str): source node to start from, usually 
                 the root node of the tree.
   Returns:
   dfs_result (list): list of visited nodes in order.
   """
   # Define variables
   dfs_result = []
   queue = []
   # Add source node to queue
   queue.append(source)
   while queue:
      # Get last item in queue
      node = queue.pop()
      # Check if we have visited node before
      if node not in dfs_result:
         dfs_result.append(node)
         # Add neighbors to queue
         for neighbor in graph.get(node, []):
            queue.append(neighbor)
   return dfs_result

Заключение

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

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

См. больше из этой серии Объяснение алгоритмов: №1: рекурсия, №2: сортировка, №3: поиск, №4: жадные алгоритмы, №5: динамическое программирование, №6: дерево обход (текущая статья).