Visualizador Web de Estructuras de Datos

Raíz

Nodo sin padre.

Hoja

Nodo sin hijos.

Altura

En ABB, AVL y el auxiliar de Rojo-Negro se cuentan niveles: árbol vacío 0, hoja 1. Revisa la convención de la función que estudias.

Profundidad

Distancia desde la raíz.

FE

Altura del subárbol derecho menos altura del izquierdo.

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.

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;

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

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.
 * @pre raiz es NULL o referencia una variable valida con un AVL finito/aciclico, orden estricto, padres consistentes y FE exactos.
 * @note Retorna void. Referencia raiz NULL, vacio o valor ausente dejan el arbol sin cambios; la API web rechaza vacio/ausencia antes de mutar y no equivale a ejecutar este cuerpo C.
 * @note Con dos hijos intercambia nro con el sucesor minimo del hijo derecho, conservando las reservas durante el intercambio. Despues libera la reserva del sucesor, no necesariamente la reserva encontrada inicialmente.
 * @note Con cero/un hijo reenlaza raiz o padre y actualiza el padre del hijo antes de free. Libera exactamente una reserva si encuentra x; no reserva memoria ni imprime. Los alias a la reserva liberada dejan de ser utilizables; la reserva retenida puede cambiar de valor.
 * @note Reequilibra desde el padre de la reserva retirada mediante alturas y rotaciones. Identidades vivas se conservan; los enlaces, orden y FE intermedios no certifican un AVL final. El llamador mantiene propiedad del arbol restante y debe liberarlo al terminar.
 */
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);
}

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.
  * @note Retorna un alias prestado a una reserva existente o NULL por ausencia/vacio. No reserva, libera ni modifica enlaces. El alias deja de ser utilizable cuando se libera esa reserva.
 */
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;
}

Avanza por la rama izquierda hasta el último nodo para obtener el menor valor del subárbol.

/**
 * @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.
 * @pre nodo debe ser distinto de NULL.
  * @note Requiere nodo no NULL y enlaces validos. Recorre izquierdo cambiando solo su alias local y retorna un alias prestado; no modifica la raiz, reserva ni libera memoria. El llamador debe comprobar el vacio.
 */
AVL avl_minimo(AVL nodo) {
    while (nodo->izq) 
        nodo = nodo->izq;
    return nodo;
}

Avanza por la rama derecha hasta el último nodo para obtener el mayor valor del subárbol.

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

Calcula la altura estructural a partir de la profundidad máxima 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).
  * @note Cuenta niveles: vacio 0 y hoja 1. Calcula las alturas recursivamente sin consultar ni modificar FE o enlaces; no cuenta nodos.
 */
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;
}

Recorrido izquierda-raíz-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);
    }
}

Consulta las reglas indicadas en la referencia avanzada de este TAD. No modifica ni repara la estructura; observa las condiciones que hacen devolver verdadero o falso.

/**
 * @brief Comprueba equilibrio por alturas en cada subarbol.
 * @param nodo Raiz prestada del subarbol; NULL es valido.
 * @return 1 si todas las diferencias altura(der)-altura(izq) estan entre -1 y 1; 0 en otro caso.
 * @pre Enlaces finitos, aciclicos y nodos vivos.
 * @note No verifica orden ABB, padres ni el FE almacenado; la validacion del backend es distinta.
 * @note No muta, reserva, libera ni imprime; cortocircuita al hallar desequilibrio.
 * @note C no fija el orden de los operandos de la resta de alturas; ambas consultas son puras.
 * @note Recalcula alturas por nodo: coste O(n*h), no certificado lineal.
 */
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;
}

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

/**
 * @brief Libera toda la memoria del árbol AVL (postorden).
 * @param raiz Raíz del árbol a liberar.
  * @note Libera hijos izquierdo/derecho antes del padre. Recibe la raiz por valor y no pone a NULL la raiz del llamador: asignar NULL despues de esta llamada. Los alias a reservas liberadas dejan de ser utilizables; NULL no tiene efecto.
 */
void avl_liberarAVL(AVL raiz) {
    if (!raiz) 
        return;
    avl_liberarAVL(raiz->izq);
    avl_liberarAVL(raiz->der);
    free(raiz);
}