Как только вы узнаете достаточно о различных структурах данных, вы начинаете думать про себя: правильно, так… в чем смысл, опять же? Почему у нас вообще есть все эти структуры?

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

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

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

Крошечный вкус обхода дерева

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

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

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

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

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

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

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

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

Но мы пока не будем говорить о поиске в ширину. Вместо этого давайте обратимся ко второму из двух вариантов: поиск в глубину (DFS).

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

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

Это дерево было таким глубоким, что я чуть не утонул

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

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

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

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

В обоих случаях нам нужно сделать три вещи:

  1. Считайте данные узла, который мы проверяем или обновляем.
  2. Отметьте узел слева от узла (левая ссылка), на котором мы сейчас находимся.
  3. Отметьте узел справа от узла (левая ссылка), на котором мы сейчас находимся.

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

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

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

Первая из этих распространенных стратегий DFS выглядит примерно так: а) прочитать данные узла, на котором мы находимся, б) посетить узел, на который имеется ссылка слева, если он существует, и в) посетить узел, на который имеется ссылка. право, если оно существует. Процесс чтения данных с последующим посещением левого узла, за которым следует правый узел, часто записывается в краткой форме как DLR, где D означает данные, L обозначает левый узел, а R обозначает правый узел.

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

  1. Предварительный заказ (DLR): прочтите данные узла, затем посетите левое поддерево / узлы, а затем правое поддерево / узлы.
  2. Inorder (LDR): посетите левое поддерево / узлы, затем прочтите данные узла и, наконец, посетите правое поддерево / узлы.
  3. Поступорядочение (LRD): посетите левое поддерево / узлы, затем правое поддерево / узлы и, наконец, прочтите данные узла.

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

На изображении ниже мы опробуем все три этих метода на двоичном дереве, в котором всего 12 узлов. Вот как выглядел бы каждый из этих обходов, если бы мы выводили имя каждого узла при его посещении:

Интересно! Если мы посмотрим, как работают эти три обхода, мы довольно быстро заметим, что вся краткая форма DLR на самом деле имеет значительный вес.

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

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

Наконец, в обходе после очередности мы сначала обращаемся к ссылке на левый узел, затем к правому узлу, а затем, если таковой не существует, мы читаем данные узла, на котором мы сейчас находимся. Вот почему мы читаем данные узла a, за которым следует узел c, перед чтением данных узла b . Мы заканчиваем чтением корневого узла в самом конце обхода (после посещения всех узлов в левом поддереве и правом поддереве), что соответствует сокращению для обхода после порядка: LRD.

Еще больше с рекурсией!

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

Думаю, это круто.

Но… как мы на самом деле подходим к реализации любой из этих стратегий? Конечно, с помощью рекурсии!

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

Возможно, вы уже видели, как стратегию «сначала в глубину» можно реализовать как рекурсивный метод. Если задуматься, становится все более и более ясным: мы делаем одно и то же - читаем данные, проверяем ссылку на левый узел и проверяем ссылку на правый узел - снова и снова, пока мы не пройдем через все узлы в дереве. Конечно, иногда мы выполняем эти три действия в немного порядке, в зависимости от того, какую стратегию мы выбрали, но тем не менее, мы делаем те же три действия в одном и том же порядке с каждым узлом. что мы посещаем.

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

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

Таким образом, количество времени, которое нам понадобится для обхода дерева с использованием DFS, прямо пропорционально количеству узлов в дереве. Временная сложность использования поиска в ширину в двоичном дереве составляет O (n), где n - количество узлов в дереве.

Если у нас 5 узлов, нам потребуется O (5), а если у нас есть 50 узлов, которые нужно посетить, это займет O (50) с точки зрения времени.

Хорошо, а как мы можем реализовать одно из этих узловых «сечений» в коде? Что ж, это может быть так же просто, как объект, и может выглядеть так:

node1 = {
  data: 1,
  left: referenceToLeftNode,
  right: referenceToRightNode
};

Это не так уж и плохо! Сделаем еще один шаг? Напишем функцию для стратегии поиска обхода предзаказов. Я буду использовать псевдокодирование в JavaScript, но, надеюсь, его будет легко перевести с одного языка на другой:

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

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

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

Но как насчет сложности пространства? Ну, поскольку DFS обычно реализуется рекурсивно, это приводит к тому, что мы вызываем одну функцию изнутри себя много раз. Давайте вернемся к нашему примеру дерева поперечного сечения. Если бы мы реализовали предварительный поиск, мы бы перемещались от узла 1 к 2, от 2 к 4 и от узла 4 к 8. Каждый раз, когда мы посещали один из этих узлов, мы вызывали бы функцию preorderSearch из первой функции. мы вызвали, когда передали корневой узел.

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

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

Как только мы достигнем листового узла, наша preorderSearch функция будет return, потому что мы передадим ей ссылки на left и right узлы, которые просто не будут существовать!

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

Когда мы делаем шаг назад, это на самом деле довольно мощно - мы можем так много узнать о сильных и слабых сторонах алгоритма, просто взглянув на структуру данных! И поскольку мы уже знаем, где используются деревья - например, в git bisect командах, и при реализации сложных структур, таких как лабиринты, - мы можем понять, насколько легко или сложно будет выполнить поиск по ним с помощью DFS, одним простым взглядом.

Не знаю, как вы, но я бы сказал, что мы на пути к тому, чтобы стать мастерами алгоритмов!

Ресурсы

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

  1. Бинарные деревья, профессор Х. Левент Акин.
  2. Traversals, Натан Лэндман, Карли Мур, Чимин Хим
  3. BFS vs DFS для двоичного дерева, GeeksforGeeks
  4. Приложения поиска в глубину, GeeksforGeeks
  5. Обход двоичного дерева: Preorder, Inorder, Postorder, mycodeschool