Временная сложность проверки сбалансированности бинарного дерева

Я практикую некоторые вопросы интервью и пытаюсь выяснить временную сложность моего решения, чтобы определить, сбалансировано ли данное бинарное дерево.

Я считаю, что решение 2 имеет временную сложность O(n), а решение 1 имеет временную сложность O(n^2). Это связано с тем, что в решении 1 вы возвращаетесь к нижней части дерева, чтобы проверить, сбалансировано ли дерево, а также проверить наличие различий в высоте поддерева. Дополнительная сложность возникает по мере того, как мы поднимаемся вверх по дереву к корню, а get_height все еще рекурсивно спускается вниз по дереву для вычисления высоты. Поэтому, путешествуя по дереву еще раз --> O(n^2).

Тот факт, что решение 2 сначала сравнивает высоту, означает, что при движении вверх по дереву нам не нужно возвращаться вниз, чтобы проверить высоту поддерева.

помощник:

def get_height(root):
    if root is None:
        return 0
    else:
        return max(get_height(root.left), get_height(root.right)) + 1

Решение 1:

def is_balanced(root):
    if root is None:
        return True
    else:
        return is_balanced(root.right) and is_balanced(root.left) and (abs(get_height(root.left) - get_height(root.right)) < 2)

Решение 2:

def is_balanced2(root):
    if root is None:
        return True
    else:
        return (abs(get_height(root.left) - get_height(root.right)) < 2) and is_balanced(root.right) and is_balanced(root.left)

код для проверки разницы во времени:

s = time.time()
print("result: {}".format(is_balanced(a)))
print("time: {}".format(time.time() - s))

s = time.time()
print("result: {}".format(is_balanced2(a)))
print("time: {}".format(time.time() - s))

результаты для несбалансированного дерева:

result: False
time: 2.90870666504e-05    # solution 1
result: False
time: 1.50203704834e-05    # solution 2

python algorithm tree
person Liondancer    schedule 14.12.2015    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Я считаю, что решение 2 имеет временную сложность O (n), а решение 1 имеет временную сложность O (n ^ 2).

Я считаю иначе, как объяснено ниже.

... в решении 1 вы возвращаетесь к нижней части дерева, чтобы проверить, сбалансировано ли дерево, а также проверить наличие различий в высоте поддерева. Дополнительная сложность возникает по мере того, как мы поднимаемся вверх по дереву к корню, а get_height все еще рекурсивно спускается вниз по дереву для вычисления высоты. Следовательно, еще раз спускаемся по дереву --> O(n^2).

Это не так просто. Скажем, вы вызываете is_balanced() в корне: поскольку он рекурсивно посещает каждый узел в дереве, он вызывает get_height, который рекурсивно посещает поддерево под ним. Для корня get_height посещает почти все дерево: N-1 операций, поэтому O(N). Для каждого из двух потомков корня get_height посещает их (примерно) половину дерева: снова O(N). Это продолжается до тех пор, пока get_height не будет работать на ~N None узлах под N/2 листовыми узлами: по-прежнему O(N). Всего в дереве ~ log2N уровней, вы выполняете O (N) обработку на каждом, поэтому общая сложность составляет O (N log N).

Тот факт, что решение 2 сначала сравнивает высоту, означает, что при движении вверх по дереву нам не нужно возвращаться вниз, чтобы проверить высоту поддерева.

Неа. Во втором решении вы изменили порядок выполнения проверок is_balanced и get_height. Для любого дерева, для которого оба теста в конечном итоге проходят успешно, общий объем обработки — и, следовательно, эффективность big-O — остается неизменной.

Отдельно ваша логика не проверяет сбалансированное двоичное дерево: вы можете перечитать определение.

person Tony Delroy    schedule 14.12.2015
comment
Я не уверен, как мои решения не проверяют, сбалансировано ли двоичное дерево. Не могли бы вы привести несколько примеров? Спасибо - person Liondancer; 16.12.2015
comment
@Liondancer: рассмотрим пример дерева в Википедии здесь, представленный с сбалансированным двоичным деревом минимально возможная максимальная высота (также известная как глубина) для листовых узлов: для сбалансированного дерева слева левая ветвь ABCD имеет высоту 3 (используя их корень = 0), а правая ветвь E имеет высоту 1.. .. это не соответствует вашему abs(get_height(root.left) - get_height(root.right)) < 2) условию. Как говорит Википедия, разница в высоте ‹2 распространена в сбалансированных бинарных деревьях — даже гарантируется некоторыми алгоритмами вставки — но не является частью определения. - person Tony Delroy; 16.12.2015