Есть много статей, в том числе и на хабре, где подробно рассказывается про бинарные деревья как про структуру данных. В этой статье я больше сосредоточусь на подходах к решению алгоритмических задач, где используются бинарные деревья.
Немного теории для общего понимания сути.
Бинарное дерево - это иерархические структура данных, в которой каждый узел имеет не более двух дочерних узлов. Узлы обычно называются правыми и левыми потомками. При этом каждый из потомков, в свою очередь тоже является узлом, который может иметь двух потомков. Если у узла нет потомков, такой узел называют листом.
Не путать бинарное дерево с бинарным деревом поиска. Второе отличается тем, что хранит данные в отсортированном виде и обладает следующими свойствами:
Все значения в узлах левого дочернего поддерева меньше значения родительского узла
Все значения в узлах правого дочернего поддерева больше значения родительского узла
Каждый дочерний узел тоже является бинарным деревом поиска
Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)
Для решения задач на бинарные деревья существует всего два варианта:
Обход дерева в глубину (depth-first search, DFS)
Обход дерева в ширину (breadth-first search, BFS)
В этой части статьи рассмотрю обход дерева в глубину. Существует три вида обхода в глубину:
Прямой обход (NLR)
Центрированный обход (LNR)
Обратный обход (LRN)
L - левый узел (left), R - правый узел (right), N - родительский узел (node)
Обход дерева в глубину осуществляется двумя способами:
Рекурсивный способ
Итеративный способ
Преимущества |
Недостатки |
|
Рекурсивный подход |
1. Простота и читаемость кода: 2. Соответствие математическим описаниям: |
1. Переполнение стека: 2. Накладные расходы на вызовы функций: 3. Ограниченная масштабируемость: |
Итеративный подход |
1. Контроль над стеком: 2. Более высокая производительность: Итеративные алгоритмы могут быть быстрее, так как отсутствуют накладные расходы на вызов функций и создание новых записей в стеке вызовов. 3. Большая гибкость: Итеративные алгоритмы могут быть более гибкими и позволять более сложные манипуляции с состоянием, что сложно реализовать в рекурсии. |
1. Более сложный код и менее наглядный код: |
Сейчас рассмотрим рекурсивный обход дерева в коде на java. Сделаю сразу с отсылкой к задаче на leetcode: https://leetcode.com/problems/binary-tree-preorder-traversal/
Требуется обойти дерево в глубину прямым обходом (NLR) и вернуть последовательность узлов в виде списка.
Алгоритм решения следующий:
Проверяем, не является ли текущий узел пустым (null)
Добавляем в итоговый список текущий узел
Рекурсивно обходим левое поддерево
Рекурсивно обходим правое поддерево
На Java код выглядел бы так:
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList();
helper(root, result);
return result;
}
private void helper(TreeNode root, List<Integer> result) {
if (root != null) {
result.add(root.val);
helper(root.left, result);
helper(root.right, result);
}
}Вот тут еще задачки для центрированного и обратного обходов:
https://leetcode.com/problems/binary-tree-inorder-traversal/description/
https://leetcode.com/problems/binary-tree-postorder-traversal/description/
Чтобы их решить, нужно просто поменять местами пару строк в алгоритме.
Если дерево слишком глубокое (для современных машинок более 1000 узлов будет тяжеловато), то лучше использовать итеративный подход. Для итерации обычно используется собственный стек вызовов.
Но давайте перед кодом посмотрим на структуры данных, которые в целом можно использовать для итеративного обхода. Если открыть википедию, там будет рекомендация использовать стэк. Stack в Java является устаревшей структурой данных, вместо него рекомендуют использовать Deque. Преимущества Deque расписаны хорошо в этой статье - https://www.baeldung.com/java-deque-vs-stack
Для решения алгоритмических задач, по факту, никакие преимущества Deque нам не даст. Поэтому если хотите использовать по-старинке Stack - пожалуйста.
Но тут внимание вопрос: почему нельзя использовать обычный ArrayList для хранения?
На практике списки используются значительно чаще, чем очереди. Давайте подумаем, даст ли нам какое-то преимущество использование Deque конкретно в этой задаче, но сначала код (с ArrayList):
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
List<TreeNode> stack = new ArrayList<>();
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.remove(stack.size() - 1);
result.add(node.val);
// Добавляем правого ребенка в стек первым, чтобы левый обрабатывался первым
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
return result;
}Вставка элементов в конец списка - скорость O(1), вставка элементов в конец очереди - O(1)
Удаление элементов из конца списка - O(1), удаление элементов из конца очереди - O(1)
В обоих случаях операции, используемые в задаче, выполняются за константное время. Поэтому использование Deque не дает каких-либо преимуществ.
Чтобы не быть голословной, поделюсь результатами замеров (код можно сокращать и рефакторить, да-да, но оставила в таком виде для большей наглядности).
Тут код (раскрой, если интересно)
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
compare(25);
System.out.println("_______________");
}
}
private static void compare(int treSize) {
TreeNode root = generateLargeTree(treSize);
long start, end;
// Тест с ArrayDeque
start = System.currentTimeMillis();
preorderTraversalWithArrayDeque(root);
end = System.currentTimeMillis();
System.out.println("ArrayDeque Time: " + (end - start) + " ms");
// Тест с ArrayList
start = System.currentTimeMillis();
preorderTraversalWithArrayList(root);
end = System.currentTimeMillis();
System.out.println("ArrayList Time: " + (end - start) + " ms");
// Тест с Stack
start = System.currentTimeMillis();
preorderTraversalWithStack(root);
end = System.currentTimeMillis();
System.out.println("Stack Time: " + (end - start) + " ms");
}
private static List<Integer> preorderTraversalWithArrayList(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
List<TreeNode> stack = new ArrayList<>();
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.remove(stack.size() - 1);
result.add(node.getVal());
if (node.getRight() != null) {
stack.add(node.getRight());
}
if (node.getLeft() != null) {
stack.add(node.getLeft());
}
}
return result;
}
private static List<Integer> preorderTraversalWithArrayDeque(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.getVal());
if (node.getRight() != null) {
stack.push(node.getRight());
}
if (node.getLeft() != null) {
stack.push(node.getLeft());
}
}
return result;
}
private static List<Integer> preorderTraversalWithStack(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.getVal());
if (node.getRight() != null) {
stack.push(node.getRight());
}
if (node.getLeft() != null) {
stack.push(node.getLeft());
}
}
return result;
}
private static TreeNode generateLargeTree(int depth) {
if (depth == 0) {
return null;
}
TreeNode root = new TreeNode(depth);
root.setLeft(generateLargeTree(depth - 1));
root.setRight(generateLargeTree(depth - 1));
return root;
}Прогнала тест с использованием разных структур данных (ArrayList, ArrayDeque, Stack) 10 раз с деревом глубиной 25.
Лучшую скорость показали:
ArrayDeque - 2 раза
ArrayList - 6 раз
Stack - 2 раза
Результаты замеров тут
ArrayDeque Time: 2845 ms
ArrayList Time: 2231 ms
Stack Time: 4579 ms
_______________
ArrayDeque Time: 4478 ms
ArrayList Time: 1302 ms
Stack Time: 4541 ms
_______________
ArrayDeque Time: 7852 ms
ArrayList Time: 1305 ms
Stack Time: 4655 ms
_______________
ArrayDeque Time: 1537 ms
ArrayList Time: 4346 ms
Stack Time: 3870 ms
_______________
ArrayDeque Time: 4199 ms
ArrayList Time: 3966 ms
Stack Time: 1166 ms
_______________
ArrayDeque Time: 1048 ms
ArrayList Time: 1311 ms
Stack Time: 5988 ms
_______________
ArrayDeque Time: 4349 ms
ArrayList Time: 3924 ms
Stack Time: 1082 ms
_______________
ArrayDeque Time: 1135 ms
ArrayList Time: 1577 ms
Stack Time: 3744 ms
_______________
ArrayDeque Time: 7193 ms
ArrayList Time: 1207 ms
Stack Time: 4070 ms
_______________
ArrayDeque Time: 1188 ms
ArrayList Time: 1124 ms
Stack Time: 4230 ms
_______________
То есть какой-то явной динамики нет, а поэтому можно сделать вывод, что использование любой из структур данный уместно для решения этой алгоритмической задачи.
Во второй части статьи я рассмотрю второй способ обхода деревьев - BFS (в ширину).
Комментарии (26)
Andrey_Solomatin
13.08.2024 11:35Для решения алгоритмических задач, по факту, никакие преимущества Deque нам не даст.
Я за строгость формулировок в технических статьях. Мне кажется вы имели в виду не то, что написали.
domix32
13.08.2024 11:35Вставка элементов в конец списка - скорость O(1),
Не путайте списки и массивы. Списки (обычно односвязные) вставляют новый элемент за O(n) и удаление последнего элемента также, ибо везде требуется проход от головы, если иных оптимизаций не делалось.
Andrey_Solomatin
13.08.2024 11:35Изначально фраза немного не чёткая, но она относится к коду в котором используется ArrayList. Похоже что именно этот список имеется в виду.
akozyrenko Автор
13.08.2024 11:35Речь идет об ArrayList, в основе которого и лежит массив.
Вставка элементов осуществляет за O(1) -(см. https://www.baeldung.com/java-collections-complexity - пруф не из спеки, но да простите меня:)). В худшем сценарии, да, вы правы вставка будет за O(n) - когда мы превысим capacity и нужно будет создавать новый массив и копировать все элементы. Для очень глубоких деревьев пару перестроек, все-таки случится, спорить не буду.
Удаление элементов из ArrayList, действительно, осуществляется за О(n). Но когда речь идет об удалении последнего элемента, то это займет O(1). Для удаления элемента используется метод fastRemove. Смотрим реализацию:
private void fastRemove(Object[] es, int i) { modCount++; final int newSize; if ((newSize = size - 1) > i) System.arraycopy(es, i + 1, es, i, newSize - i); es[size = newSize] = null;}При удалении последнего элемента нам не приходится создавать копию массива и сдвигать все элементы слева от него (потому что их нет), т.е. мы не попадаем в условие:
if ((newSize = size - 1) > i) { System.arraycopy(es, i + 1, es, i, newSize - i); }Все что происходит - обнуление последнего элемента и изменение размера массива.
wataru
13.08.2024 11:35В худшем сценарии, да, вы правы вставка будет за O(n) - когда мы превысим capacity и нужно будет создавать новый массив и копировать все элементы.
Вставка в конец - амартизированно O(1) все также (ибо capacity каждый раз примерно 2 раза растет).
Andrey_Solomatin
А алгоритм Дейкстры для поиска кратчайшего пути, какой из двух вариантов использует?
nronnie
Алгоритм Дейкстры он ведь не про деревья, а про графы вообще.
P40b0s
Связанный ациклический граф вообще то и есть дерево.
nronnie
Да, я этого не знал :))) Я имел в виду, что не очень понял про алгоритм Дейкстры в контексте деревьев, про которые статья. Он ведь про поиск самого "дешевого" пути среди возможных. А в дереве все равно дорога между любыми вершинами только одна (ну если не ходить туда-сюда по одним и тем же ребрам).
Andrey_Solomatin
Например найти ближайший лист от вершины.
nronnie
По сути, так называемый "обход в обратном порядке". Т.е. решаем задачу для левого поддерева, решаем задачу для правого поддерева, потом сравниваем с учетом (т.е. добавляя) ребер соединяющих левое и правое поддеревья с "центральной" вершиной.
Andrey_Solomatin
Извините, не уточнил, в контексте Дейкстеры ближайщий - это с минимальной сумой ребер. В пример это x.
wataru
Дейскстру к деревьям не применяют, потому что там существует ровно один путь между двумя любыми вершинами. Любой обход (bfs или dfs) тут работает быстрее, пишется проще, и отлично решает любую задачу, к которой можно было бы прикрутить дейскстру.
Andrey_Solomatin
Про работает быстрее соглащусь.
По имплементации одна фигня. При работе с итерацией просто коллекцию нужную выбираете. Стек обход в глубину, очередь обход в ширину, очередь с приоритетами это Дейкстера. Разница в несколько символов.
Можно ли найти самый близкий лист, не посещая все вершины?
(близкий -> c минимальным сумарным весом рёбер, в дереве без отрицательных весов)
Спойлер, да:
Вы начинаете обходить граф по алгоримту Дейкстеры и останваливаетесь на первом листе. a - b - e - c - d - x
wataru
Если стек использовать из рекурсии, то код часто сильно короче получается.
А BFS все равно получается проще, ибо в Дейкстре надо ребра релаксировать и пересчитывать приоритеты. В BFS же тупо один раз кладем в очередь, если вершина еще не помечена.
А главное, что оно исльно проще концептуально, а не длиной кода в символах. Если у вас никаких перекрестных/возвратных ребер в графе нет, то не надо обрабатывать случай их существования.
Andrey_Solomatin
Давайте вернемся к задаче которую я писал https://habr.com/ru/articles/835706/comments/#comment_27163316.
Полный обход дерева решает задачу нахождения самого короткого пути, но это будет не оптимальным решением. При всей простоте и скорости BFS, DFS не подходят для оптимального решения именно этой задачи.
Взаять алгоритм Дейкстеры и остановиться на первом листе который мы встретили в графе, на мой взгляд близко к оптимальному. Какое решение предложили бы вы?
wataru
Тут не все так однозначно. С одной стороны в Дейкстре вы можете выйти из цикла заранее, как только нашли ближайшую вершину, да. Это логичная оптимизация. С другой стороны, вы на обработку каждой вершины тратите больше времени из-за поиска в приоритетной очереди. На тесте, где ближайшая вершина окажется близко, дейкстра будет бытсрее. На тесте, где вы запустились из центра дерева - нет. В худшем случае Дейкстра будет медленнее.
Andrey_Solomatin
Тут хорошую идею оптимизации BFS закинули, https://habr.com/ru/articles/835706/comments/#comment_27164814
Тогда bfs будет в среднем случае действительно лучше. А в лучшем примерно такой-же.
nronnie
Да, я поэтому выше и написал "самый дешевый" а не "самый короткий".
domix32
В этом случае обход в глубину будет чутка эффективнее, т.к. вам все равно почти все ноды трогать. А в среднем - зависит от задачи. В среднем, из собственного опыта, задачки на lc чаще требует dfs нежели bfs.
Andrey_Solomatin
Все ноды и почти все ноды - это большая разница. Это ленивые (то что нужно) и жадные (всё) вычисления.
Для собеседования и для развития надо смотреть на оптимальные алгоритмы.
Когда в руке молоток (Python), каждая задача кажется гвоздём (DFS). Для стека я использую встренный list, а для BFS нужно импортировать collections.deque.
domix32
В случае поиска минимального листа вы просто перестаёте искать если спустились глубже текущего минимума. Если не оптимизировать или словить плохое дерево (когда минимальная нода будет самой правой), то обход сводится к полному обходу в обоих случаях.
DFS из-за стека будет оптимальнее по памяти т.к. очередь обработки в таком случае будет не больше высоты дерева. В случае с BFS размер очереди будет равняться ширине уровня и у бинарного дерева она соотвественно удваивается с каждым уровнем. Если есть какие-то инсайты касательно структуры дерева (сбалансированность, ограничения на ширину/высоту), то можно прикинуть самостоятельно какой из двух окажется оптимальнее. Алгоритмически, исходя из худшего исхода (то бишь в терминах большого О) - плотное дерево, где каждая нода кроме крайнего правого имеет по два потомка - DFS получается несколько оптимальнее под такую задачу из-за ограничений на память.
как будто-то что-то плохое. многие задачи требуют кучу и что ж теперь ручками поверх списков его реализовывать?
Andrey_Solomatin
Об этом я не подумал. Хорошая оптимизация.
Это да. Но на литкоде обычно все супер абстрактно. Можно конечно поподгонять свой код под тесты, но смысла особо нет.
Над промотать вверх кода, что-то напечатать промотать обратно. На собесе это потеря времени. А если нет разницы между BFS и DFS для задачи, то зачем платить больше.
deque двухсвязанный список. Куча это Heap. В питоне кучу руками не надо, но вот поверх списков приходится. Не самое удобное API https://docs.python.org/3/library/heapq.html#basic-examples
domix32
deque = double ended queue, то бишь двусторонняя очередь, а не двусвязный список, который double-linked list. В мире питона deque эта самая обычная очередь. Куча (aka Min/Max Heap aka Priority Queue) была в качестве примера который вроде как тоже надо импортировать ибо она не в дефолтной области видимости.
vicumg
не каждый граф - дерево, но каждое дерево - граф