Ayuda | ABB

ABB

Descripcion del TAD

Arbol binario de busqueda sin duplicados: todo valor menor va al subarbol izquierdo y todo valor mayor al derecho. En la simulacion revisa la ruta de comparaciones y confirma que la propiedad de orden se preserve despues de cada insercion o eliminacion. El ABB organiza claves por orden: menores a la izquierda y mayores a la derecha. La traza debe reflejar comparaciones sucesivas, decisiones condicionales y retorno recursivo.

Guía de aprendizaje

Objetivo: Decidir la rama y justificar los tres casos de eliminación.

Estrategia: Comparar, descender recursivamente y reconectar el subárbol retornado.

Invariante: izquierdo < nodo < derecho en todos los nodos.

Memoria C: Cada nodo se reserva con malloc y se libera al eliminar o limpiar.

Complejidad: O(h); promedio O(log n), peor O(n).

Errores frecuentes

Confundir ABB con árbol balanceado.
Olvidar reconectar el retorno recursivo.

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

abb_insertar
abb_eliminar
abb_buscar
abb_encontrarMinimo
abb_encontrarMaximo
abb_altura
abb_contarHojas
abb_inorden
abb_preorden
abb_postorden
abb_validar_rango
abb_liberarArbol

Operaciones pendientes / restricciones

No hay operaciones pendientes para esta estructura en esta fase.

Estructura del TAD en C

typedef struct ABBNodo {
    int valor;                
    struct ABBNodo *izquierdo;   
    struct ABBNodo *derecho;     
} ABBNodo;

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 binario de búsqueda.
 * @param nodo Puntero a la raíz del árbol.
 * @param valor Valor a abb_insertar.
 * @return Puntero a la raíz actualizada.
 */
ABBNodo* abb_insertar(ABBNodo* nodo, int valor) {
    if (nodo == NULL) {
        ABBNodo* nuevo = malloc(sizeof *nuevo);
        if (nuevo == NULL) {
            return NULL;
        }
        nuevo->valor = valor;
        nuevo->izquierdo = nuevo->derecho = NULL;
        return nuevo;
    }
    if (valor < nodo->valor)
        nodo->izquierdo = abb_insertar(nodo->izquierdo, valor);
    else if (valor > nodo->valor)
        nodo->derecho = abb_insertar(nodo->derecho, valor);
    return nodo;
}

Codigo C: eliminar

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

/**
 * @brief Elimina un valor del árbol binario de búsqueda.
 * @param nodo Puntero a la raíz del árbol.
 * @param valor Valor a abb_eliminar.
 * @return Puntero a la raíz actualizada.
 */
ABBNodo* abb_eliminar(ABBNodo* nodo, int valor) {
    if (nodo == NULL) return nodo;
    if (valor < nodo->valor)
        nodo->izquierdo = abb_eliminar(nodo->izquierdo, valor);
    else if (valor > nodo->valor)
        nodo->derecho = abb_eliminar(nodo->derecho, valor);
    else {
        if (nodo->izquierdo == NULL) {
            ABBNodo* temp = nodo->derecho;
            free(nodo);
            return temp;
        } else if (nodo->derecho == NULL) {
            ABBNodo* temp = nodo->izquierdo;
            free(nodo);
            return temp;
        }
        ABBNodo* temp = abb_encontrarMinimo(nodo->derecho);
        nodo->valor = temp->valor;
        nodo->derecho = abb_eliminar(nodo->derecho, temp->valor);
    }
    return nodo;
}

Codigo C: buscar

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

/**
 * @brief Busca un valor en el árbol binario de búsqueda.
 * @param nodo Puntero a la raíz del árbol.
 * @param valor Valor a abb_buscar.
 * @return Puntero al nodo encontrado o NULL si no existe.
 */
ABBNodo* abb_buscar(ABBNodo* nodo, int valor) {
    if (nodo == NULL || nodo->valor == valor)
        return nodo;
    if (valor < nodo->valor)
        return abb_buscar(nodo->izquierdo, valor);
    else
        return abb_buscar(nodo->derecho, valor);
}

