Обход Binary-Tree, как сделать быстрее?

Question

[Максим Булатов]

На собеседовании попалась задача о сравнении двух последовательности чисел, хранящихся в двух бинарных деревьях. Я затупил, пытаясь сходу изобрести обход с очередью, уже после почесал в голове и смастерил это, но интервьюер говорит, что можно сделать за O(n) на несбалансированных деревьях и нет повода ему не верить.

Сначала у меня рекурсия уходила и в пустые элементы тоже, теперь есть условие, но я не уверен, что это все еще оптимальный вариант. Прочитал главу от Кнута про деревья (Глава 2.3.1), вроде все понятно, но после разгромного интервью я теперь в каждой строке сомневаюсь. Речь именно про минималистичный обход, так то и itertools можно убрать из-за перекопирования элементов, и перехватывать исключения самостоятельно.

import itertools

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def tree_walk(node):
    if node.left:
        yield from tree_walk(node.left)
    yield node.value
    if node.right:
        yield from tree_walk(node.right)

def cmp_tree(node1, node2):
    for v1,v2 in itertools.zip_longest(tree_walk(node1), tree_walk(node2)):
        print(v1, v2)
        if v1 != v2:
            return False

    return True

"""
root1:
1
  2
    3

root2:
    3
  2
1

root3:
  2
1   3
      4
"""

root1 = Node(1)
root1.right = Node(2)
root1.right.right = Node(3)

root2 = Node(3)
root2.left = Node(2)
root2.left.left = Node(1)

root3 = Node(2)
root3.left = Node(1)
root3.right = Node(3)
root3.right.right = Node(4)

print(cmp_tree(root1, root2))
print()
print(cmp_tree(root2, root3))

UPD:
Как выяснилось, код уже с линейной сложностью. Отмечен ответ про сравнение деревьев, см. комментарии глубже.

Comments

[ayazer]

так все-же b-tree или binary-tree?

[Максим Булатов]

ayazer, Ой. ;). Сильно несбалансированное бинарное дерево это.

Answer 1

[Wataru]

У вас проблема в решении в том, что вы сравниваете 2 обхода. Это неверно для, как вам уже приводили в пример, этих двух деревьев:

1
 \
  2
   \
    3

    3
   /
  2
 /
1

Тут оба обхода вернут 1,2,3.

Можно в вашем решении добавлять всякие разделители при переходе влево-вправо-вверх. Вставить всякие yeild -1 и другие значения перед походом влево, выводом собственно элемента и походом вправо.

Но есть лучшее решение, через DFS или BFS: вы делайте обход одновременно на двух деревьях. Т.е. у вас параметр функции dfs или в очереди в bfs лежат сразу 2 вершины - по одной из каждого дерева. Вы проверяете, что у них значения одинаковые и что у них у обеих одновременно есть или нет левого и правого ребенка. Потом вызываетесь/кладете в очередь одновременно левых детей и одновременно правых детей. Если в процессе обхода вершины оказались разными, или где-то есть ребенок, а где-то нет - то деревья не равны.

Очень логично реализовывается в виде DFS (ниже псевдокод):

Equals(t1, t2):
   // обработать случай null одного или обоих деревьев.
   return t1.v == t2.v && Equals(t1.left, t2.left) && Equals(t1.right, t2.right)

Все предельно логично - 2 дерева равны, если у них равны корни, левые поддеревья и правые поддеревья.

Кстати, ваше решение, если его исправить, тоже будет за O(n).

Comments

[Максим Булатов]

Спасибо. Обойти два дерева в одном цикле было бы слишком просто. Сравнивать нужно именно упорядоченную последовательность, которая в дереве хранится, но вопрос не об этом.

Вопрос такой: DFS он ведь за O(n), а если два раза вызвать, то ведь все равно O(n), правильно?

Сначала я написал в лоб вот так, без if с лишними вызовами:

def tree_walk(node):
    yield from tree_walk(node.left)
    yield node.value
    yield from tree_walk(node.right)

