Los árboles de búsqueda binaria permiten un acceso rápido a datos ordenados, pero pueden degenerar en estructuras lineales. Los árboles AVL ofrecen balance estricto con costo operacional alto. Los árboles rojo-negro equilibran eficiencia y simplicidad mediante invariantes de color.

Un árbol rojo-negro garantiza:

• La raíz es negra.
• Los nodos hoja (NIL) son negros.
• Los hijos de un nodo rojo son negros.
• Cualquier camino desde un nodo hasta sus hojas contiene la misma cantidad de nodos negros.

Esta estructura asegura que la longitud máxima no exceda el doble de la mínima, manteniendo operaciones en O(log n).

Estructura de nodos

Definimos un enum para colores y un nodo genérico:

enum TColor { RED, BLACK };

template <typename K, typename V>
struct RBNode {
    K clave;
    V valor;
    TColor color;
    RBNode *izq, *der, *padre;
    RBNode(K k, V v, TColor c = RED)
        : clave(k), valor(v), color(c), izq(nullptr), der(nullptr), padre(nullptr) {}
};

Clase principle del árbol

La clase RBTree gestiona nodos y un centinela NIL:

template <typename K, typename V>
class RBTree {
private:
    RBNode<K, V>* raiz;
    RBNode<K, V>* nil;

public:
    RBTree() {
        nil = new RBNode<K, V>(K(), V(), BLACK);
        nil->izq = nil->der = nil->padre = nil;
        raiz = nil;
    }
    // ... métodos
};

Rtoaciones

Rotación izquierda eleva el hijo derecho:

void rotarIzquierda(RBNode<K, V>* x) {
    RBNode<K, V>* y = x->der;
    x->der = y->izq;
    if (y->izq != nil) y->izq->padre = x;
    y->padre = x->padre;
    if (x->padre == nil) raiz = y;
    else if (x == x->padre->izq) x->padre->izq = y;
    else x->padre->der = y;
    y->izq = x;
    x->padre = y;
}

Rotación derecha es análoga, intercambiando izquierda y derecha.

Inserción

Insertar un nuevo nodo rojo y ajustar propiedades:

void insertar(const K& clave, const V& valor) {
    RBNode<K, V>* actual = raiz;
    RBNode<K, V>* padre = nil;

    while (actual != nil) {
        padre = actual;
        if (clave == actual->clave) {
            actual->valor = valor;
            return;
        }
        actual = (clave < actual->clave) ? actual->izq : actual->der;
    }

    RBNode<K, V>* nuevo = new RBNode<K, V>(clave, valor);
    nuevo->padre = padre;
    nuevo->izq = nuevo->der = nil;

    if (padre == nil) raiz = nuevo;
    else if (clave < padre->clave) padre->izq = nuevo;
    else padre->der = nuevo;

    ajustarInsercion(nuevo);
}

La función de ajuste repara violaciones mediante recoloración y rotaciones.

Búsqueda

Buscar una clave retorna un puntero al valor o nullptr:

V* buscar(const K& clave) const {
    RBNode<K, V>* nodo = raiz;
    while (nodo != nil) {
        if (clave == nodo->clave) return &nodo->valor;
        nodo = (clave < nodo->clave) ? nodo->izq : nodo->der;
    }
    return nullptr;
}

El operador [] permite acceso directo, insertando un valor por defecto si no existe.

Eliminación

Eliminar un nodo y mantener balance:

void eliminar(const K& clave) {
    RBNode<K, V>* objetivo = raiz;
    while (objetivo != nil) {
        if (clave == objetivo->clave) break;
        objetivo = (clave < objetivo->clave) ? objetivo->izq : objetivo->der;
    }
    if (objetivo == nil) return;

    RBNode<K, V>* reemplazo = objetivo;
    TColor colorOriginal = reemplazo->color;
    RBNode<K, V>* hijo;

    if (objetivo->izq == nil) {
        hijo = objetivo->der;
        trasplantar(objetivo, objetivo->der);
    } else if (objetivo->der == nil) {
        hijo = objetivo->izq;
        trasplantar(objetivo, objetivo->izq);
    } else {
        reemplazo = minimo(objetivo->der);
        colorOriginal = reemplazo->color;
        hijo = reemplazo->der;

        if (reemplazo->padre == objetivo) hijo->padre = reemplazo;
        else {
            trasplantar(reemplazo, reemplazo->der);
            reemplazo->der = objetivo->der;
            reemplazo->der->padre = reemplazo;
        }
        trasplantar(objetivo, reemplazo);
        reemplazo->izq = objetivo->izq;
        reemplazo->izq->padre = reemplazo;
        reemplazo->color = objetivo->color;
    }
    delete objetivo;
    if (colorOriginal == BLACK) ajustarEliminacion(hijo);
}

La reparación post-eliminación ajusta colores y rotaciones para preservar invariantes.

Funciones auxiliares

Incluyen trasplante de subárboles, búsqueda del mínimo y gestión de memoria. La copia profunda garantiza independencia entre instancias.

Complejidad operativa

Insertar, eliminar y buscar mantienen O(log n) en el peor caso, con rotaciones limitadas.