Привет, Хаброжители!

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

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

ДЕРЕВЬЯ И ГРАФЫ: ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

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

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

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

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

Деревья: типы и методы обхода

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

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

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

Двоичные деревья

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

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

Двоичные деревья поиска

Двоичные деревья поиска (Binary Search Tree, BST) — структура данных, используемая для представления данных с иерархической организацией, в которой все узлы соответствуют следующему свойству: левый дочерний узел меньше родительского, а правый дочерний — больше. Это свойство позволяет выполнять поиск, вставку и удаление за время O(log n), что делает двоичные деревья весьма эффективными.

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

Соблюдение принципов BST помогает поддерживать баланс и оптимизацию, делая работу по созданию и анализу алгоритмов эффективной.

Сбалансированные деревья

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

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

N-арные деревья

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

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

B-деревья

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

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

Методы обхода деревьев

Обход — это процесс посещения всех узлов дерева и выполнения операции в каждом узле. Далее мы рассмотрим несколько основных методов обхода и варианты их использования.

Обход по порядку (двоичные деревья)

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

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

Пример

def in_order_traversal(root):
  if root:
    in_order_traversal(root.left)
    print(root.data, end=' ')
    in_order_traversal(root.right)

Использование обхода по порядку в BST. При этом методе обходятся узлы BST, начиная с самого левого и заканчивая самым правым. Такой порядок позволяет получать доступ к данным в порядке возрастания, что очень полезно в различных приложениях. Ярким примером является создание упорядоченного списка из BST, который можно использовать для различных целей, таких как анализ, дальнейшая обработка или предоставление данных пользователям в доступном формате.

Обход в прямом порядке

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

Пример

def pre_order_traversal(root):
  if root:
    print(root.data, end=' ')
    pre_order_traversal(root.left)
    pre_order_traversal(root.right)

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

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

Обход в обратном порядке

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

Пример

def post_order_traversal(root):
  if root:
    post_order_traversal(root.left)
    post_order_traversal(root.right)
    print(root.data, end=' ')

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

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

Обход по уровням (в ширину)

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

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

Пример

from collections import deque

def level_order_traversal(root):
  if root is None:
    return

  queue = deque([root])
  while queue:
     node = queue.popleft()
     print(node.data, end=' ')
     if node.left:
       queue.append(node.left)
     if node.right:
       queue.append(node.right)

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

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

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

Расширенные концепции обхода

Обход Морриса для повышения эффективности использования пространства

Обход Морриса — это метод обхода деревьев, который позволяет отказаться от использования рекурсии или стека, что приводит к сложности O(1). Это означает, что при перемещении по дереву память будет использоваться по минимуму. Вместо того чтобы полагаться на дополнительные структуры данных, обход Морриса использует собственную структуру дерева для хранения и доступа к информации, что повышает эффективность использования памяти.

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

Потоковые двоичные деревья для эффективного обхода

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

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

Практическое применение деревьев

Синтаксические деревья в компиляторах

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

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

Деревья решений в машинном обучении

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

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

Объектные модели документов в браузерах

Объектные модели документов (Document Object Model, DOM) — ключевой аспект веб-разработки, влияющий на то, как браузеры читают веб-страницы и взаимодействуют с ними. По сути, это древовидная структура, представляющая различные элементы, составляющие веб-страницу.

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

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

Файловые системы в операционных системах

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

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

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

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

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

Графы: представление и основные алгоритмы

Графы, как легко адаптируемые структуры данных, прекрасно подходят для представления сложных отношений между объектами. Мы рассмотрим структуру графов и некоторые важные алгоритмы, разработанные для них.

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

Кроме того, мы рассмотрим некоторые базовые понятия теории графов: вершины, ребра и пути. Изучение этих элементов позволяет глубже понять структуру и поведение графов.

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

Основные понятия

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

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

Узлы и ребра

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

Ребра служат мостами, устанавливающими связи между данными сущностями. Эти связи выступают средством отображения взаимодействия различных сущностей или их зависимостей.

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

Ориентированные и неориентированные графы

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

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

Взвешенные графы

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

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

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

Представление графов

Существуют два основных способа представления графов в информатике — матрица смежности и список смежности.

Матрица смежности

Матрица смежности — важнейшая структура данных, которая служит для изображения графов. Она задается в виде двумерного массива, строки и столбцы которого соответствуют узлам графа. В этом массиве каждая ячейка [i][j] может содержать либо логическое значение, показывающее наличие или отсутствие ребра между узлом i и узлом j, либо числовое значение, определяющее вес ребра, если граф является взвешенным.

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

Пример

class Graph:
  def __init__(self, size):
    self.adj_matrix = [[0 for _ in range(size)] for _ in range(size)]

  def add_edge(self, start, end):
    self.adj_matrix[start][end] = 1
    self.adj_matrix[end][start] = 1 # Для неориентированного графа

  def remove_edge(self, start, end):
    self.adj_matrix[start][end] = 0
    self.adj_matrix[end][start] = 0 # Для неориентированного графа

# Пример использования
graph = Graph(3)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
print(graph.adj_matrix)

Список смежности

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

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

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

Пример

class Graph:
  def __init__(self, size):
    self.adj_list = [[] for _ in range(size)]

  def add_edge(self, start, end):
    self.adj_list[start].append(end)
    self.adj_list[end].append(start) # Для неориентированного графа

# Пример использования
graph = Graph(3)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
print(graph.adj_list)

Основные алгоритмы построения графов

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

Поиск в глубину (Depth-First Search, DFS) — алгоритм обхода, который начинает с выбранного узла и проходит по ветви как можно дальше, прежде чем вернуться назад. Этот метод особенно полезен в таких задачах, как решение головоломок, где для того, чтобы найти решение, нужно сначала изучить все возможные варианты.

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

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

