Ayuda | Rojo-Negro

Rojo-Negro

Descripcion del TAD

Arbol balanceado por reglas de color (rojo/negro) que limitan la altura. Durante la simulacion observa recoloreos y rotaciones para mantener raiz negra, sin rojos consecutivos y con altura negra consistente entre caminos. El Arbol Rojo-Negro usa reglas de color para mantener balance aproximado. Didacticamente interesa seguir recoloreos, rotaciones y validacion de invariantes tras cada cambio.

Guía de aprendizaje

Objetivo: Justificar recoloreos y rotaciones con padre, abuelo y tío.

Estrategia: Insertar como ABB y ejecutar casos de reparación hasta la raíz.

Invariante: Raíz negra, sin rojo-rojo y black-height uniforme.

Memoria C: Los NIL son centinelas negros; el color no sustituye los enlaces.

Complejidad: Búsqueda, inserción y eliminación O(log n).

Errores frecuentes

Evaluar solo el color del nodo.
Usar color sin equivalente textual.

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

rbt_abuelo
rbt_eliminar
rbt_buscar
rbt_inorden
rbt_altura
rbt_validar
rbt_liberar

Operaciones pendientes / restricciones

El TAD no expone el detalle paso a paso de recoloreos/rotaciones.

Estructura del TAD en C

typedef struct nodoRBT {
    int nro;                  
    char rbt_color;               
    struct nodoRBT *padre;   
    struct nodoRBT *izq;      
    struct nodoRBT *der;     
} nodoRBT;

typedef struct nodoRBT *RBT;

Metodos del TAD en C

Codigo C: insertar

Inserta respetando reglas de orden/balance del TAD y actualiza punteros estructurales necesarios.

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

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 Rojo-Negro (con rebalanceo).
 * @param arbol Referencia a la raíz del árbol.
 * @param key Clave a eliminar.
 */
void rbt_eliminar(RBT *arbol, int key) {
    RBT z = *arbol;
    while (z != NULL && z->nro != key) {
        if (key < z->nro) z = z->izq; else z = z->der;
    }
    if (z == NULL) return; /* no encontrado */

    RBT y = z;
    char y_color_original = y->rbt_color;
    RBT x = NULL;
    RBT x_parent = NULL;

    if (z->izq == NULL) {
        x = z->der;
        x_parent = z->padre;
        transplantar(arbol, z, z->der);
    } else if (z->der == NULL) {
        x = z->izq;
        x_parent = z->padre;
        transplantar(arbol, z, z->izq);
    } else {
        y = minimo(z->der);
        y_color_original = y->rbt_color;
        x = y->der;
        if (y->padre == z) {
            x_parent = y;
        } else {
            transplantar(arbol, y, y->der);
            x_parent = y->padre;
            y->der = z->der;
            y->der->padre = y;
        }
        transplantar(arbol, z, y);
        y->izq = z->izq;
        y->izq->padre = y;
        y->rbt_color = z->rbt_color;
    }

    free(z);

    if (y_color_original == NEGRO) {
        arreglarEliminacion(arbol, x, x_parent);
    }
    if (*arbol) (*arbol)->rbt_color = NEGRO;
}

Codigo C: buscar

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

/**
 * @brief Busca un valor en el árbol Rojo-Negro.
 * @param nodoRBT Raíz del árbol.
 * @param dato Valor a rbt_buscar.
 * @return Puntero al nodo encontrado o NULL si no existe.
 */
RBT rbt_buscar(RBT nodoRBT, int dato) {
    RBT actual = nodoRBT;
    if (nodoRBT == NULL) {
        printf("\n\tEl arbol esta vacio\n\n");
        return NULL;
    }
    while (actual != NULL) {
        if (dato == actual->nro) {
            printf("\n\tEl numero %d existe en el arbol\n", dato);
            return actual;
        } else if (dato < actual->nro)
            actual = actual->izq;
        else if (dato > actual->nro)
            actual = actual->der;
    }
    printf("\n\tEl numero %d NO existe en el arbol\n", dato);
    return NULL;
}

Codigo C: inorden

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

void rbt_inorden(RBT nodo) {
    if (nodo == NULL) {
        return;
    }
    rbt_inorden(nodo->rbt_izq);
    printf("%d ", nodo->rbt_dato);
    rbt_inorden(nodo->rbt_der);
}

Codigo C: altura

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

int rbt_altura(RBT nodo) {
    if (nodo == NULL) {
        return 0;
    }
    int altIzq = rbt_altura(nodo->rbt_izq);
    int altDer = rbt_altura(nodo->rbt_der);
    return (altIzq > altDer ? altIzq : altDer) + 1;
}

Codigo C: validar

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

int rbt_validar(RBT raiz) {
    if (raiz == NULL) {
        return 1;
    }
    if (raiz->rbt_color == ROJO) {
        if ((raiz->rbt_izq != NULL && raiz->rbt_izq->rbt_color == ROJO) ||
            (raiz->rbt_der != NULL && raiz->rbt_der->rbt_color == ROJO)) {
            return 0;
        }
    }
    if (!rbt_validar(raiz->rbt_izq)) {
        return 0;
    }
    if (!rbt_validar(raiz->rbt_der)) {
        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 Rojo-Negro (postorden).
 * @param arbol Raíz del árbol a liberar.
 */
void rbt_liberar(RBT arbol) {
    if (arbol == NULL)
        return;
    rbt_liberar(arbol->izq);
    rbt_liberar(arbol->der);
    free(arbol);
}

Ir a la visualizacion