Рубрики

ВОРОТА | Gate IT 2005 | Вопрос 50

В двоичном дереве для каждого узла разница между числом узлов в левом и правом поддеревьях составляет не более 2. Если высота дерева h> 0, то минимальное количество узлов в дереве:
(А) 2 ч — 1
(Б) 2 ч — 1 + 1
(С) 2 ч — 1
(D) 2 ч

Ответ: (Б)
Объяснение:

Let there be n(h) nodes at height h.

In a perfect tree where every node has exactly 
two children, except leaves, following recurrence holds.

n(h) = 2*n(h-1) + 1

In given case, the numbers of nodes are two less, therefore
n(h) = 2*n(h-1) + 1 - 2
     = 2*n(h-1) - 1

Now if try all options, only option (b) satisfies above recurrence.

Let us see option (B)
n(h) = 2h - 1 + 1

So if we substitute 
n(h-1) = 2h-2 + 1, we should get n(h) = 2h-1 + 1

n(h) =  2*n(h-1) - 1
     =  2*(2h-2 + 1) -1
     =  2h-1 + 1.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2005 | Вопрос 50

0.00 (0%) 0 votes