Árboles AVL: rotaciones, inserción, eliminación con C++ Ejemplo

¿Qué son los árboles AVL?

Árboles AVL Son árboles de búsqueda binaria en los que la diferencia de altura entre el subárbol izquierdo y el derecho de cada nodo es -1, 0 o +1. Son árboles de búsqueda binaria autoequilibrados que mantienen un tiempo de búsqueda logarítmico, y reciben su nombre de sus inventores, Adelson-Velsky y Landis (AVL).

¿Cómo funciona el árbol AVL?

Para entender por qué existen los árboles AVL, veamos qué falla con un árbol AVL simple. Árbol de búsqueda binariaConsideremos estas claves insertadas en el orden dado:

Visualización del árbol AVL

El árbol crece linealmente cuando las claves llegan en orden ascendente, lo que degrada la búsqueda a O(n). Esto contradice el propósito de un árbol de búsqueda binaria (BST): solo un árbol equilibrado mantiene la búsqueda logarítmica. Ahora veamos las mismas claves insertadas en un orden diferente.

Las mismas claves, pero con un orden de inserción diferente, dan como resultado una estructura menos profunda, por lo que cada búsqueda se ejecuta en O(log n). Los árboles AVL imponen esa estructura al observar la altura en cada inserción y corregir el desequilibrio sin romper el orden del árbol binario de búsqueda.

Factor de equilibrio en árboles AVL

El factor de equilibrio (FE) tracks la altura de cada nodo para que el árbol pueda autoequilibrarse sobre la marcha.

Propiedades del factor de equilibrio

Factor de equilibrio árbol AVL

• El factor de equilibrio es la diferencia entre la altura del subárbol izquierdo y la altura del subárbol derecho.
• Balance factor(node) = height(node->left) − height(node->right)
• Los únicos valores permitidos son −1, 0 y +1.
• Un valor de −1 significa que el subárbol derecho contiene un nivel adicional; el nodo tiene un sesgo hacia la derecha.
• Un valor de +1 significa que el subárbol izquierdo contiene un nivel adicional; el nodo tiene un predominio de nodos izquierdos.
• Un valor de 0 significa que ambos lados tienen la misma altura; el nodo está perfectamente equilibrado.

Rotaciones AVL

Las rotaciones se ejecutan siempre que una inserción o eliminación infrinja la regla del factor de equilibrio. Los cuatro casos son LL, RR, LR y RL.

Izquierda – Rotación izquierda

Esta rotación se realiza cuando se inserta un nuevo nodo en el hijo izquierdo del subárbol izquierdo.

Árbol AVL izquierda – Rotación izquierda

Se realiza una única rotación a la derecha. Este caso se activa cuando un nodo tiene BF +2 y su hijo izquierdo tiene BF +1.

Derecha – Rotación a la derecha

Esta rotación se realiza cuando se inserta un nuevo nodo en el hijo derecho del subárbol derecho.

Se realiza una única rotación a la izquierda. Este caso se activa cuando un nodo tiene BF −2 y su hijo derecho tiene BF −1.

Rotación derecha – izquierda

Esta rotación se realiza cuando se inserta un nuevo nodo en el hijo izquierdo del subárbol derecho.

Se activa cuando BF(nodo) = −2 y BF(hijo derecho) = +1. Gira a la derecha el hijo derecho y luego gira a la izquierda el nodo.

Rotación izquierda – derecha

Esta rotación se realiza cuando se inserta un nuevo nodo en el hijo derecho del subárbol izquierdo.

Se activa cuando BF(nodo) = +2 y BF(hijo izquierdo) = −1. Gira el hijo izquierdo hacia la izquierda y luego gira el nodo hacia la derecha.

Inserción en árboles AVL

La inserción es prácticamente idéntica a una inserción simple en un árbol binario de búsqueda (BST). Después de cada inserción, el árbol se desplaza hacia arriba y se reequilibra. La inserción se ejecuta en un tiempo de O(log n) en el peor de los casos.

Implementación de inserción de árbol AVL

Paso 1: Inserta el nodo usando el algoritmo BST estándar. En el ejemplo anterior, inserta 160.

Paso 2: Actualizar el factor de equilibrio de cada ancestro a lo largo de la ruta de inserción.

Paso 3: Si algún ancestro viola el rango del factor de equilibrio, realice la rotación correspondiente. En el ejemplo, el factor de equilibrio del nodo 350 se ve afectado, por lo que una rotación LL restablece el equilibrio.

1. If BF(node) = +2 y BF(left-child) = +1, realizar rotación LL.
2. If BF(node) = −2 y BF(right-child) = −1, realizar rotación RR.
3. If BF(node) = −2 y BF(right-child) = +1, realizar rotación RL.
4. If BF(node) = +2 y BF(left-child) = −1, realizar rotación izquierda-derecha.

Eliminación en árboles AVL

La eliminación sigue la misma lógica que un árbol binario de búsqueda simple y se reequilibra posteriormente.

Paso 1: Encuentra el elemento en el árbol.

Paso 2: Elimine el nodo utilizando la eliminación estándar de BST.

Paso 3: Son posibles dos casos.

Caso 1: Eliminando del subárbol derecho.

• 1A. If BF(node) = +2 y BF(left-child) = +1, realizar rotación LL.
• 1B. If BF(node) = +2 y BF(left-child) = −1, realizar rotación izquierda-derecha.
• 1C. If BF(node) = +2 y BF(left-child) = 0, realizar rotación LL.

Caso 2: Eliminando del subárbol izquierdo.

• 2A. If BF(node) = −2 y BF(right-child) = −1, realizar rotación RR.
• 2B. If BF(node) = −2 y BF(right-child) = +1, realizar rotación RL.
• 2C. If BF(node) = −2 y BF(right-child) = 0, realizar rotación RR.

