Задания про двоичные деревья
В первой строке входа дано число N, после него следует N строк с командами для двоичной кучи. Необходимо начать с пустой кучи. Если в строке написано число, нужно добавить его в кучу. Если в строке написано GET, нужно написать в выходной файл текущий максимальный элемент кучи и удалить его из кучи.
11 10 30 GET 40 20 60 10 GET GET 0 GET Двоичные деревья поиска
Эту задачу можно решать для разных двоичных деревьев:
- Двоичное дерево поиска, наивная реализация без оптимизаций: материалы про наивную реализацию
- Декартово дерево: материалы про декартово дерево
- Дерево из стандартной библиотеки вашего языка. Найдите у себя в языке такое дерево и воспользуйтесь им для решения задачи.
Реализуйте те деревья, которые сами считаете нужным. Я рекомендую реализовать пункт 3 всем, чтобы познакомиться со стандартной библиотекой своего языка. 1 я рекомендую только тем, кто этого не делал. 2 рекомендую всем, у кого осталось на это время после решения других задач.
Только проверка на вхождение элемента
В стандартном входе в первой строке написано число N, оно означет количество чисел, которые будут даны дальше для добавления в двоичное дерево. Заведите пустое двоичное дерево поиска. Дальшее в N строках находится по одному числу. Для каждого числа вы сначала проверяете, было ли это число в дереве, а потом добавляете число в дерево, если его не было. В вывод в отдельную строку нужно написть + или — в зависимости от того, было ли число в дереве. Т.е., встречалось ли оно раньше. Например, для входа 4 10 20 10 30 (в примере всё в одну строку) вы должны вывести — — + — .
Для проврки файлы с тестами заканчиваются на слово contains , например, 1.contains.out .
Поиск следующего элемента
Задача аналогична предыдущей, но кроме знака + или — в строку надо вывести следующее по порядку число за вставленным. Или — , если такого числа нет. Например, для входа 5 20 10 20 40 30 (в примере всё в одну строку) вы должны вывести
- - (потому что 20 еще нет) - 20 (потому что сразу за 10 в дереве идет число 20 по порядку) + - (число 20 есть, но следующего по порядку за ним нет) - - - 40 (числа 30 нет, но по порядку за ним идет 40) Для проверки файлы с тестами заканчиваются на слово min-after , например, 1.min-after.out .
Источник