Реализуйте сбалансированное двоичное дерево поиска.
ВНИМАНИЕ! Пользоваться vector и set из STL СТРОГО ЗАПРЕЩЕНО, однако рекомендуется стрессить ваше решение с ними для поиска багов.
Формат входных данных:
В первой строке дано число n - количество операций с деревом. 1 <= n <= 100000.
Далее дается n строк – операции с деревом. В каждой строке находится одна из следующих операций:
1) insert x – добавить в дерево ключ x. Если ключ x уже в дереве, то ничего делать не нужно.
2) delete x – удалить из дерева ключ x. Если ключа x в дереве нет, то ничего делать не нужно.
3) exists x – если ключ х есть в дереве, то выведите “true”, иначе “false”.
Формат выходных данных:
Выведите последовательно результат выполнения всех операций exists. Каждый ответ нужно выводить в отдельной строке.
Пример:
|
Ввод |
Вывод |
|
6
insert 2
insert 5
insert 3
exists 3
exists 4
delete 5
|
true
false |
(c) Курбатов Е., 2016