Рубрики

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 65

GATE

Предположим, у нас есть сбалансированное двоичное дерево поиска T, содержащее n чисел. Нам даны два числа L и H, и мы хотим суммировать все числа в T, которые лежат между L и H. Предположим, что в T таких чисел m. Если самая тесная верхняя граница времени для
вычислите сумму O (n a log b n + m c log d n), значение a + 10b + 100c + 1000d равно ____.
(А) 60
(Б) 110
(С) 210
(D) 50

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

int getSum(node *root, int L, int H)
{
   // Base Case
   if (root == NULL)
      return 0;

   if (root->key < L)        
       return getSum(root->right, L, H);

  if (root->key > H)
      return getSum(root->left, L, H)

   if (root->key >= L && root->key <=H)        
      return getSum(root->left, L, H) + root->key +
             getSum(root->right, L, H);
}

Выше всегда занимает O (m + Logn) время. Обратите внимание, что код сначала перемещается по высоте, чтобы найти узел, который находится в диапазоне. Как только такой узел найден, он возвращается для левого и правого потомков. Два рекурсивных вызова выполняются, только если узел находится в зоне действия. Таким образом, для каждого узла, который находится в диапазоне, мы делаем не более одного дополнительного вызова (здесь дополнительный вызов означает вызов узла, который не находится в диапазоне).

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

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

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 65

0.00 (0%) 0 votes