Задания про двоичные деревья

Двоичная куча

Решайте эту задачу, только если вы раньше не программировали кучу. Реализация кучи на основе массива

В первой строке входа дано число N, после него следует N строк с командами для двоичной кучи. Необходимо начать с пустой кучи. Если в строке написано число, нужно добавить его в кучу. Если в строке написано GET, нужно написать в выходной файл текущий максимальный элемент кучи и удалить его из кучи.

Например, для входа

11
10
30
GET
40
20
60
10
GET
GET
0
GET

будет выведено

30
60
40
20

Двоичные деревья поиска

Эту задачу можно решать для разных двоичных деревьев:

  1. Двоичное дерево поиска, наивная реализация без оптимизаций: материалы про наивную реализацию
  2. Декартово дерево: материалы про декартово дерево
  3. Дерево из стандартной библиотеки вашего языка. Найдите у себя в языке такое дерево и воспользуйтесь им для решения задачи.

Реализуйте те деревья, которые сами считаете нужным. Я рекомендую реализовать пункт 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.