Как рассчитать высоту красного черного дерева?

Question

Я почти закончил реализацию красного черного дерева, но я застрял с , как рассчитать высоту (не черный высота). Может ли кто-нибудь дать мне подсказку или концепцию о том, как реализовать высоту? Я знаю формулу, но это не очень помогает.

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

В основном, как я узнаю, когда он прошел до самого длинного пути?

Я не очень беспокоюсь о временной сложности решения, но я бы хотел избежать n .

Answer 1

Существует простой рекурсивный подход для вычисления высоты дерева, который работает во времени O (n), где n - количество узлов. Идея состоит в том, чтобы вычислить высоту каждого дочернего узла, а затем взять максимум этих значений, плюс один. Вот некоторые псевдокод:

function treeHeight(node n) { 
    if (n is null) return -1; 
    return max(treeHeight(n.left), treeHeight(n.right)) + 1; 
} 

Это посещает каждый узел только один раз и делает O (1) работу на узел, таким образом, общая сложность времени O (п).

Надеюсь, это поможет!