Implementación de Rotaciones en Árboles AVL: Código C++ Detallado

Implementación de Rotaciones en Árboles AVL con C++

Los árboles AVL son un tipo de árbol binario de búsqueda auto-balanceable. Para mantener su propiedad de balanceo, utilizan rotaciones cuando las inserciones o eliminaciones provocan un desequilibrio. El equilibrio se mide mediante el Factor de Equilibrio (FE) de cada nodo. A continuación, se detalla la implementación en C++ de las cuatro rotaciones fundamentales: simples y dobles.

Rotaciones Dobles

Las rotaciones dobles se aplican cuando el desequilibrio se produce en la subrama "interior" del subárbol. Son esencialmente una combinación de dos rotaciones simples.

Rotación Doble a Derechas (RDD)

Esta rotación se aplica cuando un nodo está desequilibrado hacia la izquierda (FE = -2) y su hijo izquierdo tiene un desequilibrio hacia la derecha (FE = 1).

// Rotación doble a derechas
template<class DATO>
void AVL<DATO>::RDD(Nodo<DATO>* nodo)
{
    cout << "RDD" << endl;
    Nodo<DATO> *Padre = nodo->padre;
    Nodo<DATO> *P = nodo;
    Nodo<DATO> *Q = P->izquierdo;
    Nodo<DATO> *R = Q->derecho;
    Nodo<DATO> *B = R->izquierdo;
    Nodo<DATO> *C = R->derecho;

    if(Padre)
        if(Padre->derecho == nodo) Padre->derecho = R;
        else Padre->izquierdo = R;
    else raiz = R;

    // Reconstruir árbol:
    Q->derecho = B;
    P->izquierdo = C;
    R->izquierdo = Q;
    R->derecho = P;

    // Reasignar padres:
    R->padre = Padre;
    P->padre = Q->padre = R;
    if(B) B->padre = Q;
    if(C) C->padre = P;

    // Ajustar valores de FE:
    switch(R->FE) {
        case -1: Q->FE = 0; P->FE = 1; break;
        case 0:  Q->FE = 0; P->FE = 0; break;
        case 1:  Q->FE = -1; P->FE = 0; break;
    }
    R->FE = 0;
}

Rotación Doble a Izquierdas (RDI)

Se aplica cuando un nodo está desequilibrado hacia la derecha (FE = 2) y su hijo derecho tiene un desequilibrio hacia la izquierda (FE = -1).

// Rotación doble a izquierdas
template<class DATO>
void AVL<DATO>::RDI(Nodo<DATO>* nodo)
{
    cout << "RDI" << endl;
    Nodo<DATO> *Padre = nodo->padre;
    Nodo<DATO> *P = nodo;
    Nodo<DATO> *Q = P->derecho;
    Nodo<DATO> *R = Q->izquierdo;
    Nodo<DATO> *B = R->izquierdo;
    Nodo<DATO> *C = R->derecho;

    if(Padre)
        if(Padre->derecho == nodo) Padre->derecho = R;
        else Padre->izquierdo = R;
    else raiz = R;

    // Reconstruir árbol:
    P->derecho = B;
    Q->izquierdo = C;
    R->izquierdo = P;
    R->derecho = Q;

    // Reasignar padres:
    R->padre = Padre;
    P->padre = Q->padre = R;
    if(B) B->padre = P;
    if(C) C->padre = Q;

    // Ajustar valores de FE:
    switch(R->FE) {
        case -1: P->FE = 0; Q->FE = 1; break;
        case 0:  P->FE = 0; Q->FE = 0; break;
        case 1:  P->FE = -1; Q->FE = 0; break;
    }
    R->FE = 0;
}

Rotaciones Simples

Las rotaciones simples se utilizan cuando el desequilibrio se produce en la subrama "exterior" del subárbol.

Rotación Simple a Derechas (RSD)

Se realiza cuando un nodo está desequilibrado hacia la izquierda (FE = -2) y su hijo izquierdo también tiene un desequilibrio hacia la izquierda (FE = -1).

// Rotación simple a derechas
template<class DATO>
void AVL<DATO>::RSD(Nodo<DATO>* nodo)
{
    cout << "RSD" << endl;
    Nodo<DATO> *Padre = nodo->padre;
    Nodo<DATO> *P = nodo;
    Nodo<DATO> *Q = P->izquierdo;
    Nodo<DATO> *B = Q->derecho;

    if(Padre)
        if(Padre->derecho == P) Padre->derecho = Q;
        else Padre->izquierdo = Q;
    else raiz = Q;

    // Reconstruir árbol:
    P->izquierdo = B;
    Q->derecho = P;

    // Reasignar padres:
    P->padre = Q;
    if(B) B->padre = P;
    Q->padre = Padre;

    // Ajustar valores de FE:
    P->FE = 0;
    Q->FE = 0;
}

Rotación Simple a Izquierdas (RSI)

Se efectúa cuando un nodo está desequilibrado hacia la derecha (FE = 2) y su hijo derecho también presenta un desequilibrio hacia la derecha (FE = 1).

// Rotación simple a izquierdas
template<class DATO>
void AVL<DATO>::RSI(Nodo<DATO>* nodo)
{
    cout << "RSI" << endl;
    Nodo<DATO> *Padre = nodo->padre;
    Nodo<DATO> *P = nodo;
    Nodo<DATO> *Q = P->derecho;
    Nodo<DATO> *B = Q->izquierdo;

    if(Padre)
        if(Padre->derecho == P) Padre->derecho = Q;
        else Padre->izquierdo = Q;
    else raiz = Q;

    // Reconstruir árbol:
    P->derecho = B;
    Q->izquierdo = P;

    // Reasignar padres:
    P->padre = Q;
    if(B) B->padre = P;
    Q->padre = Padre;

    // Ajustar valores de FE:
    P->FE = 0;
    Q->FE = 0;
}