Пример

def dfs(graph, start, visited=None):
  if visited is None:
    visited = set()
  visited.add(start)
  for neighbor in graph.adj_list[start]:
    if neighbor not in visited:
      dfs(graph, neighbor, visited)
  return visited

Поиск в ширину

Поиск в ширину (Breadth-First Search, BFS) — алгоритм обхода, который посещает узлы поуровнево, начиная с корневого и двигаясь вширь. То есть сначала он проверяет все узлы, ближайшие к корню, и только потом переходит на следующий уровень. Этот метод особенно эффективен для определения кратчайшего пути в невзвешенных графах. Ключевое преимущество BFS — его способность гарантировать обнаружение кратчайшего пути между двумя узлами, если таковой существует.

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

Пример

from collections import deque

def bfs(graph, start):
  visited = set()
  queue = deque([start])
  while queue:
    vertex = queue.popleft()
    if vertex not in visited:
      visited.add(vertex)
      queue.extend(set(graph.adj_list[vertex]) - visited)
  return visited

Алгоритм Дейкстры (для взвешенных графов)

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

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

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

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

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

Практическое применение графов

• Социальные сети. Графовые структуры используются на платформах некоторых социальных сетей. Пользователи представлены в виде узлов, а связи, такие как дружба или профессиональное взаимодействие, — в виде ребер. Такое графическое представление не только упрощает визуальную сложность сетей, но и помогает пользователям легко ориентироваться в обширной сети связей на этих платформах.
• Маршрутизация в Интернете. Маршрутизаторы используют графовые алгоритмы, в том числе алгоритм Дейкстры, для поиска наиболее эффективных путей передачи пакетов данных по сети. Эти алгоритмы учитывают различные аспекты топологии сети, такие как пропускная способность канала, задержка и перегруженность, чтобы выполнять эффективную маршрутизацию пакетов. Такой оптимальный поиск путей обеспечивает своевременную доставку данных, сокращает задержки и повышает общую эффективность сети.
• Рекомендательные системы. Платформы электронных продаж и контента, такие как Amazon и Netflix, используют алгоритмы на основе графов в своих рекомендательных системах. Они связывают пользователей с товарами или контентом, соответствующими их предпочтениям, на основе индивидуального выбора пользователей. Эти алгоритмы анализируют обширные данные о пользователях, выявляют тенденции и дают соответствующие рекомендации, постоянно предлагая новые варианты.
• Карты Google. Графические алгоритмы используются для определения наиболее эффективных маршрутов между населенными пунктами, учитывая расстояние, трафик, перекрытие дорог и другие важные данные. Благодаря этим усовершенствованным алгоритмам карты Google предоставляют точные данные в режиме реального времени, гарантируя пользователям беспроблемную поездку.

Практические советы

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

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

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

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

Практические упражнения

1. Реализация дерева двоичного поиска.

• Создайте базовое двоичное дерево поиска с методами вставки и обхода по порядку.
• Вставьте числа 10, 5, 15, 2, 5, 13, 22, 1, 14, а затем выполните обход по порядку.

Решение

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

  def insert(self, value):
    new_node = Node(value)
    if self.root is None:
      self.root = new_node
      return
    current = self.root
    while True:
      if value < current.value:
        if current.left is None:
          current.left = new_node
          return
        current = current.left
      else:
        if current.right is None:
          current.right = new_node
          return
        current = current.right

  def in_order_traversal(self, node, result=[]):
    if node:
      self.in_order_traversal(node.left, result)
      result.append(node.value)
      self.in_order_traversal(node.right, result)
    return result

# Тест
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
  bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Вывод: [1, 2, 5, 5, 10, 13, 14, 15, 22]

2. Реализация графа с помощью списка смежности.

• Создайте класс Graph с методами для добавления ребер и выполнения поиска в ширину.
• Добавьте ребра, соединяющие узлы 0, 1, 2, 3 и 4 нелинейным образом, и выполните поиск в ширину, начиная с узла 0.

Решение

from collections import defaultdict, deque

class Graph:
  def __init__(self):
    self.graph = defaultdict(list)

  def add_edge(self, u, v):
    self.graph[u].append(v)

  def bfs(self, start):
    visited = set()
    queue = deque([start])
    while queue:
      vertex = queue.popleft()
      if vertex not in visited:
        print(vertex, end=' ')
        visited.add(vertex)
        queue.extend(set(self.graph[vertex]) - visited)

# Тест
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
  g.add_edge(u, v)
g.bfs(0) # Вывод: 0 1 2 3 4

3. Поиск в глубину на графе.

• Реализуйте поиск в глубину для графа, созданного в упражнении 2.
• Выполните поиск в глубину, начиная с узла 0.

Решение

def dfs(graph, start, visited=None):
  if visited is None:
    visited = set()
  visited.add(start)
  print(start, end=' ')
  for neighbor in graph.graph[start]:
    if neighbor not in visited:
      dfs(graph, neighbor, visited)

# Тест
dfs(g, 0) # Выход: 0 1 2 4 3

Резюме

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

Мы начали с деревьев и исследовали их иерархическую природу, благодаря которой они отлично подходят для представления данных, связанных отношением «предок — потомок». Мы рассмотрели простые двоичные деревья, каждый узел которых имеет не более двух потомков, и более сложные структуры, такие как двоичные деревья поиска, деревья AVL и B-деревья, а также познакомили вас с вариантами их применения.

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

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

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

Упражнения данной главы помогли вам на практике закрепить полученные знания и улучшить навыки программирования.

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

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

Более подробно с книгой можно ознакомиться на сайте издательства:

» Оглавление
» Отрывок

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Python