Codigo C: minimo

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

/**
 * @brief Encuentra el nodo con el valor mínimo en el árbol.
 * @param nodo Puntero a la raíz del árbol.
 * @return Puntero al nodo con el valor mínimo.
 */
ABBNodo* abb_encontrarMinimo(ABBNodo* nodo) {
    if (nodo == NULL) {
        return NULL;
    }

    while (nodo->izquierdo != NULL)
        nodo = nodo->izquierdo;
    return nodo;
}

Codigo C: maximo

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

/**
 * @brief Encuentra el nodo con el valor máximo en el árbol.
 * @param nodo Puntero a la raíz del árbol.
 * @return Puntero al nodo con el valor máximo.
 */
ABBNodo* abb_encontrarMaximo(ABBNodo* nodo) {
    while (nodo != NULL && nodo->derecho != NULL)
        nodo = nodo->derecho;
    return nodo;
}

Codigo C: altura

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

/**
 * @brief Calcula la abb_altura del árbol binario de búsqueda.
 * @param nodo Puntero a la raíz del árbol.
 * @return Altura del árbol (número de niveles).
 */
int abb_altura(ABBNodo* nodo) {
    if (nodo == NULL)
        return 0;
    int altIzq = abb_altura(nodo->izquierdo);
    int altDer = abb_altura(nodo->derecho);
    return (altIzq > altDer ? altIzq : altDer) + 1;
}

Codigo C: contar_hojas

Cuenta nodos sin hijos para medir terminales del arbol.

int abb_contarHojas(ABBNodo* nodo) {
    if (nodo == NULL) {
        return 0;
    }
    if (nodo->izquierdo == NULL && nodo->derecho == NULL) {
        return 1;
    }
    return abb_contarHojas(nodo->izquierdo) + abb_contarHojas(nodo->derecho);
}

Codigo C: inorden

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

/**
 * @brief Realiza un recorrido en abb_inorden del árbol.
 * @param nodo Puntero a la raíz del árbol.
 */
void abb_inorden(ABBNodo* nodo) {
    if (nodo != NULL) {
        abb_inorden(nodo->izquierdo);
        printf("%d ", nodo->valor);
        abb_inorden(nodo->derecho);
    }
}

Codigo C: preorden

Recorrido raiz-izquierda-derecha; util para serializar la forma del arbol.

/**
 * @brief Realiza un recorrido en abb_preorden del árbol.
 * @param nodo Puntero a la raíz del árbol.
 */
void abb_preorden(ABBNodo* nodo) {
    if (nodo != NULL) {
        printf("%d ", nodo->valor);
        abb_preorden(nodo->izquierdo);
        abb_preorden(nodo->derecho);
    }
}

Codigo C: postorden

Recorrido izquierda-derecha-raiz; usado en liberacion segura de memoria.

/**
 * @brief Realiza un recorrido en abb_postorden del árbol.
 * @param nodo Puntero a la raíz del árbol.
 */
void abb_postorden(ABBNodo* nodo) {
    if (nodo != NULL) {
        abb_postorden(nodo->izquierdo);
        abb_postorden(nodo->derecho);
        printf("%d ", nodo->valor);
    }
}

Codigo C: validar

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

int abb_validar_rango(ABBNodo* nodo, int minimo, int maximo) {
    if (nodo == NULL) {
        return 1;
    }
    if (nodo->valor <= minimo || nodo->valor >= maximo) {
        return 0;
    }
    if (!abb_validar_rango(nodo->izquierdo, minimo, nodo->valor)) {
        return 0;
    }
    if (!abb_validar_rango(nodo->derecho, nodo->valor, maximo)) {
        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 (abb_postorden).
 * @param nodo Raíz del árbol o subárbol a liberar.
 */
void abb_liberarArbol(ABBNodo* nodo) {
    if (nodo == NULL) return;
    abb_liberarArbol(nodo->izquierdo);
    abb_liberarArbol(nodo->derecho);
    free(nodo);
}

Ir a la visualizacion