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 ABBNodo {
    int valor; /**< Dato entero almacenado. */
    struct ABBNodo *izquierdo; /**< Hijo izquierdo. */
    struct ABBNodo *derecho; /**< Hijo derecho. */
} ABBNodo;

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 entero.
 * @return Raíz actualizada; NULL si el árbol estaba vacío y malloc falla.
 * @note Si falla la reserva en un subárbol, se conserva la raíz existente sin insertar el valor.
  * @note El arbol debe ser un ABB valido y aciclico. Un duplicado conserva la misma raiz sin reservar otro nodo. Asigne el retorno a la raiz del llamador; los enlaces internos se modifican. El nuevo nodo se inicializa antes de enlazarlo.
 */
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;
}

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 entero.
 * @return Puntero a la raíz actualizada.
  * @note Un valor ausente conserva la raiz. Asigne el retorno a la raiz del llamador. Con cero o un hijo se libera el nodo encontrado y se retorna el reemplazo. Con dos hijos se copia el valor del sucesor, se conserva la reserva del nodo encontrado y se elimina el sucesor. Los alias al nodo liberado dejan de ser validos.
 */
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;
}

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 entero.
 * @return Puntero al nodo encontrado o NULL si no existe.
  * @note Consulta sin mutacion. El retorno es un alias prestado de un nodo existente, no una copia ni una reserva nueva. NULL tambien representa un arbol vacio.
 */
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);
}

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

/**
 * @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, o NULL si el árbol está vacío.
  * @note Consulta sin mutacion: sigue enlaces izquierdos y retorna un alias prestado, no una reserva nueva. NULL representa el arbol vacio.
 */
ABBNodo* abb_encontrarMinimo(ABBNodo* nodo) {
    if (nodo == NULL) {
        return NULL;
    }

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

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

/**
 * @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, o NULL si el árbol está vacío.
  * @note Consulta sin mutacion: sigue enlaces derechos y retorna un alias prestado, no una reserva nueva. NULL representa el arbol vacio.
 */
ABBNodo* abb_encontrarMaximo(ABBNodo* nodo) {
    while (nodo != NULL && nodo->derecho != NULL)
        nodo = nodo->derecho;
    return nodo;
}

Calcula la altura estructural a partir de la profundidad máxima 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).
  * @note Cuenta niveles: NULL retorna cero y una hoja retorna uno. No cuenta aristas, no modifica el arbol y recorre ambos subarboles.
 */
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;
}

Cuenta nodos sin hijos para medir terminales del árbol.

/**
 * @brief Cuenta hojas sin modificar el arbol ni imprimir.
 * @param nodo Raiz prestada del subarbol, o NULL.
 * @return 0 para NULL, 1 para una hoja, o la suma de ambos subarboles.
 * @note Helper mostrado por la aplicacion; no incluido en el C/H descargado.
 * C no fija el orden de evaluacion de las dos llamadas sumadas.
 * No declara locales para sus resultados parciales; son operandos de la expresion.
 * Tiempo O(n), pila recursiva O(h); no reserva ni libera nodos.
 */
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);
}

Recorrido izquierda-raíz-derecha; en ABB produce valores ordenados de menor a mayor.

/**
 * @brief Realiza un recorrido inorden del árbol.
 * @param nodo Puntero a la raíz del árbol.
  * @note Imprime izquierdo, raiz y derecho en stdout con formato "%d " por nodo, incluido el espacio final y sin agregar salto de linea. NULL no imprime nada. No modifica enlaces ni reserva memoria.
 */
void abb_inorden(ABBNodo* nodo) {
    if (nodo != NULL) {
        abb_inorden(nodo->izquierdo);
        printf("%d ", nodo->valor);
        abb_inorden(nodo->derecho);
    }
}

Recorrido raíz-izquierda-derecha; útil para serializar la forma del árbol.

/**
 * @brief Realiza un recorrido preorden del árbol.
 * @param nodo Puntero a la raíz del árbol.
  * @note Imprime raiz, izquierdo y derecho en stdout con formato "%d " por nodo, incluido el espacio final y sin agregar salto de linea. NULL no imprime nada. No modifica enlaces ni reserva memoria.
 */
void abb_preorden(ABBNodo* nodo) {
    if (nodo != NULL) {
        printf("%d ", nodo->valor);
        abb_preorden(nodo->izquierdo);
        abb_preorden(nodo->derecho);
    }
}

Recorrido izquierda-derecha-raíz; usado en liberación segura de memoria.

/**
 * @brief Realiza un recorrido postorden del árbol.
 * @param nodo Puntero a la raíz del árbol.
  * @note Imprime izquierdo, derecho y raiz en stdout con formato "%d " por nodo, incluido el espacio final y sin agregar salto de linea. NULL no imprime nada. No modifica enlaces ni reserva memoria.
 */
void abb_postorden(ABBNodo* nodo) {
    if (nodo != NULL) {
        abb_postorden(nodo->izquierdo);
        abb_postorden(nodo->derecho);
        printf("%d ", nodo->valor);
    }
}

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 Valida orden ABB estricto con limites opcionales, sin mutacion.
 * @param nodo Raiz del subarbol finito y aciclico; NULL admitido.
 * @param hay_minimo Indicador de limite inferior presente; cero lo omite.
 * @param minimo Limite inferior exclusivo, solo comparado si hay_minimo.
 * @param hay_maximo Indicador de limite superior presente; cero lo omite.
 * @param maximo Limite superior exclusivo, solo comparado si hay_maximo.
 * @return 1 si el subarbol respeta todos los limites; 0 si no.
 * @note Auxiliar didactico de la aplicacion; no exportado por el C/H del TAD.
 * La llamada inicial usa 0,0,0,0: INT_MIN e INT_MAX son claves validas.
 * No usa sentinelas fuera de int ni suma/resta uno. Los limites presentes
 * rechazan igualdad y duplicados. El cortocircuito omite limites ausentes
 * y omite el subarbol derecho cuando el izquierdo resulta invalido.
 */
int abb_validar_rango(ABBNodo* nodo, int hay_minimo, int minimo, int hay_maximo, int maximo) {
    if (nodo == NULL) {
        return 1;
    }
    if ((hay_minimo && nodo->valor <= minimo) || (hay_maximo && nodo->valor >= maximo)) {
        return 0;
    }
    if (!abb_validar_rango(nodo->izquierdo, hay_minimo, minimo, 1, nodo->valor)) {
        return 0;
    }
    if (!abb_validar_rango(nodo->derecho, 1, nodo->valor, hay_maximo, maximo)) {
        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 (abb_postorden).
 * @param nodo Raíz del árbol o subárbol a liberar.
  * @note Libera cada nodo en orden izquierdo, derecho y raiz; NULL no hace nada. El parametro se recibe por valor: no pone a NULL la raiz del llamador. Despues de la llamada, asigne NULL a esa raiz y no use los alias a las reservas liberadas.
 */
void abb_liberarArbol(ABBNodo* nodo) {
    if (nodo == NULL) return;
    abb_liberarArbol(nodo->izquierdo);
    abb_liberarArbol(nodo->derecho);
    free(nodo);
}