Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles izquierdo y derecho no difieren en más de 1.
No se trata de árboles perfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos donde los ABB no garantizan tiempos de búsqueda óptimos.
El algoritmo para mantener un árbol AVL equilibrado se basa en reequilibrados locales, de modo que no es necesario explorar todo el árbol después de cada inserción o borrado.
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.
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".
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 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.
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 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.
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
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.
***CODIGO EN JAVA****
Clase AVL
package arboles;
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
public class AVL extends JFrame {
AVLgrafico t;
public AVL() {
t = new AVLgrafico(50);
JMenuBar menuBar = new JMenuBar();
JMenu menuFile = new JMenu();
JMenuItem menuFileExit = new JMenuItem();
menuFile.setText("File");
menuFileExit.setText("Exit");
// Add action listener.for the menu button
menuFileExit.addActionListener
(
new ActionListener() {
public void actionPerformed(ActionEvent e) {
AVL.this.windowClosed();
}
}
);
menuFile.add(menuFileExit);
menuBar.add(menuFile);
setTitle("AVLFrame");
setJMenuBar(menuBar);
setSize(new Dimension(500, 400));
// Add window listener.
this.addWindowListener
(
new WindowAdapter() {
public void windowClosing(WindowEvent e) {
AVL.this.windowClosed();
}
}
);
}
/**
* Shutdown procedure when run as an application.
*/
public static void main(String[] args) {
// Create application frame.
AVL frame = new AVL();
// Show frame.
frame.setVisible(true);
}
protected void windowClosed() {
// TODO: Check if it is safe to close the application
// Exit application.
System.exit(0);
}
public void paint(Graphics g)
{ int dato,n = 20;
Random r = new Random();
for ( int i =1 ; i < n ; i++)
{
System.out.print(i);
g.setColor(new Color(180,180,220));
g.fillRect(1,1,500,500);
dato = r.nextInt(100);
t = t.insercion(t,dato);
t.dibuja(g,t,200,30,200,30,100);
pausa(1000);
}
raya();
pausa(1000);
for ( int i =1 ; i <n ; i++)
{
g.setColor(new Color(180,180,220));
g.fillRect(1,1,500,500);
t = t.elimina(t,t.dato());
if ( t != null)
t.dibuja(g,t,200,30,200,30,100);
pausa(1000);
}
}
public void raya()
{
System.out.println("===================================================");
}
private void pausa(int a)
{
try { Thread.sleep(a);
}catch(Exception e){ }
}
}
Clase AVLgrafico
package arboles;
import java.awt.*;
public class AVLgrafico {
private int dato ;
private static boolean propagacion;
private int balance ;
private AVLgrafico izq,der;
AVLgrafico(int d)
{
dato = d ;
propagacion = true ;
izq = der = null;
balance = 0 ;
}
int dato() {return dato;}
private AVLgrafico LL(AVLgrafico t)
{
AVLgrafico p = t.izq;
t.izq = p.der;
p.der = t ;
return p;
}
private AVLgrafico RR(AVLgrafico t)
{
AVLgrafico p = t.der;
t.der = p.izq;
p.izq = t ;
return p;
}
private AVLgrafico LR(AVLgrafico t)
{
AVLgrafico p = t.izq;
t.izq = RR(p);
return LL(t);
}
private AVLgrafico RL(AVLgrafico t)
{
AVLgrafico p = t.der;
t.der = LL(p);
return RR(t);
}
private int cuentaNiveles(AVLgrafico t)
{
if ( t == null) return -1;
int a = cuentaNiveles(t.izq);
int b = cuentaNiveles(t.der);
if ( a < b ) return b + 1 ;
return a + 1 ;
}
private void corrigeBalance(AVLgrafico t)
{
if ( t!=null)
{
int a = cuentaNiveles(t.izq);
int b = cuentaNiveles(t.der);
t.balance = b-a ;
corrigeBalance(t.izq);
corrigeBalance(t.der);
}
}
public AVLgrafico insercion(AVLgrafico t, int d)
{
if ( t==null) return new AVLgrafico(d);
if ( d < t.dato)
{
t.izq = insercion(t.izq,d);
if (propagacion)
{
t.balance--;
if ( t.balance == -2)
{
if (t.izq.balance < 0 )
t = LL(t);
else
t = LR(t);
corrigeBalance(t);
propagacion = false ;
}
if ( t.balance == 0 )
propagacion = false ;
}
}
else
{
t.der = insercion(t.der,d);
if (propagacion)
{
t.balance++;
if ( t.balance == 2)
{
if (t.der.balance < 0 )
t = RL(t);
else
t = RR(t);
corrigeBalance(t);
propagacion = false ;
}
if ( t.balance == 0 )
propagacion = false ;
}
}
return t;
}
public void dibuja(Graphics g, AVLgrafico t,int i, int j, int pi, int pj, int desplaza)
{
if (t!= null)
{
g.setColor(Color.blue);
g.drawLine(i+12,j+12,pi+12,pj+12);
dibuja(g,t.izq,i-desplaza,j+40,i,j,desplaza/2);
dibuja(g,t.der,i+desplaza,j+40,i,j,desplaza/2);
g.setColor(new Color(220,220,230));
g.fillOval(i,j,25,25);
g.setColor(Color.blue);
g.drawOval(i,j,25,25);
g.drawString(String.valueOf(t.dato),i+5,j+20);
g.setColor(Color.red);
g.drawString(String.valueOf(t.balance),i+5,j+40);
}
}
public void muestra(AVLgrafico t, int nivel)
{
if (t!= null)
{
muestra(t.izq,nivel+1);
for( int i=0;i<nivel;i++) System.out.print(" ");
System.out.println(t.dato);
muestra(t.der,nivel+1);
}
}
public AVLgrafico elimina(AVLgrafico t, int x)
{
t = eliminar(t,x);
corrigeBalance(t);
return t;
}
public AVLgrafico eliminar(AVLgrafico t, int x)
{
if ( t == null ) return null ;
if ( x < t.dato )
{
t.izq = eliminar(t.izq,x);
if ((propagacion ) && (t.balance == 0))
{
t.balance++;
propagacion = false;
}
if (propagacion)
{
t.balance++;
corrigeBalance(t);
if ( t.balance == 2)
{
if (t.der.balance < 0 )
t = RL(t);
else
t = RR(t);
// corrigeBalance(t);
// propagacion = false ;
}
}
}
else if ( x > t.dato)
{
t.der = eliminar(t.der,x);
if ((propagacion ) && (t.balance == 0))
{
t.balance--; if ( t.balance == -2)prin("DEBERIA ROtAR");
propagacion = false;
}
if (propagacion)
{
t.balance--;
corrigeBalance(t);
if ( t.balance == -2)
{
if (t.izq.balance < 0 )
t = LL(t);
else
t = LR(t);
// corrigeBalance(t);
// propagacion = false ;
}
}
}
else // dato encontrado se debe eliminar
{ // se usara el criterio de reemplazar la raiz por el mayor de los hijos menores
propagacion = true ;
if ( t.izq == null) return t.der ;
else if (t.izq.der == null )
{
t.dato = t.izq.dato ;
t.balance = t.izq.balance ;
t.izq = eliminar(t.izq,t.dato);
corrigeBalance(t);
if ( t.balance == 2)
{
if (t.der.balance < 0 )
t = RL(t);
else
t = RR(t);
}
}
else
{
AVLgrafico h,p;
p = t.izq ;
h = p.der ;
while (h.der != null)
{
p = h ;
h = h.der ;
}
t.dato = h.dato;
t.izq = eliminar(t.izq,t.dato) ;
corrigeBalance(t);
if ( t.balance == 2)
{
if (t.der.balance < 0 )
t = RL(t);
else
t = RR(t);
}
}
}
corrigeBalance(t);
return t ;
}
public void prin ( String s) { System.out.println(s); }
}
Clase Probador
package arboles;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
public class Probador extends JFrame{
MonoConABB monin;
/**
* The constructor
*/
public Probador() {
JMenuBar menuBar = new JMenuBar();
JMenu menuFile = new JMenu();
JMenuItem menuFileExit = new JMenuItem();
menuFile.setText("File");
menuFileExit.setText("Exit");
monin = new MonoConABB();
Container c = this.getContentPane();
// add(c);
c.add(monin);
// Add action listener.for the menu button
menuFileExit.addActionListener
(
new ActionListener() {
public void actionPerformed(ActionEvent e) {
Probador.this.windowClosed();
}
}
);
menuFile.add(menuFileExit);
menuBar.add(menuFile);
setTitle("Probador");
setJMenuBar(menuBar);
setSize(new Dimension(700, 500));
// Add window listener.
this.addWindowListener
(
new WindowAdapter() {
public void windowClosing(WindowEvent e) {
Probador.this.windowClosed();
}
}
);
}
public static void main(String[] args) {
// Create application frame.
Probador frame = new Probador();
// Show frame.
frame.setVisible(true);
}
/**
* Shutdown procedure when run as an application.
*/
protected void windowClosed() {
// TODO: Check if it is safe to close the application
// Exit application.
System.exit(0);
}
}
Clase MonoConABB
package arboles;
import java.awt.*;
public class MonoConABB extends Canvas
{
ABB t;
MonoConABB()
{
t = new ABB(50);
/* for(int i=0;i<30;i++)
t = t.insertar(t,(int)(Math.random()*10000)%100);
t.inorden(t);
System.out.println("\n ----------------------- " );
t.postorden(t);
System.out.println(" \n---------------------- " );
t.preorden(t);
System.out.println("\n------------------- " );
*/
}
public void paint(Graphics g)
{ for(int i=0;i<30;i++)
{
int paPonerlo =(int)(Math.random()*10000)%100;
g.setColor(Color.BLACK);
g.drawString(String.valueOf(paPonerlo),15,390);
t.dibujar(g,t,350,20,350,20,150);
try { Thread.sleep(1250);
} catch (Exception e) { }
t = t.insertar(t,paPonerlo);
g.setColor(Color.WHITE);
g.fillRect(10,370,40,40);
}
}
}
Clase ABB
package arboles;
import java.awt.*;
/*//////////////////////////////////////////////////////
ARBOL DE BUSQUEDA BINARIA
//////////////////////////////////////////////////////*/
public class ABB
{
private int dato ;
private ABB izq, der ;
ABB(int d)
{
dato = d ;
izq = der = null ;
}
public ABB insertar(ABB t,int d)
{
if (t == null)
return new ABB(d);
if (d == t.dato) return t;
if ( d < t.dato)
t.izq = insertar(t.izq,d);
else
t.der = insertar(t.der,d);
return t ;
}
/*
* RECORRIDOS
**/
public void inorden(ABB t)
{
if (t != null)
{
inorden(t.izq);
System.out.print(" " + t.dato);
inorden(t.der);
}
}
public void postorden(ABB t)
{
if (t != null)
{
postorden(t.izq);
postorden(t.der);
System.out.print(" " + t.dato);
}
}
public void preorden(ABB t)
{
if (t != null)
{
System.out.print(" " + t.dato);
preorden(t.izq);
preorden(t.der);
}
}
public void dibujar(Graphics g,ABB t, int x,int y, int px, int py, int desplazamiento)
{
if (t != null)
{
g.setColor(new Color(5,5,5));
g.drawLine(x+10,y+10,px+10,py+18);
g.setColor(new Color(255,255,0));
g.fillOval(x,y,20,20);
g.setColor(new Color(5,5,5));
g.drawString(String.valueOf(t.dato),x+5,y+15);
g.drawOval(x,y,20,20);
dibujar(g,t.izq,x-desplazamiento,y+30,x,y,desplazamiento/2);
dibujar(g,t.der,x+desplazamiento,y+30,x,y,desplazamiento/2);
}
}
}
Clase Main
package arboles;
public class Main {
public static void main(String[] args) {
AVL avl = new AVL();
avl.setVisible(true);
MonoConABB p = new MonoConABB();
//p.setVisible(true);
}
}