C++ Ejemplo de árboles AVL

A continuación se muestra un C++ programa de implementación de árboles AVL:

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct node {
    struct node *left;
    int data;
    int height;
    struct node *right;
};

class AVL {
public:
    struct node *root;

    AVL() {
        this->root = NULL;
    }

    int calheight(struct node *p) {
        if (p->left && p->right) {
            if (p->left->height < p->right->height)
                return p->right->height + 1;
            else
                return p->left->height + 1;
        }
        else if (p->left && p->right == NULL) {
            return p->left->height + 1;
        }
        else if (p->left == NULL && p->right) {
            return p->right->height + 1;
        }
        return 0;
    }

    int bf(struct node *n) {
        if (n->left && n->right)
            return n->left->height - n->right->height;
        else if (n->left && n->right == NULL)
            return n->left->height;
        else if (n->left == NULL && n->right)
            return -n->right->height;
        return 0;
    }

    struct node *llrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        p->left = tp->right;
        tp->right = p;
        return tp;
    }

    struct node *rrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        p->right = tp->left;
        tp->left = p;
        return tp;
    }

    struct node *rlrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        struct node *tp2 = p->right->left;
        p->right = tp2->left;
        tp->left = tp2->right;
        tp2->left = p;
        tp2->right = tp;
        return tp2;
    }

    struct node *lrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        struct node *tp2 = p->left->right;
        p->left = tp2->right;
        tp->right = tp2->left;
        tp2->right = p;
        tp2->left = tp;
        return tp2;
    }

    struct node *insert(struct node *r, int data) {
        if (r == NULL) {
            r = new struct node;
            r->data = data;
            r->left = r->right = NULL;
            r->height = 1;
            return r;
        }
        if (data < r->data)
            r->left = insert(r->left, data);
        else
            r->right = insert(r->right, data);

        r->height = calheight(r);

        if (bf(r) == 2 && bf(r->left) == 1)       r = llrotation(r);
        else if (bf(r) == -2 && bf(r->right) == -1) r = rrrotation(r);
        else if (bf(r) == -2 && bf(r->right) == 1)  r = rlrotation(r);
        else if (bf(r) == 2 && bf(r->left) == -1)   r = lrrotation(r);

        return r;
    }

    void levelorder_newline() {
        if (this->root == NULL) {
            cout << "\nEmpty tree\n";
            return;
        }
        levelorder_newline(this->root);
    }

    void levelorder_newline(struct node *v) {
        queue<struct node *> q;
        struct node *cur;
        q.push(v);
        q.push(NULL);
        while (!q.empty()) {
            cur = q.front();
            q.pop();
            if (cur == NULL && q.size() != 0) {
                cout << "\n";
                q.push(NULL);
                continue;
            }
            if (cur != NULL) {
                cout << " " << cur->data;
                if (cur->left != NULL)  q.push(cur->left);
                if (cur->right != NULL) q.push(cur->right);
            }
        }
    }

    struct node *deleteNode(struct node *p, int data) {
        if (p->left == NULL && p->right == NULL) {
            if (p == this->root) this->root = NULL;
            delete p;
            return NULL;
        }
        struct node *q;
        if (p->data < data)      p->right = deleteNode(p->right, data);
        else if (p->data > data) p->left  = deleteNode(p->left, data);
        else {
            if (p->left != NULL) {
                q = inpre(p->left);
                p->data = q->data;
                p->left = deleteNode(p->left, q->data);
            } else {
                q = insuc(p->right);
                p->data = q->data;
                p->right = deleteNode(p->right, q->data);
            }
        }

        if (bf(p) == 2 && bf(p->left) == 1)         p = llrotation(p);
        else if (bf(p) == 2 && bf(p->left) == -1)    p = lrrotation(p);
        else if (bf(p) == 2 && bf(p->left) == 0)     p = llrotation(p);
        else if (bf(p) == -2 && bf(p->right) == -1)  p = rrrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 1)   p = rlrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 0)   p = rrrotation(p);

        return p;
    }

    struct node *inpre(struct node *p) {
        while (p->right != NULL) p = p->right;
        return p;
    }

    struct node *insuc(struct node *p) {
        while (p->left != NULL) p = p->left;
        return p;
    }

    ~AVL() {}
};

int main() {
    AVL b;
    int c, x;
    do {
        cout << "\n1.Display levelorder on newline";
        cout << "\n2.Insert";
        cout << "\n3.Delete\n";
        cout << "\n0.Exit\n";
        cout << "\nChoice: ";
        cin >> c;
        switch (c) {
        case 1: b.levelorder_newline(); break;
        case 2:
            cout << "\nEnter no. "; cin >> x;
            b.root = b.insert(b.root, x);
            break;
        case 3:
            cout << "\nWhat to delete? "; cin >> x;
            b.root = b.deleteNode(b.root, x);
            break;
        case 0: break;
        }
    } while (c != 0);
}

Ejemplo de ejecución del código anterior:

1. Copia el código anterior y guárdalo en un archivo llamado avl.cpp.
2. Compilar el código:

g++ avl.cpp -o run

3. Ejecute el código.

./run

Ventajas de los árboles AVL

• La altura del árbol AVL siempre está equilibrada y nunca crece más allá del tronco N.
• La búsqueda es más rápida que un árbol de búsqueda binaria simple porque el árbol no puede degenerar.
• El autoequilibrio es automático; no se requiere ningún paso de reconstrucción.
• El rendimiento determinista es adecuado para sistemas en tiempo real e índices en memoria.

Preguntas Frecuentes