Saltar al contenido

Rotar, insertar, eliminar con el ejemplo C ++

¿Qué son los árboles AVL?

Árboles AVL son árboles de búsqueda binarios en los que la diferencia entre la altura del subtítulo izquierdo y derecho es -1, 0 o +1.

Los árboles AVL también se denominan árbol de búsqueda binaria autoequilibrado. Estos árboles ayudan a mantener el tiempo de búsqueda logarítmica. Lleva el nombre de sus inventores (AVL) Adelson, Velsky y Landis.

En este tutorial de algoritmos, aprenderá:

¿Cómo funciona AVL Tree?

Para comprender mejor la necesidad de árboles AVL, veamos algunas desventajas de los árboles de búsqueda binarios simples.

Considere las siguientes claves ingresadas en el orden dado en el árbol de búsqueda binaria.

Visualización de árbol AVL

La altura del árbol crece linealmente en tamaño a medida que colocamos las claves en orden creciente de su valor. Entonces O (n) toma la operación de búsqueda, en el peor de los casos.

Se necesita un tiempo lineal para buscar un elemento; por lo que no se utiliza la estructura de árbol de búsqueda binaria. Por otro lado, si la altura del árbol está equilibrada, obtenemos un mejor tiempo de búsqueda.

Ahora veamos las mismas claves pero insertadas en un orden diferente.

Aquí, las claves son las mismas, pero como se insertan en un orden diferente, asumen diferentes posiciones y la altura del árbol permanece equilibrada. Entonces, una búsqueda no tomará más de O (log n) en ningún aspecto del árbol. Ahora está claro que, si se inserta correctamente, la altura del árbol se puede mantener equilibrada.

En los mástiles AVL, controlamos la altura del mástil durante la operación. Se realizan modificaciones para mantener la altura equilibrada sin anular las propiedades subyacentes del árbol de búsqueda binaria.

Factor de equilibrio en árboles AVL

El factor de equilibrio (BF) que ayuda a monitorear la altura de los árboles es una característica fundamental de todos los nodos en los árboles AVL.

Propiedades del factor de equilibrio

Árbol de factores de equilibrio AVL

Rotación AVL

Para hacer el balance del árbol AVL en sí, cuando se inserta o elimina un nodo del árbol, se realiza la rotación.

Realizamos la siguiente rotación LL, rotación RR, rotación CD y rotación RL.

Izquierda – Rotación izquierda

Esta rotación se realiza cuando el hijo izquierdo del título izquierdo inserta un nuevo nodo.

Árbol AVL a la izquierda – Girar a la izquierda

Se realiza una rotación a la derecha. Este tipo de rotación se reconoce cuando un nodo tiene un factor de equilibrio como +2 y su hijo izquierdo tiene un factor de equilibrio como +1.

Derecha – Girar a la derecha

Esta rotación se realiza cuando el hijo correcto del subtítulo correcto inserta un nuevo nodo.

Se hace una rotación hacia la izquierda. Este tipo de rotación se reconoce cuando un nodo tiene un factor de equilibrio como -2, y su hijo correcto tiene un factor de equilibrio de -1.

Derecha – Girar a la izquierda

Esta rotación se realiza cuando el niño inserta un nuevo nodo a la derecha del título izquierdo.

Esta rotación se realiza cuando un nodo tiene un factor de equilibrio como –2, y su hijo tiene un factor de equilibrio a la derecha de +1.

Izquierda – Girar a la derecha

Esta rotación se realiza cuando el niño inserta un nuevo nodo a la derecha del título izquierdo.

Esta rotación se realiza cuando un nodo tiene un factor de equilibrio como +2, y su hijo derecho tiene un factor de equilibrio como -1.

Insertar en árboles AVL

La operación de entrada es casi la misma que la de los árboles de búsqueda binarios simples. Después de cada inserción, equilibraremos la altura del árbol. La operación toma O (log n) la peor complejidad de tiempo.

Implementación de mástiles AVL

Paso 1: Inserte el nodo en el árbol AVL utilizando el mismo algoritmo de inserción de BST. En el ejemplo anterior, ingrese 160.

Paso 2: Cuando se agrega el nodo, se actualiza el factor de balance de cada nodo. Después de ingresar 160, se actualiza el factor de balance de cada nodo.

Paso 3: Ahora verifique si algún nodo excede el rango del factor de balance si se excede el factor de balance, luego rote usando el caso a continuación. En el ejemplo anterior, se excede el factor de equilibrio de 350 y luego se aplica el caso 1, giramos LL y el mástil se equilibra nuevamente.

  1. Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = +1, gire LL.
  2. Si BF (nodo) = -2 y BF (nodo -> niño derecho) = 1, gire RR.
  3. Si BF (nodo) = -2 y BF (nodo -> niño derecho) = +1, gire RL.
  4. Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = -1, gire CD.

Destruido en árboles AVL

La eliminación también es muy sencilla. Eliminamos la misma lógica utilizada en árboles de búsqueda binarios simples. Después de destruirlo, reestructuramos el árbol, si es necesario, para mantener su altura justa.

Paso 1: Encuentra el elemento en el árbol.

Paso 2: Elimine el nodo, de acuerdo con Delete BST.

Paso 3: Se pueden realizar dos casos: –

Caso 1: Eliminando del subtítulo correcto.

Caso 2: Eliminando del título de la izquierda.

Ejemplo de C ++ de árboles AVL

A continuación se muestra el código C ++ que implementa á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
{
private:
    
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;
            }
    }

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

        p->left = tp->right;
        tp->right = p;

        return tp; 
    }


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

        p->right = tp->left;
        tp->left = p;

        return tp; 
    }


    struct node * rlrotation(struct node *n){
        struct node *p;
        struct node *tp;
        struct node *tp2;
        p = n;
        tp = p->right;
        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;
        struct node *tp;
        struct node *tp2;
        p = n;
        tp = p->left;
        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){
            struct node *n;
            n = new struct node;
            n->data = data;
            r = n;
            r->left = r->right = NULL;
            r->height = 1; 
            return r;             
        }
        else{
            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<<"n"<<"Empty 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 *t;
        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 = llrotation(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.Deleten";
        cout<<"n0.Exitn";
        cout<<"nChoice: ";

        cin>>c;

        switch (c)
        {
        case 1:
            b.levelorder_newline();
            // to print the tree in level order
            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 actual del código anterior:

  1. Copie el código anterior y pegue «avl.cpp».
  2. Compila el código:
g++ avl.cpp -o run
  1. Ejecute el código.
./run 

Ventajas de los árboles AVL

Resumen: