Implementación de Árbol Binario AVL en C++: Clases y Métodos

Árbol Binario AVL: Definición de Clases

Clase Nodo (Nodo)

template<class DATO>
class AVL;

// Clase Nodo de Árbol AVL:
template<class DATO>
class Nodo {
public:
    // Constructor:
    Nodo(const DATO dat, Nodo<DATO> *pad = NULL,
         Nodo<DATO> *izq = NULL, Nodo<DATO> *der = NULL) :
        dato(dat), padre(pad), izquierdo(izq), derecho(der), FE(0) {}

    // Miembros:
    DATO dato;
    int FE; // Factor de Equilibrio
    Nodo<DATO> *izquierdo;
    Nodo<DATO> *derecho;
    Nodo<DATO> *padre;

    friend class AVL<DATO>;
};

Clase Árbol AVL (AVL)

template<class DATO>
class AVL {
private:
    enum { IZQUIERDO, DERECHO };

    // Punteros del árbol:
    Nodo<DATO> *raiz;
    Nodo<DATO> *actual;
    int contador;
    int altura;

public:
    // Constructor y destructor básicos:
    AVL() : raiz(NULL), actual(NULL), contador(0), altura(0) {}
    ~AVL() { Podar(raiz); }

    // --- Operaciones Principales ---
    // Insertar en árbol ordenado:
    void Insertar(const DATO dat);
    // Borrar un elemento del árbol:
    void Borrar(const DATO dat);
    // Función de búsqueda:
    bool Buscar(const DATO dat);

    // --- Comprobaciones --- 
    // Comprobar si el árbol está vacío:
    bool Vacio(Nodo<DATO> *r) { return r == NULL; }
    // Comprobar si es un nodo hoja:
    bool EsHoja(Nodo<DATO> *r) { return !r->derecho && !r->izquierdo; }

    // --- Métodos de Acceso e Información ---
    // Contar número de nodos:
    const int NumeroNodos();
    const int AlturaArbol();
    // Calcular altura de un dato:
    int Altura(const DATO dat);
    // Devolver referencia al dato del nodo actual:
    DATO &ValorActual() { return actual->dato; }
    // Moverse al nodo raíz:
    void Raiz() { actual = raiz; }

    // --- Recorridos --- 
    // Aplicar una función a cada elemento del árbol:
    void InOrden(void (*func)(DATO&, int), Nodo<DATO> *nodo = NULL, bool r = true);
    void PreOrden(void (*func)(DATO&, int), Nodo<DATO> *nodo = NULL, bool r = true);
    void PostOrden(void (*func)(DATO&, int), Nodo<DATO> *nodo = NULL, bool r = true);

private:
    // --- Funciones de Equilibrado --- 
    void Equilibrar(Nodo<DATO> *nodo, int rama, bool nuevo);
    void RSI(Nodo<DATO>* nodo); // Rotación Simple Izquierda
    void RSD(Nodo<DATO>* nodo); // Rotación Simple Derecha
    void RDI(Nodo<DATO>* nodo); // Rotación Doble Izquierda-Derecha
    void RDD(Nodo<DATO>* nodo); // Rotación Doble Derecha-Izquierda

    // --- Funciones Auxiliares ---
    void Podar(Nodo<DATO>* &nodo); // Elimina todos los nodos
    void auxContador(Nodo<DATO>* nodo);
    void auxAltura(Nodo<DATO>* nodo, int a);
};

Árbol Binario AVL: Implementación de Métodos

Método Podar

Elimina todos los nodos del subárbol a partir del nodo proporcionado (incluido él), usando un recorrido en postorden.

template<class DATO>
void AVL<DATO>::Podar(Nodo<DATO>* &nodo)
{
    // Algoritmo recursivo, recorrido en postorden
    if (nodo) {
        Podar(nodo->izquierdo); // Podar subárbol izquierdo
        Podar(nodo->derecho);   // Podar subárbol derecho
        delete nodo;            // Eliminar nodo actual
        nodo = NULL;
    }
}

Método Insertar

Inserta un dato en el árbol AVL, manteniendo la propiedad de árbol binario de búsqueda y realizando el equilibrado si es necesario.

template<class DATO>
void AVL<DATO>::Insertar(const DATO dat)
{
    Nodo<DATO> *padre = NULL;

    // std::cout << "Insertar: " << dat << std::endl; // Descomentar para depuración

    actual = raiz;
    // Buscar la posición de inserción
    while (!Vacio(actual) && dat != actual->dato) {
        padre = actual;
        if (dat > actual->dato) {
            actual = actual->derecho;
        } else if (dat < actual->dato) {
            actual = actual->izquierdo;
        }
    }

    // Si el dato ya existe, no se inserta
    if (!Vacio(actual)) return;

    // Insertar el nuevo nodo
    if (Vacio(padre)) { // El árbol estaba vacío
        raiz = new Nodo<DATO>(dat);
    } else if (dat < padre->dato) {
        padre->izquierdo = new Nodo<DATO>(dat, padre);
        Equilibrar(padre, IZQUIERDO, true);
    } else if (dat > padre->dato) {
        padre->derecho = new Nodo<DATO>(dat, padre);
        Equilibrar(padre, DERECHO, true);
    }
}

Método Equilibrar

Revisa y ajusta los factores de equilibrio (FE) hacia la raíz desde el nodo insertado/borrado, aplicando las rotaciones necesarias (RSI, RSD, RDI, RDD) para mantener el árbol AVL balanceado.

template<class DATO>
void AVL<DATO>::Equilibrar(Nodo<DATO> *nodo, int rama, bool nuevo)
{
    bool salir = false;

    // Recorrer el camino hacia la raíz desde el padre del nodo insertado/borrado
    while (nodo && !salir) {
        // Ajustar FE según la operación (inserción o borrado)
        if (nuevo) { // Inserción
            if (rama == IZQUIERDO) nodo->FE--;
            else nodo->FE++;
        } else { // Borrado
            if (rama == IZQUIERDO) nodo->FE++;
            else nodo->FE--;
        }

        // Evaluar el FE del nodo actual
        if (nodo->FE == 0) { // El árbol se ha equilibrado en este punto
            salir = true;
        } else if (nodo->FE == -2) { // Desequilibrio hacia la izquierda
            if (nodo->izquierdo->FE == 1) RDD(nodo); // Rotación Doble Derecha-Izquierda
            else RSD(nodo); // Rotación Simple Derecha
            salir = true; // Después de una rotación, el subárbol queda equilibrado
        } else if (nodo->FE == 2) { // Desequilibrio hacia la derecha
            if (nodo->derecho->FE == -1) RDI(nodo); // Rotación Doble Izquierda-Derecha
            else RSI(nodo); // Rotación Simple Izquierda
            salir = true; // Después de una rotación, el subárbol queda equilibrado
        }

        // Subir al padre para continuar el proceso si no se ha salido
        if (nodo->padre) {
            // Determinar por qué rama se sube (izquierda o derecha del padre)
            if (nodo->padre->derecho == nodo) rama = DERECHO;
            else rama = IZQUIERDO;
        }
        nodo = nodo->padre; // Moverse al siguiente nodo en el camino hacia la raíz
    }
}