Получил feedback:
"Такое решение будет работать за O(n log n) на сбалансированных деревьях и за O(n^2) на несбалансированных. Следующим шагом я бы попросил его еще немного улучшить до O(n)."

Потом исправил, ответа не получил и теперь не знаю, есть ли что-то еще. Правильно ведь, что рекурсия и цикл дают одинаковую сложность обхода, разве что цикл эффективнее?

[Wataru]

Максим Булатов,

Интервьювер - дурак был. Рекомендую отправить рекрутеру жалобу. Просто, что бы ему стадно было. Тут никаким боком ни N log N, ни N^2 вылезти не могут. У вас самый обычный DFS написан - работает за O(n).
Тут другая проблема: если node.left нет, то вы вызываетесь от Null (или None, или что там в питоне) и при попытке уже от этого взять node.left программа упадет с ошибкой.

Но если это исправить (добавив if node: в начало функции, например, или как вы с проверкой node.left перед вызовом, что почти то же самое, лишь чуть чуть сэкономит на вызовах функции), то работать будет так же - за O(n).

> Вопрос такой: DFS он ведь за O(n), а если два раза вызвать, то ведь все равно O(n), правильно?

Будет O(2n) = O(n). Но вам не надо 2 раза вызывать BFS! Вы один раз вызываете, но одновременно по двум деревьям, с двумя параметрами! и двигаете одновременно оба параметра или влево или вправо.

Т.е. вместо того что бы обойти первое дерево, запомнить обход, обойти второе дерево, запомнить обход, сравнить 2 обхода - вы должны параллельно обходить оба дерева. Как код, что я привел в конце.

[Максим Булатов]

wataru, сравниваем именно упорядоченный результат обхода. В одном цикле можно, с двумя очередями, но это другая реализация того же самого алгоритма: получаем последовательность. Точно ведь линейно?

Есть основания полагать, что интервьюер таки умный и это я чего-то не понял. Что меняется, если деревья несбалансированные? Получаются лишние тупики, но их максимальное количество n+1. Может, еще что-нибудь?

[Wataru]

> сравниваем именно упорядоченный результат обхода. В одном цикле можно, с двумя очередями, но это другая реализация того же самого алгоритма: получаем последовательность. Точно ведь линейно?

Упорядоченный результат обхода для разных деревьев может быть одинаковым (пример я вам привел в ответе). В одном цикле с двумя очередьми это будет уже другая реализация. Вы не просто должны взять 2 обхода и делать их параллельно, вы должны смотреть, чтобы у двух деревьев одновременно были левые или правые дети. Иначе - сразу же возвращаете false.

Точно линейно! Каждую вершину обойдете не более одного раза, вершин линейно.

> Есть основания полагать, что интервьюер таки умный и это я чего-то не понял.

Если интервьювер действительно ругался на вот этот ваш код, считая что он нелинеен, то он "чего-то не понял":

def tree_walk(node):
    yield from tree_walk(node.left)
    yield node.value
    yield from tree_walk(node.right)

От сбалансированности меняется глубина дерева. У сбалансированного она - O(log N). У не сбалансированного она - O(N). Это имеет значение тольуо если вы не обходите ВСЕ дерево, а спускаетесь один раз, например, ища заданный элемент в дереве поиска. В задаче сравнения двух деревьев вы будете делать ПОЛНЫЙ обход дерева: вы же их целиком сравниваете, да?

Лишние тупики - НЕТ! Что в несбалансированном дереве из N вершин будет N+1 "тупиков", что и в сбалансированном их будет столко же. Это просто доказать. Сколько всего left и right у всех N вершин? 2N. Сколько из них ведут не в тупики? Ровно N-1 - каждая из вершин, кроме корня, занимает чей-то left или right. Вот и получается, что тупиков будет ровно 2N-N+1 = N+1. Еще раз, неважно, как ваше дерево устроено: палка ли, сбалансированное ли - тупиков всегда одинаково. И обход будет занимать ровно то же самое время - O(N) (если смотреть на худший случай. Так-то, при правельной реализации вы можете прекратить обход заранее, например, если корни не совпали).

