Visualizador Web de Estructuras de Datos

Codigo C: Insertar

/**
 * @brief Devuelve el rbt_abuelo de un nodo.
 * @param n Nodo dado.
 * @return Puntero al rbt_abuelo o NULL si no existe.
 */
RBT rbt_abuelo(RBT n) {
    if ((n != NULL) && (n->padre != NULL))
        return n->padre->padre;
    else
        return NULL;
}

/**
 * @brief Devuelve el tío de un nodo (hermano del padre).
 * @param n Nodo dado.
 * @return Puntero al tío o NULL si no existe.
 */
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 Rotación simple derecha.
 * @param r Referencia a la raíz del árbol.
 * @param nodoRBT Nodo sobre el que se aplica la rotación.
 */
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 Rotación simple izquierda.
 * @param r Referencia a la raíz del árbol.
 * @param nodoRBT Nodo sobre el que se aplica la rotación.
 */
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 Caso 5 de inserción: rotación final y recoloreo.
 * @param n Nodo insertado.
 * @param arbol Referencia a la raíz del árbol.
 */
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 Caso 4 de inserción: ajuste para alinear nodo, padre y rbt_abuelo.
 * @param n Nodo insertado (puede cambiar tras rotación).
 * @param arbol Referencia a la raíz del árbol.
 */
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 Caso 3 de inserción: tío rojo o tío negro.
 * @param n Nodo insertado.
 * @param arbol Referencia a la raíz del árbol.
 */
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 Caso 2 de inserción: si padre es negro, árbol válido.
 * @param n Nodo insertado.
 * @param arbol Referencia a la raíz del árbol.
 */
void rbt_insercion_caso2(RBT n, RBT *arbol) {
    if (n->padre->rbt_color == NEGRO)
        return;
    else
        rbt_insercion_caso3(n, arbol);
}

/**
 * @brief Caso 1 de inserción: si es raíz, pintar de negro.
 * @param n Nodo insertado.
 * @param arbol Referencia a la raíz del árbol.
 */
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 valor en el árbol Rojo-Negro.
 * @param arbol Referencia a la raíz del árbol.
 * @param dato Valor a rbt_insertar.
 */
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");
}