Ayuda | AVL

AVL

Descripcion del TAD

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. El AVL extiende al ABB con balanceo automatico. Ademas de insertar/eliminar, se interpretan factores de equilibrio y rotaciones para sostener altura logaritmica.

Guía de aprendizaje

Objetivo: Relacionar altura y FE con LL, RR, LR y RL.

Estrategia: Operar como ABB, actualizar alturas y reparar el primer desequilibrio.

Invariante: Orden ABB y |FE| ≤ 1 por nodo.

Memoria C: Las rotaciones cambian enlaces; no crean ni destruyen nodos.

Complejidad: Búsqueda, inserción y eliminación O(log n).

Errores frecuentes

Rotar según el valor sin calcular FE.
No actualizar alturas después de rotar.

Glosario jerárquico

Raíz: Nodo sin padre.
Hoja: Nodo sin hijos.
Altura: Longitud del camino máximo hacia una hoja.
Profundidad: Distancia desde la raíz.
FE: Diferencia de alturas entre subárboles.
Rotación: Cambio local de enlaces que conserva el orden.
Recoloreo: Cambio de colores para reparar reglas rojo-negro.
Black-height: Cantidad de nodos negros por camino hasta NIL.
Heapify: Proceso de restaurar la propiedad de heap.

Controles de ejecucion paso a paso

Checkbox Interpretar codigo paso a paso: activado muestra toda la traza; desactivado aplica solo el resultado final.
Botones: Preparar, Reproducir, Pausar, Inicio, Anterior, Siguiente, Final y Repetir.
Navegacion por traza: Anterior paso y Siguiente paso.
Velocidad de simulacion: slider de -2x a +2x (0.00x = 1.00x real).
En modo rapido (checkbox desactivado), el resultado visual final debe coincidir con el ultimo estado de la traza interpretada.
Al llegar al ultimo paso, Siguiente paso se bloquea hasta cambiar entradas/operacion; Anterior paso se habilita solo cuando ya avanzaste.

Teclado y accesibilidad

←/→: retroceder o avanzar.
Inicio/Fin: primer o último estado.
Espacio: pausar.
Los colores, rotaciones e invariantes incluyen texto y símbolos; con movimiento reducido se desactivan transiciones prolongadas.

Operaciones soportadas

avl_insertar
avl_eliminar
avl_buscar
avl_minimo
avl_maximo
avl_altura
avl_inorden
avl_validar_fes
avl_liberarAVL

Operaciones pendientes / restricciones

El TAD no expone informacion textual de rotaciones realizadas.

Estructura del TAD en C

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

typedef nodoAVL* AVL;

Metodos del TAD en C

Codigo C: insertar

Inserta respetando reglas de orden/balance del TAD y actualiza punteros estructurales necesarios.

/**
 * @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;
    }
}

Codigo C: eliminar

Localiza el objetivo y aplica el caso de borrado correspondiente (hoja, un hijo, dos hijos o rebalanceo).

/**
 * @brief Elimina el valor indicado del árbol AVL (con rebalanceo).
 * @param raiz Referencia a la raíz del árbol.
 * @param x Valor a avl_eliminar.
 */
void avl_eliminar(AVL *raiz, int x) {
    if (raiz == NULL) {
        return;
    }

    AVL z = avl_buscar(*raiz, x);
    if (!z) return;

    // Si tiene dos hijos, intercambiar con el sucesor inorden y descender
    while (z->izq && z->der) {
        AVL s = avl_minimo(z->der);
        int tmp = z->nro;
        z->nro = s->nro;
        s->nro = tmp;
        z = s; // continuar eliminando más abajo
    }

    // Ahora z tiene 0 o 1 hijo: avl_eliminar físicamente
    AVL padre = z->padre;
    AVL child = (z->izq) ? z->izq : z->der;
    if (child) child->padre = padre;

    if (!padre) {
        *raiz = child;
    } else if (padre->izq == z) {
        padre->izq = child;
    } else {
        padre->der = child;
    }
    free(z);

    // Reequilibrar subiendo desde el padre
    if (padre) rebalancearTrasEliminar(raiz, padre);
}

Codigo C: buscar

Navega por comparaciones hasta encontrar el valor o concluir que no existe.

/**
 * @brief Busca un valor en el árbol AVL.
 * @param raiz Raíz del árbol.
 * @param x Valor a avl_buscar.
 * @return Puntero al nodo con el valor o NULL si no se encuentra.
 */
AVL avl_buscar(AVL raiz, int x) {
    if (!raiz) 
        return NULL;
    if (x < raiz->nro) 
        return avl_buscar(raiz->izq, x);
    if (x > raiz->nro) 
        return avl_buscar(raiz->der, x);
    return raiz;
}

Codigo C: minimo

Avanza por la rama izquierda hasta el ultimo nodo para obtener el menor valor del subarbol.

/**
 * @brief Obtiene el nodo con el valor mínimo del subárbol dado.
 * @param nodo Raíz del subárbol.
 * @return Puntero al nodo con el valor mínimo.
 */
AVL avl_minimo(AVL nodo) {
    while (nodo->izq) 
        nodo = nodo->izq;
    return nodo;
}

Codigo C: maximo

Avanza por la rama derecha hasta el ultimo nodo para obtener el mayor valor del subarbol.

AVL avl_maximo(AVL raiz) {
    AVL aux = raiz;
    while (aux != NULL && aux->der != NULL) {
        aux = aux->der;
    }
    return aux;
}

Codigo C: altura

Calcula la altura estructural a partir de la profundidad maxima de sus ramas.

/**
 * @brief Calcula la avl_altura del árbol (número de niveles).
 * @param arbol Raíz del árbol.
 * @return Altura del árbol (0 si está vacío).
 */
int avl_altura(AVL arbol) {
    if (arbol == NULL) 
        return 0;
    int altIzq = avl_altura(arbol->izq);
    int altDer = avl_altura(arbol->der);
    return (altIzq > altDer ? altIzq : altDer) + 1;
}

Codigo C: inorden

Recorrido izquierda-raiz-derecha; en ABB produce valores ordenados de menor a mayor.

void avl_inorden(AVL nodo) {
    if (nodo != NULL) {
        avl_inorden(nodo->izq);
        printf("%d ", nodo->nro);
        avl_inorden(nodo->der);
    }
}

Codigo C: validar

Comprueba invariantes del TAD (orden, balance o reglas de color segun corresponda).

int avl_validar_fes(AVL nodo) {
    if (nodo == NULL) {
        return 1;
    }
    int fe = avl_altura(nodo->der) - avl_altura(nodo->izq);
    if (fe < -1 || fe > 1) {
        return 0;
    }
    if (!avl_validar_fes(nodo->izq)) {
        return 0;
    }
    if (!avl_validar_fes(nodo->der)) {
        return 0;
    }
    return 1;
}

Codigo C: limpiar

Recorre la estructura liberando todos los nodos y deja el puntero raiz en estado nulo para reinicio seguro.

/**
 * @brief Libera toda la memoria del árbol AVL (postorden).
 * @param raiz Raíz del árbol a liberar.
 */
void avl_liberarAVL(AVL raiz) {
    if (!raiz) 
        return;
    avl_liberarAVL(raiz->izq);
    avl_liberarAVL(raiz->der);
    free(raiz);
}

Ir a la visualizacion