Рубрики

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

Числа 1, 2,…. n вставляются в двоичное дерево поиска в некотором порядке. В результирующем дереве правое поддерево корня содержит p узлов. Первый номер, который нужно вставить в дерево, должен быть
(А) р
(Б) р + 1
(С) n — p
(D) n — p + 1

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

Двоичное дерево поиска — это структура данных двоичного дерева на основе узлов, которая имеет следующие свойства:

  • Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.
  • Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла.
  • Левое и правое поддерево каждого также должно быть двоичным деревом поиска.
    Не должно быть повторяющихся узлов.

Итак, скажем, n = 10, p = 4. В соответствии со свойством BST корень должен быть 10-4 = 6 (учитывая все уникальные элементы в BST). А согласно вставке BST , root является первым элементом, который должен быть вставлен в BST. Следовательно, ответ (np).

Тест на этот вопрос
Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте

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

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

0.00 (0%) 0 votes