Высота дерева с использованием глубины

Привет всем. Мне нужно какое-то направление в отношении вычисления временной сложности высоты функции, которая использует глубину функции для получения высоты дерева.

Итак, функция такая:

height(Tree)
height h = 0;
for(each external node of T)
 h = max(height, getdepth(external node));

Наихудшим случаем этого алгоритма будет случай, когда каждый узел находится на одном уровне? В этом случае мы делаем то же самое для всех внешних узлов, поскольку все узлы будут иметь одинаковую высоту — n*(n-some_i) = n^2 ? Но если подумать об этом так - когда дерево несбалансировано либо влево, либо вправо, сложность будет снова что-то 1+2+3+4...+n = n^2 ?

Я немного смущен. Это правильный способ думать об этом?

Спасибо


algorithm tree
person bespectacled    schedule 19.04.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

person Jim Mischel    schedule 19.04.2011