По сути, деревья — это тип графа.
➢ Состоит из узлов, каждый из которых имеет корневой (родительский) узел.
➢ Корневой узел имеет ноль или более дочерних узлов.
➢ Дочерние узлы могут иметь ноль или более дочерних узлов.
Отвечая на задачи, связанные с деревьями и графами, мы можем столкнуться с неоднозначными деталями и неверными предположениями. Обязательно проясните все неясности со своим интервьюером.
Типы деревьев
1. Деревья против двоичного дерева
Ø Дерево — это тип дерева, узлы которого могут иметь любое количество дочерних элементов.
Ø Бинарное дерево — это дерево, в котором каждый узел имеет до двух дочерних элементов. Не все деревья являются бинарными.
2. Двоичное дерево поиска
Ø Бинарное дерево поиска соответствует свойству:
Все левые потомки ‹= корень ‹ все правые потомки
Примечание. Определение двоичного дерева поиска может различаться в зависимости от равенства. Некоторые могут определить его так, чтобы у него не было дубликатов. Другие могут определить это как наличие повторяющихся значений с правой стороны. Обязательно уточните это у интервьюера.
3. Сбалансированное дерево
Ø Не все деревья сбалансированы. Обратитесь за разъяснениями к интервьюеру здесь.
Ø Балансировка дерева не означает, что левое и правое поддеревья имеют полностью одинаковый размер. (Они называются «идеальными двоичными деревьями»).
Ø Дерево должно быть достаточно сбалансированным, чтобы обеспечить O(log n) для ВСТАВКИ, УДАЛЕНИЯ, ДОСТУПА и ПОИСКА.
4. Полное двоичное дерево.
Ø Каждый уровень дерева полностью заполнен, за исключением, пожалуй, последнего уровня.
5. Полное двоичное дерево.
Ø Каждый узел имеет либо ноль, либо двух дочерних элементов.
Ø Ни один узел не имеет только одного дочернего элемента
6. Идеальное двоичное дерево
Ø Тот, который одновременно полон и завершен. Все конечные узлы находятся на одном уровне, и этот уровень имеет максимальное количество узлов.
Ø Количество уровней = 2k -1 узлов, где k = нет. уровней.
Примечание: идеальные деревья редко встречаются в интервью; не думайте, что дерево идеально.
Обход двоичного дерева
Рассмотрим следующее дерево и соответствующие ему обходы:
1. Обход по порядку:
Слева -> Корень -> Справа
2,7,5,6,11,1,9,5,9
2. Обход предварительного заказа
Корень -> Левый -> Правый
1,7,2,6,5,11,9,9,5
3. Обход после заказа
Слева -> Справа -> Корень
2,5,11,6,7,5,9,9,1
Примечание. Обычного обхода двоичного дерева недостаточно для однозначной сериализации дерева. Также требуется предварительный или пост-заказ.
Двоичные кучи
Ø Кучи — это полное двоичное дерево, элементы которого по существу отсортированы. Существует два типа кучи: минимальная куча и максимальная куча.
Ø Min-Heap — это полное двоичное дерево, в котором каждый узел меньше своих дочерних элементов. Следовательно, корень — это минимальный элемент дерева. Макс-кучи структурно эквивалентны, но их элементы расположены в порядке убывания, что делает корень максимальным элементом дерева.
С кучей можно выполнять две важные операции: вставку и извлечение.
1. Вставьте:
§ Вставка происходит в самом низу дерева, вставляя элемент в самое правое место, чтобы сохранить все свойства дерева.
§ После вставки элемента в самую правую позицию на последнем уровне мы меняем местами элемент с родительским элементом до тех пор, пока позиция элемента не станет такой, что свойство дерева минимальной кучи будет удовлетворено.
Примечание. Это занимает время O(log n), где n — количество узлов в куче.
2. Извлеките минимальный элемент:
§ Минимальный элемент кучи всегда находится наверху. Чтобы удалить его, мы меняем его местами с самым правым элементом нижнего уровня (последним элементом).
§ Затем мы меняем местами элемент (который теперь находится в корне) с одним из его дочерних элементов до тех пор, пока свойство Min-Heap не будет удовлетворено во всем дереве.
§ Решая, с каким дочерним узлом производить замену, мы обычно выбираем замену на меньший узел, чтобы сохранить свойство.
Примечание. Это занимает время O(log n), где n — количество узлов в куче.
ГРАФЫ
Не все графы являются деревьями. Дерево – это связный граф без цикла.
Ø Графы представляют собой совокупность узлов с ребрами между ними.
Ø Могут быть направленными (ребра в одном направлении) или ненаправленными (ребра, соединяющиеся в обоих направлениях)
Ø Графы могут иметь несколько подграфов, и если между каждой парой узлов существует путь, то этот граф называется связным графом.
Ø Граф может быть циклическим (с циклами) или ациклическим (без циклов).
Представление графиков
- Матрица смежности:
§ матрица nxn с Auv =1, если (u, v) — ребро
§ Работает для направленных и ненаправленных списков.
§ Пространство пропорционально n2.
§ Проверка ребра занимает время O(1).
§ Идентификация всех ребер занимает время O(n2).
2. Список смежности:
§ Работает для ориентированных и неориентированных графов
§ Каждое ребро является направленным.
§ Пространство, пропорциональное m+n
§ Проверка того, что (u, v) является ребром, занимает время O(deg(u)), где deg(u) = нет соседей u.
§ Идентификация всех ребер занимает время O(m+n).
Ø Неориентированный граф связен, если для каждой пары узлов u и v существует путь между u и v.
Ø Цикл в неориентированном графе — это путь V1, V2, … Vk-1, в котором V1 = Vk-1, k>1 и все ребра различны.
Ø Дерево: неориентированный граф является деревом, если он связен и не содержит циклов.
Теорема: Пусть G — неориентированный граф на n узлах. Любые два из следующих утверждений подразумевают третье.
· G подключен
· G имел n-1 ребер
· G не содержит цикла.
ОБХОД ГРАФА
Примечание: (Проблема с подключением к науке и технологиям, заданная в интервью на основе этого)
Ø Учитывая две точки S и T, существует ли путь между S и T?
S — T Задача о кратчайшем пути:
Учитывая две точки S и T, каков кратчайший путь между S и T?
Приложения: Facebook, прохождение лабиринта, число Кевина Бэкона, наименьшее количество переходов в сообщении. Сеть, номер Эрдос
Поиск в ширину
Мы начинаем с корня (или выбранного узла) и исследуем каждого соседа, прежде чем перейти к любому из других дочерних узлов. Его часто используют для вычисления кратчайшего пути.
Ø BFS использует очередь. Он посещает соседей А прежде, чем посетить кого-либо из его соседей.
Ø По сути, это поиск, который происходит уровень за уровнем.
Ø Находит все узлы, достижимые из начального узла S.
Ø Вычисляет расстояния от s до всех остальных вершин.
Пример БФС:
§ Начинайте с S
§ Откройте для себя все, что доступно.
§ Если у узла несколько соседей, они обрабатываются в алфавитном порядке.
Ø Выведите S из очереди и просмотрите всех соседей S на основе списка смежности. Они отмечены как dist = 1.
Ø Они также помечены как просмотренные. Они никогда больше не помещаются в очередь, если они доступны будущему узлу.
Ø Теперь мы выталкиваем A и смотрим на соседей A.
Обновленное расстояние = 1 + расстояние до исследуемого узла.
Поиск в глубину
Мы начинаем с корня (или выбранного узла) и полностью исследуем каждую ветвь, прежде чем переходить к любому из других дочерних элементов. Он часто используется, когда мы хотим посетить каждый узел графа (проще).
Ø Находит все узлы, достижимые из начального узла, S, вероятно, в другом порядке, чем BFS.
Ø Следуйте одному пути до конца, прежде чем исследовать другие.
Ø Реализовано с использованием стека.
Пример ДФС:
Ø Поместите корень (или начальный узел) в стек. Проходя следующие узлы, извлекайте элемент из стека и помещайте в стек его соседей по алфавиту.
Ø Теперь вытолкните элемент и нажмите на соседей «вытолкнутого элемента». Продолжайте этот процесс, пока стек не станет пустым.
Ø Отмеченные цифры обозначают порядок прохождения узлов.
Пример рекурсивного DFS:
Ø Начните с S, выберите первый узел в алфавитном порядке, т. е. в данном случае A.
Ø Из узла A выберите следующий узел среди соседей A, который появляется в алфавитном порядке, т. е. в данном случае B.
Соседями Ø B являются только D. Итак, следующий D пересекается.
Ø Далее, поскольку B не имеет соседей, он возвращается к узлу, где другие его соседи не пересекаются.
D → B → A
Все еще имеет непройденных соседей, т. е. G
Ø Теперь A проверяет своих соседей (обрабатывает свои узлы) и пересекает узел G.
Ø Пройдя все узлы A, мы возвращаемся к S.
Ø Мы обрабатываем оставшиеся узлы S в алфавитном порядке. Сначала мы идем к F и обнаруживаем, что у него есть соседи C и проходится E. C пересекается. C имеет соседей E. E пройден. Таким образом, E, I и H проходятся последовательно.
Что следует учитывать во время собеседования
1) Вы должны быть хорошо знакомы с написанием обходов по порядку, предзаказу и послезаказу как рекурсивно, так и итеративно.
2) Всегда проверяйте крайние случаи:
а. Пустое дерево
б. Один узел
в. Два узла
д. Очень перекошенное дерево (как связанный список)
3) Методы решения «деревянных задач»
1. Обход по уровням. Когда вас просят пройти по дереву по уровням, лучше всего использовать поиск в ширину.
2. Использование очередей и стеков полезно при попытке реализовать BFS и DFS
3. Используйте рекурсию: наиболее распространенный подход к решению проблем с деревьями
Метод 1: решение сверху вниз (обход предварительного заказа)
Мы начинаем с корня и придумываем некоторые значения. Мы передаем эти значения ее дочерним элементам при рекурсивном вызове функции. Ниже приведен псевдокод:
top_down (корень, параметры):
1. Вернуть конкретное значение для нулевого узла.
2. При необходимости обновите ответ.
3. left_ans = top_down(root.left, left.params)
4. right_ans = top_down(root.right, right.params)
5. вернуть ответ, если необходимо
Пример. Найдите максимальную глубину дерева.
1. возврат, если root равен нулю
2. если корень является листовым узлом:
3. ответ = макс(ответ, глубина)
4. максимальная_глубина(корень.левый, глубина + 1)
5. максимальная_глубина(корень.справа, глубина + 1)
Метод 2: решение снизу вверх (обход после заказа)
Это еще одно рекурсивное решение, в котором вся функция вычисляется для дочерних узлов, а затем выдает ответ в соответствии с возвращаемыми значениями и значением самого текущего узла. Этот обход представляет собой обход после заказа.
дно_вверх (корень, параметры):
1. вернуть конкретное значение для нулевого узла
2. left_ans = Bottom_up(root.left)
3. правый_анс = нижний_вверх(корень.правый)
4. возвращать ответы
Пример. Найдите максимальную глубину дерева.
1. вернуть 0, если root равен нулю
2. левая_глубина = максимальная_глубина(корень.левый)
3. правая_глубина = максимальная_глубина(корень.справа)
4. вернуть максимум (левая_глубина, правая_глубина) + 1
Примечание. Чтобы выяснить, какой метод рекурсии использовать, мы можем задать себе вопрос: можем ли мы использовать параметры и значение самого узла, чтобы определить, какие параметры следует передавать дочерним элементам? Если да, попробуйте решить проблему, используя подход «сверху вниз».
В противном случае, если ответ положительный на вопрос: «Для узла в дереве, если вы знаете ответ его дочерних элементов, можете ли вы вычислить ответ узла», выберите подход «снизу вверх». сильный>
4) Сложности пространства и времени
Поставьте лайк и поделитесь, если вам понравился этот контент!
