Árbol AVL

silexcorp's picture

Árbol AVL

      El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Georgii Adelson-Velskii y Yevgeniy Landis.

      La característica principal de los árboles AVL es que siempre están equilibrados, es decir que la rama de la izquierda no difiere de más de 1 de la altura de la rama derecha.

Rotaciones:

      Siempre se aplican después de una inserción, y pueden ser simples o dobles. Donde: izq = izquierda, der = derecha, fe = factor de equilibrio y n el nodo.

Izquierda Izquierda - II

n -> izq = n1->der

n1->der= n

n = n1

Condiciones antes de la última operación:

Si n1->fe = -1;

n->fe = 0

n1->fe = -1

Si no;

n->fe = -1

n1->fe = 1

Derecha Derecha - DD

n -> der= n1->izq

n1->izq = n

n = n1

Condiciones antes de la última operación:

Si n1->fe = -1;

n->fe = 0

n1->fe = -1

Si no;

n->fe = -1

n1->fe = 1

Izquierda Derecha - ID

n1->der = n2->izq

n2->izq = n1

n->izq = n2->der

n2->der = n

n = n2

Condiciones antes de la última operación:

Si n2->fe = -1;

n->fe = 1

n1->fe = 0

n2->fe = 0

Si n2->fe = 0;

n->fe = 0

n1->fe = 0

n2->fe = 0

Si n2->fe = 1;

n->fe = 0

n1->fe = -1

n2->fe = 0

Derecha Izquierda - DI

n1->izq= n2->der

n2->der= n1

n->der= n2->izq

n2->izq = n

n = n2

Condiciones antes de la última operación:

Si n2->fe = -1;

n->fe = 0

n1->fe = 1

n2->fe = 0

Si n2->fe = 0;

n->fe = 0

n1->fe = 0

n2->fe = 0

Si n2->fe = 1;

n->fe = -1

n1->fe = 0

n2->fe = 0

 

Ejemplo:

#ifndef S_ARBOL_AVL_H
#define S_ARBOL_AVL_H

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

/* ARBOL AVL DE USUARIOS */

struct DATOAVL{
    int   user_id;
    char *user_pass;
    char *user_name;
    char *user_last_name;
};

struct NODOAVL{
    DATOAVL dato_avl;
    struct NODOAVL *izq;
    struct NODOAVL *der;
    int fe;
};

struct ARBOLAVL{
    NODOAVL *raiz;
};

typedef NODOAVL *ARBOLAVL;

extern void insertar_en_avl(ARBOLAVL *raiz, DATOAVL dato);
extern void eliminar_avl(ARBOLAVL *raiz, DATOAVL dato);
extern void rotacion_simple(ARBOLAVL *raiz, bool estado);
extern void rotacion_doble(ARBOLAVL *raiz, bool estado);
extern void balancear (ARBOLAVL *raiz);
extern void cambiar_avl(ARBOLAVL *raiz);
extern void factor(ARBOLAVL raiz);
extern void in_orden(ARBOLAVL raiz);
extern bool buscar_nodo_avl(ARBOLAVL *raiz, DATOAVL dato);
extern NODOAVL *buscar_nodo_avl_(ARBOLAVL *raiz, DATOAVL dato);
static bool estado;

#endif // S_ARBOL_AVL_H

 

#include "s_arbol_avl.h"

