Rede de árvores binárias de busca com herança e polimorfismo

Python Hard classes

Tarefa «Rede de árvores binárias de busca com herança e polimorfismo»

Implemente a classe Node para um nó de árvore binária de busca (BST) com os métodos insert, search, delete. Crie a classe BST, que armazena a raiz e contém os métodos insert (inserir valor), search (buscar valor, retorna True/False), delete (remover valor) e get_height (altura da árvore). Em seguida, crie a classe AVLTree, que herda de BST, sobrescrevendo insert e delete para suportar balanceamento (com rotações). Dados de entrada: sequência de comandos. Comandos: "insert x" para inserir x, "delete x" para remover x (se existir), "search x" para exibir "found" ou "not found", "height" para exibir a altura da árvore. Para AVLTree, após cada inserção/remoção, verifica-se o balanço (diferença de altura das subárvores <= 1) e realiza-se a rotação correspondente. Restrições: -10^9 <= x <= 10^9, número de comandos até 10^5.

Formato de Entrada

A primeira linha: um número inteiro n (1 <= n <= 10^5) — a quantidade de comandos. Em seguida, n linhas, cada uma contendo um comando: insert x, delete x, search x ou height.

Formato de Saída

Para cada comando search, exiba "found" ou "not found" em uma linha separada. Para o comando height, exiba um número inteiro — a altura da árvore (altura da árvore vazia = 0).

Exemplos

Exemplo 1

ENTRADA

SAÍDA

Exemplo 2

ENTRADA

2
0 0 0
2 -2 2 -2

SAÍDA

main.py