Árbol AVL


Árbol AVL

Árbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.

Contenido

Descripción

Un ejemplo de árbol binario no equilibrado (no es AVL)
Un ejemplo de árbol binario equilibrado (si es AVL)

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Adelson-Velskii y Landis. Lo dieron a conocer en la publicación de un artículo en 1962: "An algorithm for the organization of information" ("Un algoritmo para la organización de la información").

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.

Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Los árboles AVL más profundos son los árboles de Fibonacci.

Definición formal

Definición de la altura de un árbol

Sea T un árbol binario de búsqueda y sean Ti y Td sus subárboles, su altura H(T), es:

  • 0 si el árbol T contiene solo la raíz
  • 1 + max(H(Ti),H(Td)) si contiene más nodos

Definición de árbol AVL

  • Un árbol vacío es un árbol AVL
  • Si T es un árbol no vacío y Ti y Td sus subárboles, entonces T es AVL si y solo si:
  • Ti es AVL
  • Td es AVL
  • | H(Ti) − H(Td) | < = 1

Factor de equilibrio

Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los árboles binarios de búsqueda (ABB), y además el dato que controla el factor de equilibrio.

El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:

FE = altura subárbol derecho - altura subárbol izquierdo;
Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.

Si el factor de equilibrio de un nodo es:

0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.
1 -> el nodo está desequilibrado y su subárbol derecho es un nivel más alto.
-1 -> el nodo está desequilibrado y su subárbol izquierdo es un nivel más alto.

Si el factor de equilibrio | Fe | > = 2 es necesario reequilibrar.

Operaciones

Las operaciones básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos que serían realizados en un árbol binario de búsqueda desequilibrado, pero precedido o seguido por una o más de las llamadas "rotaciones AVL".

Rotaciones

El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.


ROTACIÓN SIMPLE A LA DERECHA.

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).

rotación simple a la derecha‎ iniciorotación simple a la derecha final

op rotDer: AVL{X} -> [AVL{X}] .
eq rotDer(arbolBin(R1, arbolBin(R2, I2, D2), D1)) ==
arbolBin(R2, I2, arbolBin(R1, D2, D)) .

ROTACIÓN SIMPLE A LA IZQUIERDA.

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).

Precondición : Tiene que tener hijo derecho no vacío.

rotación a la izquierda iniciorotación a la izquierda final

 op rotIzq: AVL{X} -> [AVL{X}] .
eq rotIzq(arbolBin(R1, I, arbolBin(R2, I2, D2))) ==
arbolBin(R2, arbolBin(R1, I, I2), D2) .


Si la inserción se produce en el hijo derecho del hijo izquierdo del nodo desequilibrado (o viceversa) hay que realizar una doble rotación.

ROTACIÓN DOBLE A LA DERECHA.
La Rotación doble a la Derecha son dos rotaciones simples, primero rotacion simple izquierda y luego rotación simple derecha.

rotación a la izquierda iniciorotación a la izquierda final

ROTACIÓN DOBLE A LA IZQUIERDA.
La Rotación doble a la Izquierda son dos rotaciones simples, primero rotacion simple derecha y luego rotación simple izquierda.

rotación a la izquierda iniciorotación a la izquierda final

Inserción

La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.

Proceso de inserción:

1.buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda)
2.insertar el nuevo nodo con factor de equilibrio “equilibrado”
3.desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario


Insercion1.jpg Insercion2.jpg Insercion3-1.jpg Insercion3-2.jpg Insercion4-1.jpg Insercion4-2.jpg

Debido a que las rotaciones son una operación que tienen complejidad constante y a que la altura esta limitada a O (log(n)), el tiempo de ejecución para la inserción es del orden O (log(n)).

op insertar: X$Elt AVL{X} -> AVLNV{X} .
eq insertar(R, crear) == arbolBin(R, crear, crear) .
        ceq insertar(R1, arbolBin(R2, I, D)) ==
if (R1==R2) then
                        arbolBin(R2, I, D)
                elseif (R1<R2) then
                        if ( (altura(insertar(R1,I)) – altura(D)) < 2) then
                                arbolBin(R2, insertar(R1, I), D)
                        else ***hay que reequilibrar
                                if (R1 < raiz(I)) then
                                        rotarDer(arbolBin(R2, insertar(R1, I), D))
                                else
                                        rotarDer(arbolBin(R2, rotarIzq(insertar(R1, I)), D))
                                fi .
                        fi .
                else
                        if ( (altura(insertar(R1,I)) – altura(D)) < 2) then
                                arbolBin(R2, insertar(R1, I), D)
                        else *** hay que reequilibrar
                                if (R1 > raiz(D)) then
                                        rotarIzq(arbolBin(R, I, insertar(R1, D)))
                                else
                                        rotatIzq(arbolBin(R, I, rotarDer(insertar(R1, D))))
                                fi .
                        fi .
                fi .

Extracción

El procedimiento de borrado es el mismo que en el caso de árbol binario de búsqueda.La diferencia se encuentra en el proceso de reequilibrado posterior. El problema de la extracción puede resolverse en O (log n) pasos. Una extracción trae consigo una disminución de la altura de la rama donde se extrajo y tendrá como efecto un cambio en el factor de equilibrio del nodo padre de la rama en cuestión, pudiendo necesitarse una rotación.

Esta disminución de la altura y la corrección de los factores de equilibrio con sus posibles rotaciones asociadas pueden propagarse hasta la raíz.


Extraccion1.jpg Borrar A, y la nueva raíz será M.

Extraccion2.jpg Borrado A, la nueva raíz es M. Aplicamos la rotación a la derecha.

Extraccion3.jpg El árbol resultante ha perdido altura.

En borrado pueden ser necesarias varias operaciones de restauración del equilibrio, y hay que seguir comprobando hasta llegar a la raíz.


op eliminar: X$Elt AVL{X} -> AVL{X} .
eq eliminar(R, crear) == crear .
ceq eliminar(R1, arbolBin(R2, I, D)) ==
        if (R1 == R2) then
                if esVacio(I) then
                        D
                elseif esVacio(D) then
                        I
                else
                        if (altura(I) - altura(eliminar(min(D),D)) < 2) then
                                arbolBin(min(D), I, eliminar(min(D), D))
                        ***tenemos que reequilibrar
                        elseif (altura(hijoIzq(I) >= altura(hijoDer(I)))) then
                                rotDer(arbolBin(min(D), I, eliminar(min(D),D)))
                        else
   rotDer(arbolBin(min(D), rotIzq(I), eliminar(min(D),D)))

Búsqueda

Ejemplo en Java

public class Nodo { 
    int numMat; 
    Nodo izqda, drcha; 
    public Nodo(int mat){ 
        numMat = mat; 
        izqda = drcha = null; 
    } 
    public void re_enorden(){ 
        if(izqda != null) 
            izqda.re_enorden(); 
        System.out.println("Matricula:   " +numMat); 
        if(drcha != null) 
            drcha.re_enorden(); 
    } 
} 
 
public class ABB { 
    private Nodo raiz; 
    public ABB(){ 
        raiz = null; 
    } 
    public void insertar(int nuevoM){ 
        if(raiz==null){ 
            raiz =  new Nodo(nuevoM); 
        } 
        else{ 
            insertar(raiz,nuevoM); 
        } 
    } 
    private void insertar(Nodo rz, int nm){ 
        if (rz == null) 
            rz = new Nodo(nm); 
        else if(nm < rz.numMat) 
            insertar(rz.izqda,nm); 
        else if(nm > rz.numMat) 
            insertar(rz.drcha,nm); 
        else 
            System.out.println("Numero Duplicados"); 
    } 
    public void visualizar(){ 
        if(raiz!=null) 
            raiz.re_enorden(); 
    } 
}
 
public class Ejecutar { 
    public static void main(String []args){ 
        ABB arbol = new ABB(); 
        arbol.insertar(6); 
        arbol.insertar(3); 
        arbol.insertar(7); 
        arbol.visualizar(); 
    } 
}

Ejemplo de TAD AVL en C

#include <stdio.h>
 
typedef struct AVL{
        int dato, FB; // FB es la altura del subarbol izquierdo menos la altura del subarbol derecho
        AVL *izq, *der;
        bool borrado;
} AVL;
 
void rotarLL(AVL* &A){ //precond: el arbol necesita una rotacion LL
        AVL* aux = A->izq->der;
        A->izq->der = A;
        A->izq->FB = 0; 
        AVL* aux2 = A->izq;
        A->izq = aux;
        A->FB = 0;
        A = aux2;
}
 
void rotarRR(AVL* &A){ //precond: el arbol necesita una rotacion RR
        AVL* aux = A->der->izq;
        A->der->izq = A;
        A->der->FB = 0; 
        AVL* aux2 = A->der;
        A->der = aux;
        A->FB = 0;
        A = aux2;
}
 
void rotarLRalter(AVL* &A){ //precond: el arbol necesita una rotacion LR
        rotarRR(A->izq);
        rotarLL(A);
}
 
void rotarRLalter(AVL* &A){ //precond: el arbol necesita una rotacion RL
        rotarLL(A->der);
        rotarRR(A);
}
 
AVL* Crear(){
        return NULL;
}
 
void Insert(int n, bool &aumento, AVL* &A){
        if (A == NULL){
                A = new AVL;
                A->dato = n;
                A->FB = 0;
                A->izq = NULL;
                A->der = NULL;
                aumento = true;
                A->borrado = false;
        }else{
                if (n < A->dato){                      
                        Insert(n, aumento, A->izq);                    
                        if (aumento){
                                switch (A->FB){
                                        case -1:{
                                                A->FB = 0;
                                                aumento = false;
                                                break;
                                        }
                                        case 0:{
                                                A->FB = 1;
                                                aumento = true;
                                                break;
                                        }
                                        case 1:{
                                                if (A->izq->FB == 1){ // Si es 1 necesita una rotacion LL si es -1 necesita una rotacion LR
                                                        rotarLL(A);
                                                }else{
                                                        rotarLRalter(A);
                                                }
                                                aumento = false;
                                                break;
                                        }
                                }
                        }
                }else{
                        Insert(n, aumento, A->der);                    
                        if (aumento){
                                switch (A->FB){
                                        case -1:{
                                                if (A->der->FB == 1){ // Si es 1 necesita una rotacion RL si es -1 necesita una rotacion RR
                                                        rotarRLalter(A);
                                                }else{
                                                        rotarRR(A);
                                                }
                                                aumento = false;                                             
                                                break;
                                        }
                                        case 0:{
                                                A->FB = -1;
                                                aumento = true;
                                                break;
                                        }
                                        case 1:{
                                                A->FB = 0;
                                                aumento = false;
                                                break;
                                        }
                                }
                        }
                }
        }
}
 
void Insertar(AVL* &A, int n){
        bool aumento;
        Insert(n, aumento, A);
}
 
bool EsVacio(AVL* A){
        return A == NULL;
}
 
bool Pertenece(AVL* A, int n){
        if (A == NULL){
                return false;
        }else{
                if (A->dato == n){
                        if (A->borrado){
                                return false;
                        }else{
                                return true;
                        }
                }else if (n < A->dato){         
                        return Pertenece(A->izq, n);
                }else{
                        return Pertenece(A->der, n);
                }         
        }
}
 
void Borrar(AVL* &A, int n){
        if (A->dato == n){
                A->borrado = true;
        }else if (n < A->dato){         
                Borrar(A->izq, n);
        }else{
                Borrar(A->der, n);
        }
}

Véase también

Árbol AVL (INGLES)

Árbol Binario (INGLES)

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Árbol AVL — es un término usado en computación para referirse a un tipo especial de árbol binario ideado por los matemáticos rusos Adelson Velskii y Landis. Fue el primer árbol de búsqueda binario auto balanceable que se ideó …   Enciclopedia Universal

  • Árbol rojo-negro — Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en… …   Wikipedia Español

  • Árbol binario de búsqueda — Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática. Contenido 1 Descripción 2 Operaciones 2.1 Búsqueda …   Wikipedia Español

  • Árbol biselado — Un Árbol biselado o Árbol Splay es un Árbol binario de búsqueda auto balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores. Realiza operaciones básicas como… …   Wikipedia Español

  • Árbol 2-3 — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 2 de febrero de 2009. También puedes… …   Wikipedia Español

  • Árbol AA — En informática un árbol AA es un tipo de árbol binario de búsqueda auto balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, Arne Andersson. Los árboles AA son …   Wikipedia Español

  • Árbol de Fibonacci — Árboles de Fibonacci de orden 1, 2, 3 y 4. Se llama árbol de Fibonacci a una variante de árbol binario con la propiedad que el orden de un nodo se calcula como la sucesión de Fibonacci. El árbol de Fibonacci se define de la siguiente manera: El… …   Wikipedia Español

  • Árbol binario de búsqueda auto-balanceable — En ciencias de la computación, un árbol binario de búsqueda auto balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento …   Wikipedia Español

  • Árbol (informática) — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • AVL — El acrónimo AVL puede tomar a: Automatic Vehicle Location (Localización Automática de Vehículos). La Academia Valenciana de la Lengua. El árbol binario de datos AVL, ideado por Adelson Velskii y Landis. Nivelador automático de volumen (Auto Bajo… …   Wikipedia Español


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.