/*
 * Estados del arbol */
    void set_estado(bool b){estado = b;}
    bool get_estado(){ return estado;}

    /*
     * Crear NODO de avl */
    NODOAVL *crear_nodo_arbol_avl(DATOAVL dato){
        NODOAVL *nuevo = new NODOAVL;
        nuevo->dato_avl = dato;
        nuevo->izq = NULL;
        nuevo->der = NULL;
        nuevo->fe = 0;
        return nuevo;
    }

    /*
     * Insertar en avl */
    void insertar_en_avl(ARBOLAVL *raiz, DATOAVL dato){
         if ((*raiz) == NULL) {
            (*raiz) = crear_nodo_arbol_avl(dato);
         }else if(dato.user_id > (*raiz)->dato_avl.user_id){
                insertar_en_avl(&((*raiz)->izq), dato);
         }else if(dato.user_id < (*raiz)->dato_avl.user_id){
                insertar_en_avl(&((*raiz)->der), dato);
         }balancear(raiz);

    }

    /*
     * Cambiar avl */
    void cambiar_avl(ARBOLAVL *raiz){
        NODOAVL *aux, *temporal;
        temporal = *raiz;
        aux = (*raiz)->izq;
        while(aux->der){
            temporal = aux;
            aux = aux->der;
        }
        (*raiz)->dato_avl = aux->dato_avl;
        if(temporal == (*raiz)){
            temporal->izq = aux->izq;
        }else{
            temporal->der = aux->izq;
        }(*raiz) = aux;
    }

    /*
     * Hallar altura */
    int altura(ARBOLAVL raiz){
        int AI, AD;
        if(raiz==NULL)
            return 0;
        else{
            AI = altura(raiz->izq);
            AD = altura(raiz->der);
            if(AI>AD){return AI+1;
            }else{return AD+1;
            }
        }
    }

    /*
     * Buscar el factor de equilibro */
    void factor(ARBOLAVL raiz){
        if (raiz != NULL) {
           factor(raiz->izq);
           int alt_izq,alt_der,fe;

           alt_izq = altura(raiz->izq);
           alt_der = altura(raiz->der);
           fe = alt_der - alt_izq;

           raiz->fe = fe;
           factor(raiz->der);
        }
    }

    /*
     * Rotaciones simples II DD */
    void rotacion_simple(ARBOLAVL *raiz, bool izq){
        ARBOLAVL temporal;
         if (izq){
             temporal = (*raiz)->izq;
             (*raiz)->izq = temporal->der;
             temporal->der = *raiz;
         }else{
             temporal = (*raiz)->der;
             (*raiz)->der = temporal->izq;
             temporal->izq = *raiz;
         }*raiz = temporal;
    }

    /*
     * Rotaciones dobles ID DI */
    void rotacion_doble(ARBOLAVL *raiz, bool izq){
        if (izq){
            rotacion_simple(&(*raiz)->izq, false);
            rotacion_simple(raiz, true);
        }else{
            rotacion_simple(&(*raiz)->der, true);
            rotacion_simple(raiz, false);
        }
     }

    /*
     * Balancear avl */
    void balancear (ARBOLAVL *raiz){
      if((*raiz)!=NULL){
        if (altura((*raiz)->izq) - altura((*raiz)->der) == 2){
            if (altura ((*raiz)->izq->izq) >= altura ((*raiz)->izq->der)){
                rotacion_simple(raiz, true);
            }else{
                rotacion_doble(raiz, true);}
          }else if (altura((*raiz)->der) - altura((*raiz)->izq) == 2){
            if (altura ((*raiz)->der->der) >= altura ((*raiz)->der->izq)){
                rotacion_simple(raiz, false);
            }else{
                rotacion_doble(raiz, false);}
          }
      }
    }

    /*
     * Buscar nodo en avl */
    bool buscar_nodo_avl(ARBOLAVL *raiz, DATOAVL dato){
        bool eleccion = false;
        if((*raiz) != NULL){
            if(dato.user_id < (*raiz)->dato_avl.user_id){
                eleccion = buscar_nodo_avl(&((*raiz)->izq),dato);
            }else if(dato.user_id > (*raiz)->dato_avl.user_id){
                eleccion = buscar_nodo_avl(&((*raiz)->der), dato);
            }else{ return true; }
        }else{ return eleccion; }
    }

    /*
     * Buscar nodo en avl_ retorna NODO */
    NODOAVL *buscar_nodo_avl_(ARBOLAVL *raiz, DATOAVL dato){
        if((*raiz) != NULL){
            //printf(" hmmm busco: %d y hallo: %d\n",dato.user_id, (*raiz)->dato_avl.user_id);
            if(dato.user_id == (*raiz)->dato_avl.user_id){
                return (*raiz);
            }else if(dato.user_id > (*raiz)->dato_avl.user_id){
                buscar_nodo_avl_(&((*raiz)->izq),dato);
            }else if(dato.user_id < (*raiz)->dato_avl.user_id){
                buscar_nodo_avl_(&((*raiz)->der), dato);
            }
        }
    }

 

    /*
     * Eliminar en avl */
    void eliminar_avl(ARBOLAVL *raiz, DATOAVL dato){
        if((*raiz)){
            if(dato.user_id < (*raiz)->dato_avl.user_id){
                eliminar_avl(&((*raiz)->izq), dato);
            }else if(dato.user_id > (*raiz)->dato_avl.user_id){
                eliminar_avl(&((*raiz)->der), dato);
            }else{
                NODOAVL *aux;aux = (*raiz);
                if(aux->izq == NULL){
                    (*raiz) = aux->der;
                }else if(aux->der == NULL){
                    (*raiz) = aux->izq;
                }else{
                    cambiar_avl(&aux);
                }
                delete(aux);balancear(raiz);
            }
        }
    }

    /*
     * Mostrar datos inorden */
    void in_orden(ARBOLAVL raiz){
        if(raiz != NULL){
            in_orden(raiz->izq);
                printf("DATO: %d\n", raiz->dato_avl.user_id);
            in_orden(raiz->der);
        }
    }

 

by Alexander

 

Comments