Как вы можете рассчитать глубину двоичного дерева с меньшей сложностью?

Question

Учитывая бинарное дерево поиска т, довольно легко получить его глубину с помощью рекурсии, как следующее:

def node_height(t):  
    if t.left.value == None and t.right.value == None: 
     return 1 
    else: 
     height_left = t.left.node_height() 
     height_right = t.right.node_height() 
     return (1 + max(height_left,height_right)) 

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

Answer 1

Если вы сохраняете высоту как поле в объекте Node, вы можете добавить 1, когда вы добавляете узлы в дерево (и вычитаете во время удаления).

Это сделает операцию постоянной для получения высоты любого узла, но добавляет дополнительную сложность в операции добавления/удаления.

Answer 2

Этот вид простирается от @cricket_007, упомянутого в его ответе.

Итак, если вы делаете (1 + max(height_left,height_right)), вам придется посетить каждый узел, который по существу является операцией O (N). Для среднего случая со сбалансированным деревом вы будете смотреть на что-то вроде T(n) = 2T(n/2) + Θ(1).

Теперь это можно улучшить до времени O (1), если вы можете сохранить высоту определенного узла. В этом случае высота дерева будет равна высоте корня. Таким образом, модификация, которую вам нужно будет сделать, будет связана с вашим методом insert(value). В начале корню задана высота по умолчанию 0. Узел, который нужно добавить, присваивается высоте 0. Для каждого узла, с которым вы сталкиваетесь при попытке добавить этот новый узел, увеличьте node.height на 1, если необходимо, и убедитесь, что он установлен в 1 + max (высота левого ребенка, высота правого ребенка). Таким образом, функция высоты просто вернет node.height, следовательно, позволит постоянное время. Сложность времени для вставки также не изменится; нам просто нужно дополнительное пространство для хранения целочисленных значений n, где n - это количество узлов.

Показано, что показано, что я пытаюсь сказать.

  5 [0] 

- insert 2 [increase height of root by 1] 

      5 [1] 
     /
     / 
    [0] 2 

- insert 1 [increase height of node 2 by 1, increase height of node 5 by 1] 

      5 [2] 
     /
     / 
    [1] 2  
    /
    / 
[0] 1 

- insert 3 [new height of node 2 = 1 + max(height of node 1, height of node 3) 
           = 1 + 0 = 1; height of node 5 also does not change] 

      5 [2] 
     /
     / 
    [1] 2  
    /\ 
    / \ 
[0] 1  3 [0] 

- insert 6 [new height of node 5 = 1 + max(height of node 2, height of node 6) 
           = 1 + 1 = 2] 

      5 [2] 
     /\ 
     / \ 
    [1] 2  6 [0] 
    /\ 
    / \ 
[0] 1  3 [0]