Двоичные деревья - это общая структура данных для быстрого доступа к данным. Сначала в ширину и сначала в глубину - это две важные методологии, которые необходимо понимать при работе с деревьями. Прежде чем мы перейдем к этому, давайте рассмотрим структуру данных двоичного дерева.
Обратите внимание, что двоичное дерево поиска и двоичное дерево - это не одно и то же. Деревья двоичного поиска - это тип структуры данных, в которой значение в левом узле меньше родительского значения, а правое значение больше родительского значения. В двоичном дереве каждый узел имеет два соединения независимо от значения.
Со структурами данных вы можете выполнять четыре основных типа действий: Доступ, Поиск, Вставка и Удаление.
Я рекомендую посмотреть это видео с HackerRank с Гейл Лаакманн МакДауэлл, автором Cracking the Coding Interview. Она подробно описывает структуры данных, DFS и BFS, а также детали реализации каждого алгоритма.
Чтобы было ясно, графики и деревья - это структуры данных. DFS и BFS - это алгоритмы. Мы используем структуры данных в наших алгоритмах.
Дерево двоичного поиска
Бинарное дерево поиска - это структура данных, которая упрощает поиск и организацию данных.
Поиск в глубину (DFS)
Поиск в глубину - это обычно рекурсивный алгоритм. Обязательно используйте флаг isVisited, чтобы не попасть в бесконечный цикл.
При поиске в глубину, начав путь, мы не останавливаемся, пока не дойдем до конца. Другими словами, мы проходим через одну ветвь дерева, пока не дойдем до листа, а затем возвращаемся к стволу дерева.
Узел в двоичном дереве может иметь только две ссылки. временная сложность зависит от количества узлов в дереве. O (n), где n - количество узлов в дереве. Стек вызовов увеличивается до тех пор, пока мы не достигнем корневого узла, поэтому он не работает эффективно для деревьев с большим количеством глубоко вложенных узлов, иначе стек вызовов может быть превышен. Высота дерева показывает, сколько памяти нам понадобится.
Поиск в ширину (BFS)
Используйте очередь.
