RU
EN
ES
ZH
FR
DE
PT
AR
HI
Сеть бинарных деревьев поиска с наследованием и полиморфизмом
Python
Сложный
classes
Задача «Сеть бинарных деревьев поиска с наследованием и полиморфизмом»
Реализуйте класс Node для узла бинарного дерева поиска (BST) с методами insert, search, delete. Создайте класс BST, который хранит корень и содержит методы insert (добавление значения), search (поиск значения, возвращает True/False), delete (удаление значения), и get_height (высота дерева). Затем создайте класс AVLTree, наследующий от BST, переопределяющий insert и delete для поддержки балансировки (с поворотами). Входные данные: последовательность команд. Команды: "insert x" добавить x, "delete x" удалить x (если есть), "search x" вывести "found" или "not found", "height" вывести высоту дерева. Для AVLTree после каждой вставки/удаления проверяется баланс (разница высот поддеревьев <= 1) и выполняется соответствующий поворот. Ограничения: -10^9 <= x <= 10^9, количество команд до 10^5.
Формат ввода
Первая строка: одно целое число n (1 <= n <= 10^5) — количество команд. Затем n строк, каждая содержит команду: insert x, delete x, search x или height.
Формат вывода
Для каждой команды search выведите "found" или "not found" в отдельной строке. Для команды height выведите одно целое число — высоту дерева (высота пустого дерева = 0).
Примеры
Пример 1
ВВОД
3
1 2 -3 4
-1 -2
5 0 3
ВЫВОД
Пример 2
ВВОД
2
0 0 0
2 -2 2 -2
ВЫВОД
main.py