Laboratorio de árboles y montículos en C
AVL
Acerca de esta estructura
Árbol AVL auto-balanceado.
1 Preparar
Ejemplos guiados
Los ejemplos construyen el estado mediante operaciones públicas reales.
2 Predecir
Prepara una traza para predecir una condición aún no ejecutada.
Practica anticipando una condición C antes de revelar su resultado: elige Insertar y un valor, activa Paso a paso y pulsa Ejecutar operación. Responde Verdadero o Falso; NULL indica ausencia de un nodo referenciado.
Comprobar u omitir avanza varias instrucciones hasta esa decisión; Siguiente paso avanza solo una instrucción. El estado visible es el anterior a la decisión.
Durante un lote, la predicción y los controles individuales quedan bloqueados para no mezclar operaciones. Finaliza el lote o pulsa Detener lote y prepara una operación individual. Detener conserva la operación ya aceptada y descarta las pendientes.
Progreso conceptual de esta sesión: 0 aciertos de 0 intentos.
3 Ejecutar y visualizar
Código C: Insertar
/**
* @brief Inserta un valor en el árbol AVL.
* @param raiz Referencia a la raíz del árbol.
* @param x Valor a avl_insertar (no se insertan duplicados).
* @pre raiz apunta a una variable valida (o es NULL); su arbol inicial tiene enlaces finitos/aciclicos, orden estricto, padres consistentes y FE exactos de un AVL equilibrado.
* @note Retorna void: referencia raiz NULL, duplicado o fallo de malloc no producen estado de error retornado ni cambian el arbol. La API web rechaza duplicados antes de mutar; no equivale a ejecutar este cuerpo C.
* @note Un valor nuevo reserva exactamente un nodo, inicializa nro/FE/hijos/padre y luego lo publica mediante raiz o enlace del padre. Los campos de malloc no se leen antes de inicializarlos.
* @note Conserva identidades/valores de nodos previos; no libera reservas ni imprime. Recorre con padre/actual, propaga FE con n/padre y compone las rotaciones necesarias; enlaces y FE parciales no certifican un AVL terminado.
* @note Cada nueva reserva queda propiedad del llamador hasta liberarla con avl_liberarAVL. No modifica referencias prestadas externas; pueden cambiar los enlaces/raiz pero no la identidad de reservas previas.
*/
void avl_insertar(AVL *raiz, int x) {
if (raiz == NULL) {
return;
}
AVL padre = NULL, actual = *raiz;
while (actual != NULL) {
padre = actual;
if (x < actual->nro)
actual = actual->izq;
else if (x > actual->nro)
actual = actual->der;
else
return; // no duplicados
}
AVL nuevo = malloc(sizeof(*nuevo));
if (nuevo == NULL) {
return;
}
nuevo->nro = x;
nuevo->FE = 0;
nuevo->izq = nuevo->der = NULL;
nuevo->padre = padre;
if (padre == NULL) {
*raiz = nuevo;
return;
}
if (x < padre->nro)
padre->izq = nuevo;
else
padre->der = nuevo;
// Rebalanceo incremental tras inserción
AVL n = nuevo;
while (padre != NULL) {
if (n == padre->izq)
padre->FE--;
else
padre->FE++;
if (padre->FE == 0)
break;
if (padre->FE == -2) {
if (n->FE <= 0)
avl_RSD(raiz, padre);
else
avl_RDD(raiz, padre);
break;
}
if (padre->FE == 2) {
if (n->FE >= 0)
avl_RSI(raiz, padre);
else
avl_RDI(raiz, padre);
break;
}
n = padre;
padre = padre->padre;
}
}3 Controlar la ejecución
Actual: +0.00x (1.00x real)
Función: — · Profundidad: — · Fase: — · Concepto: —
Paso: 0/0
4 Comprender
Referencia completa de la estructura
Árbol AVL auto-balanceado: mantiene factor de equilibrio por nodo en el rango [-1, 1]. La animación debe mostrar detección del nodo desbalanceado y aplicación de rotaciones (LL, RR, LR, RL) sincronizadas con la linea C que se interpreta. Las rotaciones C conservan valores y reservas, reenlazan padres/raíz y actualizan FE como altura(derecho)-altura(izquierdo), sin poner ambos a cero. Las simples calculan primero A y luego B con formulas O(1); las dobles componen dos simples sin preasignar FE. También contemplan hijo equilibrado al eliminar y nieto FE-1/0/1. El llamador mantiene factores de ancestros; durante la reconexion y antes de actualizar FE no se debe afirmar un AVL terminado. Estas correcciones nativas no certifican por sí solas cada traza visual. Eliminar retorna void y no imprime. Con dos hijos intercambia el valor con el sucesor y libera su reserva; la reserva encontrada inicialmente puede seguir viva con otro valor. Sin hijos o con uno, publica el enlace y el padre del hijo antes de free. Los alias de la reserva retirada dejan de ser utilizables. Vacío/ausencia son rechazos web; el C deja el árbol intacto. El reequilibrio recalcula alturas y puede visitar la nueva raíz del subárbol después de rotar. Validar muestra un auxiliar de equilibrio por alturas: no revisa orden ABB ni FE almacenado. El backend revisa orden y equilibrio por separado. NULL retorna 1 en el auxiliar; la primera diferencia fuera de -1..1 corta la recursión. Su traza elige altura derecha y después izquierda, aunque C permite otro orden de operandos de la resta. El main del historial reproduce consultas exitosas, incluidas repeticiones; recargar conserva esas consultas sin ejecutarlas otra vez. Máximo, Inorden y equilibrio por alturas usan los auxiliares mostrados, incluidos una vez en ese programa; no son exportaciones del C/H descargable. Inorden imprime valores ascendentes, no avl_verArbol. La comprobación de equilibrio por alturas no certifica el FE almacenado. Compile el main junto a tad_avl.c; los rechazos se anotan sin ejecutar la llamada fallida.
Condición, ruta y caso
Pila recursiva y retornos
Invariante y evidencia
Variables C
Memoria y enlaces
Relaciones estructurales
6 Comparar
Elige una pareja o una estructura contra todas. Cada una recibe una copia independiente de la misma entrada inmutable; los pasos corresponden a inserciones completas.
Prepara una comparación para estudiar forma, altura, orden e invariante después de cada inserción.
7 Reflexionar
Consola C (printf)
Programa principal del historial
Estructura del TAD
typedef struct nodoAVL {
int nro; /**< Dato entero almacenado. */
int FE; /**< Factor de equilibrio: altura del hijo derecho menos altura del izquierdo. */
struct nodoAVL *der; /**< Hijo derecho. */
struct nodoAVL *izq; /**< Hijo izquierdo. */
struct nodoAVL *padre; /**< Enlace al padre del nodo. */
} nodoAVL;
typedef nodoAVL* AVL;