Gestión estratégica de puestos de avanzada con árboles AVL #43
Description
Contexto
En el mundo postapocalíptico de Refugio 33, existen múltiples puestos de avanzadas distribuidos a lo largo del mapa. Cada puesto de avanzadas tiene una prioridad estratégica basada en factores como acceso a recursos, nivel de amenaza o valor geopolítico. Para tomar decisiones tácticas (por ejemplo, enviar ayuda, evacuar o reforzar), es necesario contar con una estructura de datos eficiente que permita:
- Insertar nuevos puestos de avanzadas.
- Eliminar puestos de avanzadas comprometidos.
- Buscar puestos de avanzadas por su identificador.
- Obtener rápidamente el puesto de avanzada con la prioridad más alta o más baja.
- Recorrer todos los puestos de avanzadas en orden creciente o decreciente de prioridad.
El equipo de desarrollo ha decidido usar un árbol AVL, dado que garantiza tiempos logarítmicos en todas estas operaciones.
Objetivo
Implementar una clase AVLTree que administre puestos de avanzadas según su prioridad estratégica. Cada nodo del árbol debe contener:
outpostId(entero): identificador único.- Otros datos necesarios
Requisitos funcionales
La clase AVLTree debe incluir:
void insert(int outpostId)void remove(int outpostId)bool contains(int outpostId)int findMin()→ Devuelve el ID del puesto de avanzada con menor prioridad.int findMax()→ Devuelve el ID del puesto de avanzada con mayor prioridad.void printInOrder()→ Muestra los puestos de avanzada ordenados por prioridad creciente.void printStats()→ Devuelve toda la información del árbol (Cantidad de nodos, altura, profundidad, etc)
Además, cada operación debe mantener balanceado el árbol. Es decir, después de cada inserción o eliminación, se deben aplicar rotaciones si la diferencia de altura entre subárboles excede 1.
Notas de implementación
- Se deben aplicar las rotaciones necesarias: simple derecha, simple izquierda, doble derecha, doble izquierda.
- El balance se define como:
altura(izquierdo) - altura(derecho)∈ {-1, 0, 1}. - Podés usar punteros raw o smart.