Каково время сложности для расчета высоты дерева avl? - PullRequest
Новая
       8

Каково время сложности для расчета высоты дерева avl?

0 голосов
/ 02 июня 2018

для данного дерева avl, какова временная сложность «лучшего» алгоритма для вычисления высоты дерева?

Я знаю, что высота дерева равна log (n), учитывая, что существует n элементовв дереве.Но как я могу рассчитать высоту?

1 Ответ

0 голосов
/ 02 июня 2018

Допустим, число узлов, составляющих дерево высотой h, равно N_h.Таким образом, высота дерева, у которого в качестве корня остался дочерний элемент, равна h-1 с N_(h-1) узлами, а правое поддерево может иметь минимальную высоту h - 2 с N_(h-2) узлами, поскольку дерево AVL сбалансировано (разница высот левого иправое поддерево не может быть больше 1).Мы можем написать формулу следующим образом: 

N_h = N_(h -1) + N_(h -2) + 1           (i)

Базовые случаи: N_1 = 1 и N_2 = 2 И 

N_(h−1) = N_(h−2) + N_(h−3) + 1           (ii)

Помещение (ii) в уравнение (i) мы получаем 

N_h = N_(h−2) + N_(h−3) + 1  + N_(h -2) + 1 
=> N_h = 2*N_(h−2) + N_(h−3) + 2 
=> N_h > 2*N_(h-2)
=> N_h > 2^(h/2)
=> log(N_h) > log(2^(h/2))
=> 2log(N_h) > h
=> h = O(log(N_h)

Заменив N_h на n мы можем написать 

h = O(lgn)
...