Чтобы решить задачу, нам нужно понять, какие ключи от 1 до 99 будут находиться в двоичном дереве поиска (ДП) высоты 4 и при этом потребуют ровно три сравнения для поиска.
Шаг 1: Структура двоичного дерева поиска
Дерево высоты 4 может иметь до 15 узлов (2
4 - 1). В нашем случае у нас есть 15 ключей:
1, 56, 59, 31, 29, 28, 32, 45, 88, 48, 49, 68, 6, 73, 47.
Шаг 2: Построение дерева
Мы можем построить дерево, начиная с корня и добавляя ключи по правилам ДП:
- Если ключ меньше текущего узла, он идет в левое поддерево.
- Если ключ больше, он идет в правое поддерево.
Предположим, что корень дерева — это 56 (среднее значение для упрощения). Дерево будет выглядеть примерно так:
Чтобы найти ключи, для которых потребуется ровно три сравнения, мы должны рассмотреть узлы, находящиеся на третьем уровне дерева (где глубина равна 3). На этом уровне будут узлы, которые можно достичь за три сравнения.
На третьем уровне находятся узлы:
- 29 (левое поддерево от 31)
- 45 (правое поддерево от 31)
- 68 (правое поддерево от 59)
Теперь мы должны определить, какие ключи могут быть помещены между узлами на этом уровне, чтобы они требовали три сравнения.
- Для узла 29: ключи от 1 до 29 (включительно) требуют 3 сравнения.
- Для узла 45: ключи от 31 до 45 (включительно) требуют 3 сравнения.
- Для узла 68: ключи от 59 до 68 (включительно) требуют 3 сравнения.
Теперь перечислим ключи:
- От 1 до 29: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
- От 31 до 45: 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45
- От 59 до 68: 59, 60, 61, 62, 63, 64, 65, 66, 67, 68
Теперь объединим все ключи и отсортируем их:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68.
Теперь мы можем записать ответ в требуемом формате (подряд, без пробелов):
Таким образом, ответ на задачу:
