Á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ó.
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.
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
Factor de equilibrio [editar]
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á equilibrado y su subárbol derecho es un nivel más alto.
-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio Fe≥2 o 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).
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.
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.
ROTACIÓN DOBLE A LA IZQUIERDA.
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
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.
Borrar A, y la
nueva raíz será M.
Borrado A, la
nueva raíz es M. Aplicamos la rotación a la derecha.
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 [editar]
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();
}