Есть вариант, что вы вообще не поняли условие задачи, но если задача действительно была - сравнить 2 бинарных дерева на полное совпадение, то интервьювер - дурак был. Ваше решение с ошибкой, да, но не по времени, а логической.

[Максим Булатов]

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

Answer 2

[ayazer]

1) питон не умеет отбрасывать хвост. Использовать рекурсию я ЯП которые не умееют в хвостовую оптимизацию - так себе идея. Особенно на абстрактной задаче на обход дерева. Особенно если сразу сказали что дерево "сильно несбалансированное". Потому легким движением ваше решение превращается в тыкву.

root1 = Node(1)
cur_node = root1
for i in range (0, 1000):
    cur_node.left = Node(i)
    cur_node = cur_node.left

2) вот эти два дерева у вас выходят одинаковыми. Как графы - да, они одинаковы т.к. симметричны. Как деревья - нет, они разные.

root1 = Node(1)
root1.right = Node(2)
root1.right.right = Node(3)

root2 = Node(3)
root2.left = Node(2)
root2.left.left = Node(1)

Так что сначала нужно пофиксить, а потом уже думать как сделать быстрее

Comments

[Максим Булатов]

2. Извините, вопрос про обход и я не уточнил, что деревья по заданию считаются одинаковыми, если одинакова упорядоченная последовательность чисел. Форма может быть разной, иначе бы это в одном цикле все проверилось, что не интересно.

В вашем примере оба дерева хранят [1, 2, 3]. Код был оценен как глупый, но рабочий, так что об улучшении можно думать.

1. Tail call это да, было бы круто. На практике, я очень не люблю рекурсию и делаю ее только если данных совсем чуть-чуть и код получается почище, чем с циклом, т.е. очень редко. Я ведь прав, полагая, что указатель в очередь положить это дешевле, чем функцию вызывать?

Но вот абстрактно, когда начинается O(n), когда и почему оно заканчивается?

[ayazer]

Максим Булатов, так это же все меняет.

2. Думаю это стоит уточнить прямо в теле вопроса т.к. просто "сравнить деревья" это в первую очередь про графы. подозреваю что в оригинальной формулировке звучало как-то "есть данные представлены в виде бинарного дерева. Нужно сравнить с другим деревом чтоб понять одинаковые ли в них данные". Тогда да, у вас наверно самое классическое решение для этой задачи. Я хотел написать что все прямо по кнуту, но потом пролистал вверх и увидел что действительно по кнуту. И решение вполне себе O(N).

1. не совсем, проблема с рекурсией не в том что это лишний вызов функции, а в том - что это создание копии всего контекста вызова каждый раз. Т.е. вместо того чтоб выделить 4 байта под счетчик 1 раз и пройтись по всем данным в цикле, вы будете выделять 4 байта на каждый рекурсивный вызов с новым значением счетчика. И все они будут висеть в памяти пока рекурсия не закончится. А теперь представьте что у вас там не 1 инт на 4 байта, а мегабайт данных. А программа работает в 16 потоков и уходит на глубину в несколько тысяч вызовов. Вот и выходит что она улетает в ООМ на рабочей машине, хотя реально переписав алгоритм можно было обойтись всего десятком мегабайт оперативки. Я могу ошибаться в нюансах работы именно питона, но +- эта проблема именно такая во всех языках без хвостовой оптимизации.

О нотация это аппроксимация от абстрактной сложности алгоритма. Она может быть для худшего/лучшего случая, она может быть по кол-ву перестановок/проходов/использованию памяти. Напирмер на примере вашего алгоритма O(N) - поиск по не сбалансированому дереву, O(logN) - поиск по сбалансированому дереву. Это позволяет грубо прикинуть эффективность алгоритма.

[Максим Булатов]

ayazer, Спасибо.