ARBOLES AVL
ARBOLES AVL
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.
CARACTERÍSTICAS
1.
Árbol binario de búsqueda
2.
Arboles balanceados
3.
La Inserción y retiro desbalancean el árbol
4.
La diferencia de alturas del árbol derecho con el
izquierdo es de (-1,0,1)
Factor
de balance o equilibrio
Se usa factor de balance
o equilibrio cuando nuestro árbol se encuentra desbalanceado por derecha o por
izquierda. (
Para balancear nuestros
arboles tenemos las siguientes herramientas
1.
Rotación a la
derecha
2.
Rotación a la
izquierda
3.
Doble rotación a
la derecha
4.
Doble rotación a la derecha
A continuación se
explicara cómo usar cada una de las
herramientas anteriores.
Rotación a la izquierda
Esta rotación se usará cuando el subárbol derecho de un
nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2.
Y además, la raíz del subárbol derecho tenga una FE de 1 ó 0, es decir, que
esté cargado a la derecha o esté equilibrado.
Ejemplo:
Se identifica p y q,
determinando el FB del árbol; si se observa de abajo hacia arriba, el
primer FB que sea diferente a 1 se le señala con una flecha y se le
identifica con una p, anterior al nodo donde se halló p, se le identificara
como q .
Se realiza una simple rotación
a la izquierda de 45° desde P .
La raíz del árbol queda
con FB -1, de manera que es balanceado.
Por último verificamos
que el inorden de igual de cuando no era avl a cuando lo rotamos para convertirlo
el avl.
Rotación
por la derecha
Esta rotación se usará
cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho,
es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo
tenga una FE de -1 ó 0, es decir, que esté cargado a la izquierda o
equilibrado.
Ejemplo:
Se identifica p y q, determinando el FB del árbol; si se observa de abajo hacia arriba, el primer FB que sea diferente a 1 se le señala con una flecha y se le identifica con una p, anterior al nodo donde se halló p, se le identificara como q .
Se realiza una simple rotación a la derecha de 45° desde P .
La raíz del árbol queda con FB 0, de manera que es balanceado.
Por último verificamos que el inorden de igual de cuando no era avl a cuando lo rotamos para convertirlo el avl.
Ejemplo:
Doble
rotación a la izquierda
Se hace doble rotación a la izquierda si se cumplen
los siguientes entes:
1. El
nodo insertado por p tiene un factor de balance (F.B.) menor que 1
2. El
nodo insertado por q tiene un factor de balance igual a 1 o -1.
Ejemplo:
Se identifica p y q, determinando el FB del árbol; si se observa de abajo hacia arriba, el primer FB que sea diferente a 1 se le señala con una flecha y se le identifica con una p, anterior al nodo donde se halló p, se le identificara como q .
Hay que hacer una simple rotación a la derecha desde q y una simple rotación a la izquierda desde p.
La raíz del árbol queda con FB 0, de manera que es balanceado.
Por último verificamos que el inorden de igual de cuando no era avl a cuando lo rotamos para convertirlo el avl.
Doble
rotación a la derecha
Se hace doble rotación a la derecha si se cumplen los
siguientes entes:
1. El
nodo insertado por p tiene un factor de balance (F.B.) menor que 1
2. El
nodo insertado por q tiene un factor de balance igual a 1 o -1.
Ejemplo:
Se identifica p y q, determinando el FB del árbol; si se observa de abajo hacia arriba, el primer FB que sea diferente a 1 se le señala con una flecha y se le identifica con una p, anterior al nodo donde se halló p, se le identificara como q .
Hay que hacer una simple rotación a la izquierda desde q y una simple rotación a la derecha desde p.
La raíz del árbol queda con FB 0, de manera que es balanceado.
Por último verificamos que el inorden de igual de cuando no era avl a cuando lo rotamos para convertirlo el avl.
Tecnicas de rotacion en arboles balanceados from PEREZHROS
Retiro
de nodos
Recordamos un poco la idea del algoritmo de
eliminación sobre árboles binarios de búsqueda. Primero se recorre el árbol
para detectar el nodo a eliminar. Una vez hecho esto hay tres casos a
diferenciar por su complejidad:
- Si dicho nodo es una hoja procedemos a eliminarlos de inmediato, sin más.
- Si dicho nodo tiene un sólo hijo, el nodo puede eliminarse después de ajustar un apuntador del padre para saltar el nodo.
- Si dicho nodo tiene dos hijos el caso es un poco más
complicado. Lo que se estila hacer es reemplazar el nodo actual por el menor
nodo de su subárbol derecho (y luego eliminar éste).
Hay que tener en cuenta que después de retirar un
nodo, si el árbol queda des balanceado tendremos que proceder a balancearlo usando
las técnicas dichas anteriormente.
Ejemplo:
En el siguiente árbol avl vamos a retirar el nodo 6.
Como apreciamos luego de retirar el 6 nuestro árbol quedo desbalanceado, por lo que debemos balancearlo usando las técnicas anteriormente mencionadas.
/* EN ESTE PROGRAMA SE MUESTRAN LAS RUTINAS QUE
INSERTAN NODOS EN UN ARBOL AVL MANTENIENDO LAS PROPIEDADES
DE UN ARBOL AVL */
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
//#include "alloc.h"
#define nodo_arbol (struct nodo *) malloc (sizeof (struct nodo))
struct nodo {
int info;
int bal;
struct nodo *izq;
struct nodo *der;
};
int main()
{
int n;
void inorden (struct nodo *raiz);
struct nodo *raiz=NULL;
int ins_avl(struct nodo **,int);
int lea();
printf ("lea n \n"); n = lea();
while (n != 9999) {
ins_avl (&raiz,n);
printf ("lea n \n"); n = lea();
}
inorden(raiz);
getch();
return 0;
}
void inorden (struct nodo *raiz)
{
if (raiz != NULL) {
inorden (raiz->izq);
printf ("%d %d ",raiz->info,raiz->bal);
inorden (raiz->der);
}
}
void r_derecha (struct nodo *p,struct nodo *q)
{
p->bal = 0;
q->bal = 0;
p->izq = q->der;
q->der = p;
}
void r_izquierda (struct nodo *p,struct nodo *q)
{
p->bal = 0;
q->bal = 0;
p->der = q->izq;
q->izq = p;
}
void dr_derecha (struct nodo *p,struct nodo **q)
{
struct nodo *r;
r = (*q)->der;
(*q)->der = r->izq;
r->izq = *q;
p->izq = r->der;
r->der = p;
switch (r->bal) {
case -1 : (*q)->bal = 1;
p->bal = 0;
break;
case 0 : (*q)->bal = p->bal = 0;
break;
case 1 : (*q)->bal = 0;
p->bal = -1;
break;
}
r->bal = 0;
*q = r;
}
void dr_izquierda (struct nodo *p,struct nodo **q)
{
struct nodo *r;
r = (*q)->izq;
(*q)->izq = r->der;
r->der = *q;
p->der = r->izq;
r->izq = p;
switch (r->bal) {
case -1 : (*q)->bal = 0;
p->bal = 1;
break;
case 1 : (*q)->bal = -1;
p->bal = 0;
break;
case 0 : (*q)->bal = p->bal = 0;
break;
}
r->bal = 0;
*q = r;
}
struct nodo *crear_nodo (int n)
{
struct nodo *nuevo;
nuevo = nodo_arbol;
nuevo->info = n;
nuevo->bal = 0;
nuevo->izq = NULL;
nuevo->der = NULL;
return (nuevo);
}
int ins_avl (struct nodo **raiz,int n)
{
struct nodo *nuevo,*p,*q,*s,*pivote,*pp;
int llave,altura;
nuevo = crear_nodo(n);
if (*raiz == NULL) {
*raiz = nuevo;
return (1); /* el arbol tiene un solo nodo */
}
pp = q = NULL;
pivote = p = *raiz;
llave = nuevo->info;
while (p != NULL) {
if (p->bal) {
pp = q;
pivote = p;
}
if (llave == p->info) {
free (nuevo);
return (2); /* ya existe */
}
else {
q = p;
if (llave < p->info)
p = p->izq;
else p = p->der;
}
}
if (llave < q->info)
q->izq = nuevo;
else q->der = nuevo;
if (llave < pivote->info) {
s = pivote->izq;
altura = 1;
}
else {
s = pivote->der;
altura = -1;
}
p = s;
while (p != nuevo)
if (llave < p->info) {
p->bal = 1;
p = p->izq;
}
else {
p->bal = -1;
p = p->der;
}
if (pivote->bal == 0)
pivote->bal = altura;
else if (pivote->bal + altura == 0)
pivote->bal = 0;
else {
if (altura == 1)
if (s->bal == 1)
r_derecha (pivote,s);
else dr_derecha (pivote,&s);
else if (s->bal == -1)
r_izquierda (pivote,s);
else dr_izquierda (pivote,&s);
if (pp == NULL)
*raiz = s;
else if (pp->izq == pivote)
pp->izq = s;
else pp->der = s;
}
}
int lea()
{
char l[10];
gets(l);
return (atoi(l));
}
0 comentarios: