Visualizador Web de Estructuras de Datos

Código C: Insertar

/**
 * @brief Consulta el abuelo sin mutar ni transferir propiedad.
 * @param n Nodo prestado vivo o NULL.
 * @return Alias prestado al padre del padre, o NULL si n o su padre son NULL.
 * @pre Los enlaces de nodos no NULL consultados apuntan a reservas vivas consistentes.
 * @note No recorre todo el arbol, imprime, reserva o libera memoria; O(1).
 */
RBT rbt_abuelo(RBT n) {
    if ((n != NULL) && (n->padre != NULL))
        return n->padre->padre;
    else
        return NULL;
}

/**
 * @brief Consulta el hermano del padre mediante rbt_abuelo.
 * @param n Nodo prestado vivo o NULL.
 * @return Alias al hijo opuesto del abuelo; NULL si no hay abuelo o tio.
 * @pre Los enlaces padre/hijos consultados son vivos y consistentes.
 * @note Si el padre es hijo izquierdo devuelve der; en otro caso devuelve izq.
 * No muta, imprime, reserva ni libera; el alias no transfiere propiedad; O(1).
 */
RBT rbt_tio(RBT n) {
    RBT a = rbt_abuelo(n);
    if (a == NULL)
        return NULL;
    if (n->padre == a->izq)
        return a->der;
    else
        return a->izq;
}

/**
 * @brief Rota a la derecha conservando identidad y orden de los nodos.
 * @param r Referencia escribible a la raiz; NULL es no-op.
 * @param nodoRBT Pivote vivo; NULL o hijo izq NULL es no-op.
 * @pre Para una rotacion efectiva, el pivote pertenece al arbol y padre/hijos
 * son vivos y consistentes. Su hijo izquierdo y el posible subarbol transferido son vivos.
 * @note Actualiza el enlace del padre o *r, transfiere B->der a A->izq,
 * coloca A como B->der y corrige padres. No reserva, libera, imprime ni recolorea;
 * O(1). La rotacion aislada no garantiza todas las reglas rojo-negro.
 * Los enlaces intermedios son pasos de escritura, no un arbol final certificado.
 */
void rbt_rotar_dcha(RBT *r, RBT nodoRBT) {
    if (r == NULL || nodoRBT == NULL || nodoRBT->izq == NULL) {
        return;
    }

    RBT padre = nodoRBT->padre;
    RBT A = nodoRBT;
    RBT B = A->izq;
    RBT C = B->der;
    if (padre != NULL) {
        if (padre->der == A)
            padre->der = B;
        else
            padre->izq = B;
    } else
        *r = B;

    A->izq = C;
    B->der = A;
    A->padre = B;
    if (C)
        C->padre = A;
    B->padre = padre;
}

/**
 * @brief Rota a la izquierda conservando identidad y orden de los nodos.
 * @param r Referencia escribible a la raiz; NULL es no-op.
 * @param nodoRBT Pivote vivo; NULL o hijo der NULL es no-op.
 * @pre Para una rotacion efectiva, el pivote pertenece al arbol y padre/hijos
 * son vivos y consistentes. Su hijo derecho y el posible subarbol transferido son vivos.
 * @note Actualiza el enlace del padre o *r, transfiere B->izq a A->der,
 * coloca A como B->izq y corrige padres. No reserva, libera, imprime ni recolorea;
 * O(1). La rotacion aislada no garantiza todas las reglas rojo-negro.
 * Los enlaces intermedios son pasos de escritura, no un arbol final certificado.
 */
void rbt_rotar_izda(RBT *r, RBT nodoRBT) {
    if (r == NULL || nodoRBT == NULL || nodoRBT->der == NULL) {
        return;
    }

    RBT padre = nodoRBT->padre;
    RBT A = nodoRBT;
    RBT B = A->der;
    RBT C = B->izq;
    if (padre != NULL) {
        if (padre->der == A)
            padre->der = B;
        else
            padre->izq = B;
    } else
        *r = B;

    A->der = C;
    B->izq = A;
    A->padre = B;
    if (C)
        C->padre = A;
    B->padre = padre;
}

/**
 * @brief Recolorea padre/abuelo y rota el abuelo del caso alineado.
 * @param n Nodo vivo en configuracion LL o RR de la reparacion.
 * @param arbol Referencia escribible y no NULL a la raiz.
 * @pre Contexto valido de insercion; padre y abuelo vivos no NULL, enlaces
 * consistentes y tio negro o NULL. No es entrada general para un nodo arbitrario.
 * @note Padre NEGRO y abuelo ROJO; LL rota dcha, el caso espejo rota izda.
 * Las rotaciones conservan reservas/valores y pueden cambiar *arbol. Void,
 * sin reserva/free/printf; no asegura una invariante global en cada escritura parcial.
 */
void rbt_insercion_caso5(RBT n, RBT *arbol) {
    RBT a = rbt_abuelo(n);
    n->padre->rbt_color = NEGRO;
    a->rbt_color = ROJO;
    if ((n == n->padre->izq) && (n->padre == a->izq)) {
        rbt_rotar_dcha(arbol, a);
    } else {
        rbt_rotar_izda(arbol, a);
    }
}

/**
 * @brief Alinea un triangulo y pasa el alias ajustado a caso5.
 * @param n Nodo vivo con padre rojo y abuelo no NULL.
 * @param arbol Referencia escribible y no NULL a la raiz.
 * @pre Contexto valido de insercion, tio negro o NULL y enlaces consistentes.
 * @note LR: rota izda en padre y nuevo_n=n->izq; RL: rota dcha en padre
 *  y nuevo_n=n->der. Si ya esta alineado no rota aqui. n no se reasigna:
 *  nuevo_n es otro local y puede identificar al padre previo. Luego llama caso5.
 * Retorna void; no reserva/libera/imprime ni recolorea directamente.
 */
