Comments 26
Для решения задач на бинарные деревья существует всего два варианта:
А алгоритм Дейкстры для поиска кратчайшего пути, какой из двух вариантов использует?
Алгоритм Дейкстры он ведь не про деревья, а про графы вообще.
Связанный ациклический граф вообще то и есть дерево.
Да, я этого не знал :))) Я имел в виду, что не очень понял про алгоритм Дейкстры в контексте деревьев, про которые статья. Он ведь про поиск самого "дешевого" пути среди возможных. А в дереве все равно дорога между любыми вершинами только одна (ну если не ходить туда-сюда по одним и тем же ребрам).
Например найти ближайший лист от вершины.
По сути, так называемый "обход в обратном порядке". Т.е. решаем задачу для левого поддерева, решаем задачу для правого поддерева, потом сравниваем с учетом (т.е. добавляя) ребер соединяющих левое и правое поддеревья с "центральной" вершиной.
1 - 2 - 1 - 1 - 1(x)
\
1 - 5 - 1(y)
Извините, не уточнил, в контексте Дейкстеры ближайщий - это с минимальной сумой ребер. В пример это x.
Дейскстру к деревьям не применяют, потому что там существует ровно один путь между двумя любыми вершинами. Любой обход (bfs или dfs) тут работает быстрее, пишется проще, и отлично решает любую задачу, к которой можно было бы прикрутить дейскстру.
тут работает быстрее, пишется проще
Про работает быстрее соглащусь.
По имплементации одна фигня. При работе с итерацией просто коллекцию нужную выбираете. Стек обход в глубину, очередь обход в ширину, очередь с приоритетами это Дейкстера. Разница в несколько символов.
Дейскстру к деревьям не применяют, потому что там существует ровно один путь между двумя любыми вершинами
Можно ли найти самый близкий лист, не посещая все вершины?
(близкий -> c минимальным сумарным весом рёбер, в дереве без отрицательных весов)
Спойлер, да:
Вы начинаете обходить граф по алгоримту Дейкстеры и останваливаетесь на первом листе. a - b - e - c - d - x
1(a) - 2(b) - 2(c) - 1(d) - 1(x)
\
1(e) - 9(f) - 1(y)Стек обход в глубину, очередь обход в ширину, очередь с приоритетами это Дейкстера. Разница в несколько символов.
Если стек использовать из рекурсии, то код часто сильно короче получается.
А BFS все равно получается проще, ибо в Дейкстре надо ребра релаксировать и пересчитывать приоритеты. В BFS же тупо один раз кладем в очередь, если вершина еще не помечена.
А главное, что оно исльно проще концептуально, а не длиной кода в символах. Если у вас никаких перекрестных/возвратных ребер в графе нет, то не надо обрабатывать случай их существования.
А главное, что оно исльно проще концептуально
Давайте вернемся к задаче которую я писал https://habr.com/ru/articles/835706/comments/#comment_27163316.
Полный обход дерева решает задачу нахождения самого короткого пути, но это будет не оптимальным решением. При всей простоте и скорости BFS, DFS не подходят для оптимального решения именно этой задачи.
Взаять алгоритм Дейкстеры и остановиться на первом листе который мы встретили в графе, на мой взгляд близко к оптимальному. Какое решение предложили бы вы?
Полный обход дерева решает задачу нахождения самого короткого пути, но это будет не оптимальным решением. При всей простоте и скорости BFS, DFS не подходят для оптимального решения именно этой задачи.
Тут не все так однозначно. С одной стороны в Дейкстре вы можете выйти из цикла заранее, как только нашли ближайшую вершину, да. Это логичная оптимизация. С другой стороны, вы на обработку каждой вершины тратите больше времени из-за поиска в приоритетной очереди. На тесте, где ближайшая вершина окажется близко, дейкстра будет бытсрее. На тесте, где вы запустились из центра дерева - нет. В худшем случае Дейкстра будет медленнее.
Да, я поэтому выше и написал "самый дешевый" а не "самый короткий".
В этом случае обход в глубину будет чутка эффективнее, т.к. вам все равно почти все ноды трогать. А в среднем - зависит от задачи. В среднем, из собственного опыта, задачки на lc чаще требует dfs нежели bfs.
В этом случае обход в глубину будет чутка эффективнее, т.к. вам все равно почти все ноды трогать.
Все ноды и почти все ноды - это большая разница. Это ленивые (то что нужно) и жадные (всё) вычисления.
Для собеседования и для развития надо смотреть на оптимальные алгоритмы.
В среднем, из собственного опыта, задачки на lc чаще требует dfs нежели bfs.
Когда в руке молоток (Python), каждая задача кажется гвоздём (DFS). Для стека я использую встренный list, а для BFS нужно импортировать collections.deque.
В случае поиска минимального листа вы просто перестаёте искать если спустились глубже текущего минимума. Если не оптимизировать или словить плохое дерево (когда минимальная нода будет самой правой), то обход сводится к полному обходу в обоих случаях.
DFS из-за стека будет оптимальнее по памяти т.к. очередь обработки в таком случае будет не больше высоты дерева. В случае с BFS размер очереди будет равняться ширине уровня и у бинарного дерева она соотвественно удваивается с каждым уровнем. Если есть какие-то инсайты касательно структуры дерева (сбалансированность, ограничения на ширину/высоту), то можно прикинуть самостоятельно какой из двух окажется оптимальнее. Алгоритмически, исходя из худшего исхода (то бишь в терминах большого О) - плотное дерево, где каждая нода кроме крайнего правого имеет по два потомка - DFS получается несколько оптимальнее под такую задачу из-за ограничений на память.
а для BFS нужно импортировать collections.deque.
как будто-то что-то плохое. многие задачи требуют кучу и что ж теперь ручками поверх списков его реализовывать?
В случае поиска минимального листа вы просто перестаёте искать если спустились глубже текущего минимума.
Об этом я не подумал. Хорошая оптимизация.
Если есть какие-то инсайты касательно структуры дерева
(сбалансированность, ограничения на ширину/высоту), то можно прикинуть
самостоятельно какой из двух окажется оптимальнее
Это да. Но на литкоде обычно все супер абстрактно. Можно конечно поподгонять свой код под тесты, но смысла особо нет.
как будто-то что-то плохое.
Над промотать вверх кода, что-то напечатать промотать обратно. На собесе это потеря времени. А если нет разницы между BFS и DFS для задачи, то зачем платить больше.
многие задачи требуют кучу и что ж теперь ручками поверх списков его реализовывать?
deque двухсвязанный список. Куча это Heap. В питоне кучу руками не надо, но вот поверх списков приходится. Не самое удобное API https://docs.python.org/3/library/heapq.html#basic-examples
deque двухсвязанный список.
deque = double ended queue, то бишь двусторонняя очередь, а не двусвязный список, который double-linked list. В мире питона deque эта самая обычная очередь. Куча (aka Min/Max Heap aka Priority Queue) была в качестве примера который вроде как тоже надо импортировать ибо она не в дефолтной области видимости.
не каждый граф - дерево, но каждое дерево - граф
Для решения алгоритмических задач, по факту, никакие преимущества Deque нам не даст.
Я за строгость формулировок в технических статьях. Мне кажется вы имели в виду не то, что написали.
Вставка элементов в конец списка - скорость O(1),
Не путайте списки и массивы. Списки (обычно односвязные) вставляют новый элемент за O(n) и удаление последнего элемента также, ибо везде требуется проход от головы, если иных оптимизаций не делалось.
Обычно списки двусвязные. Там вставка/удаление в конец - O(1).
Изначально фраза немного не чёткая, но она относится к коду в котором используется ArrayList. Похоже что именно этот список имеется в виду.
Речь идет об 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);
}Все что происходит - обнуление последнего элемента и изменение размера массива.
Бинарные деревья — решение алгоритмических задач, часть 1