AVL

Laboratorio de árboles y montículos en C

Árbol AVL auto-balanceado.

Abrir guía de AVL

1 Preparar

Los ejemplos construyen el estado mediante operaciones públicas reales.

2 Predecir

Formula una hipótesis antes de revelar el siguiente frame canónico.

Predicción Modo práctica: ocultar siguiente estado

Progreso conceptual de esta sesión: 0 aciertos de 0 intentos.

3 Ejecutar y visualizar

Codigo 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).
 */
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

Interpretar código paso a paso

Velocidad

Actual: +0.00x (1.00x real)

Progreso navegable

Función: — · Profundidad: — · Fase: — · Concepto: —

Paso: 0/0

4 Comprender

Arbol AVL auto-balanceado: mantiene factor de equilibrio por nodo en el rango [-1, 1]. La animacion debe mostrar deteccion del nodo desbalanceado y aplicacion de rotaciones (LL, RR, LR, RL) sincronizadas con la linea C que se interpreta.

Prepara una operación para observar ruta, caso e invariante.

Condición, ruta y caso

Sin frame.

Pila recursiva y retornos

Sin llamadas.

Invariante y evidencia

Sin verificación.

Variables C

Sin variables.

Memoria y enlaces

Sin transición de memoria.

Relaciones estructurales

Sin relaciones.

6 Comparar

Ambos lados reciben copias independientes de la misma entrada inmutable.

Prepara una comparación para estudiar forma, altura, ajustes, costo e invariante.

7 Reflexionar

Consola C (printf)

terminal

Historial

Estructura del TAD

typedef struct nodoAVL {
    int nro;                 
    int FE;                  
    struct nodoAVL *der;     
    struct nodoAVL *izq;     
    struct nodoAVL *padre;   
} nodoAVL;

typedef nodoAVL* AVL;