void rbt_insercion_caso4(RBT n, RBT *arbol) {
    RBT a = rbt_abuelo(n);
    RBT nuevo_n = n;

    if ((n == n->padre->der) && (n->padre == a->izq)) {
        rbt_rotar_izda(arbol, n->padre);
        nuevo_n = n->izq;
    } else if ((n == n->padre->izq) && (n->padre == a->der)) {
        rbt_rotar_dcha(arbol, n->padre);
        nuevo_n = n->der;
    }
    rbt_insercion_caso5(nuevo_n, arbol);
}

/**
 * @brief Recolorea padre y tio rojos o delega al caso geometrico.
 * @param n Nodo vivo con padre rojo y abuelo no NULL.
 * @param arbol Referencia escribible y no NULL a la raiz.
 * @pre Contexto valido de insercion, enlaces vivos consistentes.
 * @note Tio rojo: padre y tio NEGRO, abuelo ROJO y caso1 sobre el abuelo.
 * Tio negro o NULL: caso4. La recursion puede propagar la reparacion a ancestros;
 * no cambia valores ni reserva/libera/imprime. Retorno void.
 */
void rbt_insercion_caso3(RBT n, RBT *arbol) {
    RBT t = rbt_tio(n);
    RBT a;

    if ((t != NULL) && (t->rbt_color == ROJO)) {
        n->padre->rbt_color = NEGRO;
        t->rbt_color = NEGRO;
        a = rbt_abuelo(n);
        a->rbt_color = ROJO;
        rbt_insercion_caso1(a, arbol);
    } else {
        rbt_insercion_caso4(n, arbol);
    }
}

/**
 * @brief Termina si el padre es negro o delega a caso3.
 * @param n Nodo vivo con padre no NULL en la reparacion.
 * @param arbol Referencia escribible y no NULL a la raiz.
 * @pre Contexto valido de insercion y enlaces vivos consistentes.
 * @note Padre negro no cambia campos; padre rojo requiere reparar. Este caso
 * no comprueba globalmente orden, altura negra ni padres. Void, sin reserva/free/printf.
 */
void rbt_insercion_caso2(RBT n, RBT *arbol) {
    if (n->padre->rbt_color == NEGRO)
        return;
    else
        rbt_insercion_caso3(n, arbol);
}

/**
 * @brief Pinta de negro un nodo sin padre o continua la reparacion.
 * @param n Nodo vivo de la reparacion, insertado o ancestro al propagar recoloreos.
 * @param arbol Referencia escribible y no NULL a la raiz.
 * @pre Contexto valido de insercion; n no es NULL y enlaces vivos son consistentes.
 * @note Decide por n->padre==NULL, no por una comparacion con *arbol.
 * Si no es raiz llama caso2. Retorna void, sin reserva, free ni printf.
 */
void rbt_insercion_caso1(RBT n, RBT *arbol) {
    if (n->padre == NULL)
        n->rbt_color = NEGRO;
    else
        rbt_insercion_caso2(n, arbol);
}

/**
 * @brief Inserta un entero distinto mediante enlace BST y reparacion rojo-negro.
 * @param arbol Referencia escribible a la raiz; NULL es no-op.
 * @param dato Entero a insertar, incluidos los extremos del tipo int.
 * @pre Si arbol no es NULL, *arbol es NULL o un arbol rojo-negro finito, ordenado,
 * con enlaces padre/hijos consistentes y reservas vivas propias del TAD.
 * @note Retorna void. Duplicado, arbol NULL o fallo de malloc no mutan el arbol
 * ni imprimen confirmacion. No hay codigo de estado para distinguir esos casos.
 * Busca sin reservar; luego malloc crea una reserva inicialmente no inicializada.
 * Escribe dato, hijos NULL, padre y ROJO antes de publicar el enlace o la raiz.
 * Los auxiliares reparan por recoloreos/rotaciones sin reservar ni liberar nodos.
 * Solo despues de la reparacion imprime "El numero ha sido insertado" con tabulador y salto.
 * La raiz final es negra; las hojas C son NULL, no reservas NIL. Tiempo O(log n)
 * y pila O(log n) bajo la precondicion; malloc reserva un nodo y no se llama free.
 * @warning El caller no debe interpretar el retorno void como una confirmacion
 * ni volver a ejecutar para descubrir si la primera llamada inserto.
 */
void rbt_insertar(RBT *arbol, int dato) {
    if (arbol == NULL) {
        return;
    }

    RBT padre = NULL;
    RBT actual = *arbol;
    while (actual != NULL && dato != actual->nro) {
        padre = actual;
        if (dato < actual->nro)
            actual = actual->izq;
        else if (dato > actual->nro)
            actual = actual->der;
    }
    if (actual != NULL)
        return;
    actual = malloc(sizeof(struct nodoRBT));
    if (actual == NULL) {
        return;
    }
    actual->nro = dato;
    actual->izq = actual->der = NULL;
    actual->padre = padre;
    actual->rbt_color = ROJO;
    if (padre == NULL) {
        *arbol = actual;
    } else if (dato < padre->nro) {
        padre->izq = actual;
    } else if (dato > padre->nro) {
        padre->der = actual;
    }
    rbt_insercion_caso1(actual, arbol);
    printf("\tEl numero ha sido insertado\n");
}