Рубрики

BFS против DFS для двоичного дерева

Что такое BFS и DFS для двоичного дерева?
Дерево обычно обходится двумя способами:

BFS and DFSs of above Tree

Breadth First Traversal : 1 2 3 4 5

Depth First Traversals:
      Preorder Traversal : 1 2 4 5 3 
      Inorder Traversal  :  4 2 5 1 3 
      Postorder Traversal : 4 5 2 3 1

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

Есть ли разница с точки зрения сложности времени?
Все четыре обхода требуют времени O (n), поскольку они посещают каждый узел ровно один раз.

Есть ли разница с точки зрения Extra Space?
Есть разница с точки зрения необходимого дополнительного пространства.

  1. Дополнительное пространство, необходимое для обхода порядка уровней, составляет O (w), где w — максимальная ширина двоичного дерева. При обходе порядка уровней очередь одна за другой хранит узлы разного уровня.
  2. Дополнительное пространство, необходимое для первых обходов глубины, составляет O (h), где h — максимальная высота бинарного дерева. В глубинах первого обхода стек (или стек вызовов функций) хранит всех предков узла.

Максимальная ширина двоичного дерева на глубине (или высоте) h может составлять 2 ч, где h начинается с 0. Таким образом, максимальное количество узлов может быть на последнем уровне. И наихудший случай возникает, когда двоичное дерево представляет собой совершенное двоичное дерево с номерами узлов, такими как 1, 3, 7, 15 и т. Д. В худшем случае значение 2 чCeil (n / 2) .

Высота для сбалансированного бинарного дерева — O (Log n). Наихудший случай имеет место для перекошенного дерева, а наихудшая высота становится O (n).

Таким образом, в худшем случае требуется дополнительное пространство O (n) для обоих. Но худшие случаи происходят для разных типов деревьев.

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

Как выбрать один?

  1. Дополнительное пространство может быть одним из факторов (объяснено выше)
  2. Обход в глубину обычно является рекурсивным, а рекурсивный код требует накладных расходов на вызов функции.
  3. Наиболее важные моменты: BFS начинает посещать узлы из корня, а DFS начинает посещать узлы из листьев. Поэтому, если наша проблема заключается в поиске чего-то более близкого к корневому каталогу, мы бы предпочли BFS. И если целевой узел находится близко к листу, мы бы предпочли DFS.

Упражнение:
Какой обход следует использовать для печати листьев бинарного дерева и почему?
Какой обход следует использовать для печати узлов на k-м уровне, где k намного меньше общего числа уровней?

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

Рекомендуемые посты:

BFS против DFS для двоичного дерева

0.00 (0%) 0 votes