ES
RU
EN
ZH
FR
DE
PT
AR
HI
Red de árboles binarios de búsqueda con herencia y polimorfismo
Python
Hard
classes
Tarea «Red de árboles binarios de búsqueda con herencia y polimorfismo»
Implemente la clase Node para un nodo de árbol binario de búsqueda (BST) con los métodos insert, search, delete. Cree la clase BST, que almacena la raíz y contiene los métodos insert (agregar valor), search (buscar valor, devuelve True/False), delete (eliminar valor) y get_height (altura del árbol). Luego, cree la clase AVLTree, que hereda de BST, redefiniendo insert y delete para soportar el balanceo (con rotaciones). Datos de entrada: una secuencia de comandos. Comandos: "insert x" agregar x, "delete x" eliminar x (si existe), "search x" imprimir "found" o "not found", "height" imprimir la altura del árbol. Para AVLTree, después de cada inserción/eliminación se verifica el balance (diferencia de alturas de subárboles <= 1) y se realiza la rotación correspondiente. Restricciones: -10^9 <= x <= 10^9, cantidad de comandos hasta 10^5.
Formato de entrada
Primera línea: un número entero n (1 <= n <= 10^5) — la cantidad de comandos. Luego, n líneas, cada una contiene un comando: insert x, delete x, search x o height.
Formato de salida
Para cada comando search, imprima "found" o "not found" en una línea separada. Para el comando height, imprima un número entero — la altura del árbol (altura del árbol vacío = 0).
Ejemplos
Ejemplo 1
ENTRADA
3
1 2 -3 4
-1 -2
5 0 3
SALIDA
Ejemplo 2
ENTRADA
2
0 0 0
2 -2 2 -2
SALIDA
main.py