Сложность для функции MaxHeight в бинарном дереве

Question

Функция:

MAX-HEIGHT(node) 
    if(node == NIL) 
     return -1; 
    else 
    return max(MAX-HEIGHT(node.leftChild), MAX-HEIGHT(node.rightChild)) + 1; 

Предположим, что мы имеем N узлов, и мы называем функцию с MAX-HEIGHT(root).

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

Итак, какая сложность?

спасибо.

Answer 1

В среднем случае для сбалансированного бинарного дерева

T(n) = 2T(n/2) + Θ(1); 

Каждый рекурсивный вызов дает вам две проблемы половины размера. По мастер-теореме это оценило бы T (n) = Θ (n)

В худшем случае, когда каждый узел имеет только одно дочернее устройство.

T(n) = T(n-1) + Θ(1) 

который оценивает Т (п) = Θ (п)

Answer 2

вопросы вы должны задать следующие:

• Что N представляют в моей структуре данных (бинарное дерево)
• Сколько я должен пройти, прежде чем я смогу определить высоту моей структуры.

Здесь N представляет количество узлов в вашем дереве, и вам нужно пройти все их перед возвратом высоты.

По этой причине ваш алгоритм в O (N)