README.md

Упорядоченное множество на АВЛ-дереве

Если Вы сдали все предыдущие задачи, Вы уже можете написать эффективную реализацию упорядоченного множества на АВЛ-дереве. Сделайте это.

Для проверки того, что множество реализовано именно на АВЛ-дереве, мы просим Вас выводить баланс корня после каждой операции вставки и удаления.

Операции вставки и удаления требуется реализовать точно так же, как это было сделано в предыдущих двух задачах, потому что в ином случае баланс корня может отличаться от требуемого.

Формат входного файла

В первой строке файла находится число () -- число операций над множеством. Изначально множество пусто. В каждой из последующих строк файла находится описание операции.

Операции бывают следующих видов:

• A x -- вставить число в множество. Если число там уже содержится, множество изменять не следует.
• D x -- удалить число из множества. Если числа нет в множестве, множество изменять не следует.
• C x -- проверить, есть ли число в множестве.

Формат выходного файла

Для каждой операции вида C x выведите Y, если число содержится в множестве, и N, если не содержится.

Для каждой операции вида A x или D x выведите баланс корня дерева после выполнения операции. Если дерево пустое (в нем нет вершин), выведите 0.

Вывод для каждой операции должен содержаться на отдельной строке.

Пример

input.txt

6
A 3
A 4
A 5
C 4
C 6
D 5

output.txt

0
1
0
Y
N
-1

Решение

OrderedSet.scala