Desarrollado por Adelson-Velskii y Landis (1962). Los AVL son
árboles balanceados (equilibrados) con respecto a la altura de los subárboles:
Un árbol está equilibrado respecto a la altura si y solo si para cada uno de sus
nodos ocurre que las alturas de los dos subárboles difieren como mucho en 1
Es un árbol de búsqueda binario,en la cual la diferencia de las alturas de los subarboles de cada uno es uno.
Los arboles avl siempre están en equilibrio de tal modo de que si uno llegase a estar en desequilibrio realizamos rotaciones.
¿Para que sirve un arbol avl?
los podemos emplear en redes de mercadeo en seguridad informática seguridad de redes ya que nos daría un diagrama organizado y estructurados de los datos de la red
Características
*Cada nodo tiene signado un peso de acuerdo a las alturas de sus subarboles
*Un nodo tiene un peso de 1 si su subarbol derecho es mas alto , -1 si su subarbol izquierdo es mas alto y 0 si las alturas son las mismas
*La diferencia entre las alturas de los subarboles derecho e izquierdo no de exceder de 1
OPERACIONES BASICAS
*Insercion
*Rotacion Simple
*Rotacion Doble
*Eliminar
INSERCIÓN
En un árbol AVL tras realizar la insercion hay que comprobar que se sigue manteniendo la condición de equilibrio, o lo que es lo mismo , que la altura del subarbol izquierdo y la del subarbol derecho difieran en una unidad o sean iguales.Si se produce un desequilibrio hay que reestructurar el arbol para que siga siendo un arlbol AVL .El balanceo se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio, los mecanismos que usaremos para balancear el arbol son rotacion simple y doble rotacio a la derecha o al a izquierda segun el des balanceo del arbol.
Inserte las claves en el orden indicado a fin de incorporarlas a un árbol AVL
10,100,20,80,40,70.
Ingresamos el numero 10 después el 100 y así sucesivamente , y al ingresar el 20 como esta en medio de los dos pasa a ser la raiz del arbol
2) al insertar el 40 dividimos el subarbol izquierdo quedando de raiz el 80 y como hijos el 40 y el 100
g
SEGUNDO EJEMPLO
2)Inserte las claves en el orden indicado a fin de incorporarlas a un árbol AVL
5,10,20,30,40,50,60
Al igual que el arbol anterior pasa el 30 a ser la raiz ya que se encuentra en medio de los dos números creando mas ramas.
ELIMINACION
Cuando queremos eliminar un nodo del arbol debemos de tener siempre encuenta el balanceo del arbol ya que si esta desbalanceado deja de ser AVL , si se desbalancea debemos hacer rotaciones simples o dobles.Para eliminar el nodo lo hacemos como en un arbol binario ordenado, al localizar el nodo que queremos eliminar haremos los siguientes pasos:
*Si el nodo es un nodo hoja, simplemete lo eliminamos.
*Si el nodo solo tiene un hijo, lo sustituimos por su hijo
*Si el nodo eliminado tiene dos hijos, lo sustituimos por el hijo derecho y colocamos el hijo izquierdo en el subarbol izquierdo del hijo derecho.
eliminar la siguente secuencia del arbol:
100,29,71,82,48,39,101,22,46, 17,3,20,25,10.
NOTA: Despues de realizar la eliminacion concideraremos los siguentes aspectos para evaluar el balanceo del arbol
*Si el balanceo del padre del nodo eliminado cambia de 0 A + O - 1,el arbol quedo balanceado.
*Si el padre del nodo eliminado cambio de + o - 1 a 0, la altura del arbol ha cambiado y se afecta el e balanceo de su nodo antecesor
*Si el balanceo del padre del nodo eliminado cambia de + o - 1
a + o - 2 hay que hacer una rotacion. Despues de concluirla, el balanceo del padre podria cambiar, lo que as u vez podria forzarnos a hacer otrs rotacines en toda la ruta hacia arriba a medida que ascendemos hacia la raiz. Si encontramos en la ruta un nodo que cambie de 0 a + o - 1 entonces terminamos
ROTACIONES
Esta rotacion se usara cuando el subarbole izquierdo de un nodo sea 2 unidades mas alto que el derecho es decir su peso sea igual a -2.
Existen dos tipos de rotaciones
*Rotacion simple a la derecha.
*Rotacion simple a la izquierda.
*Rotacion doble a la derecha.
*Rotacion doble a la izquierda.
ROTACION SIMPLE A LA DERECHA
Una rotacion simple a la derecha se cumple si :
*El nodo indicado por P tiene valor de balance mayor a 1
*El nodo indicado por P tiene valor de balance mayor a 1
ROTACION SIMPLE A LA DERECHA
Es necesario realizar una rotación simple a la derecha cuando el suarbol izquierdo de un nodo sea 2 unidades mas alto que el derecho cuando su o cuando la sumatoria de sus nodos sea igual a 2. y ademas , la raiz del suarbol izquierdo tenga un balanceo de 1, es decir que este cargado ala izquierda
Procederemos del siguiente modo:
Llamaremos P al nodo que muestra el desequilibrio, el que tiene una sumatoria de -2. Y llamaremos Q al nodo raíz del subárbol izquierdo de P. Además, llamaremos A al subárbol izquierdo de Q, B al subárbol derecho de Q y C al subárbol derecho de P.
- Pasamos el subárbol derecho del nodo Q como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de Q siguen estando a la izquierda de P.
- El árbol P pasa a ser el subárbol derecho del nodo Q.
- Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
En el árbol resultante se puede ver que tanto P como Q quedan equilibrados en cuanto altura. En el caso de P porque sus dos subárboles tienen la misma altura (n), en el caso de Q, porque su subárbol izquierdo A tiene una altura (n+1) y su subárbol derecho también, ya que a P se añade la altura de cualquiera de sus subárboles.
En el caso de que el subárbol izquierdo esté equilibrado, el procedimiento es similar, pero los FE de los nodos P y Q en el árbol resultante son diferentes.
En principio, parece poco probable que nos encontremos un árbol con esta estructura, pero es posible encontrarlos cuando se borran nodos.
1) Si esta desequilibrado a la izquierda y su hijo derecho tiene el mismo signo (+) hacemos rotación sencilla izquierda.
1) Si esta desequilibrado a la izquierda y su hijo derecho tiene el mismo signo (+) hacemos rotación sencilla izquierda.
ROTACION SIMPLE A LA IZQUIERDA
Es necesario realizar una simple rotacion a la izquierda cuando el balanceo del subarbol derecho de un nodo sea 2 unidades mas alto que el izquierdo, es decir cuando el balance del suarbol izquierdo sea -2. y ademas , la raiz del suarbol derecho tenga como balanceo -1, es decir que este este cargado a a la derecha
Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de 2. Y llamaremos Q al nodo raíz del subárbol derecho de P. Además, llamaremos A al subárbol izquierdo de P, B al subárbol izquierdo de Q y C al subárbol derecho de Q.
- Pasamos el subárbol izquierdo del nodo Q como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de Q siguen estando a la derecha de P.
- El árbol P pasa a ser el subárbol izquierdo del nodo Q.
- Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
En el árbol resultante se puede ver que tanto P como Q quedan equilibrados en cuanto altura. En el caso de P porque sus dos subárboles tienen la misma altura (n), en el caso de Q, porque su subárbol izquierdo A tiene una altura (n+1) y su subárbol derecho también, ya que a P se añade la altura de cualquiera de sus subárboles.
ROTACION SIMPLE A LA IZQUIERDA
Es necesario realizar una simple rotacion a la izquierda cuando el balanceo del subarbol derecho de un nodo sea 2 unidades mas alto que el izquierdo, es decir cuando el balance del suarbol izquierdo sea -2. y ademas , la raiz del suarbol derecho tenga como balanceo -1, es decir que este este cargado a a la derecha
Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de 2. Y llamaremos Q al nodo raíz del subárbol derecho de P. Además, llamaremos A al subárbol izquierdo de P, B al subárbol izquierdo de Q y C al subárbol derecho de Q.
- Pasamos el subárbol izquierdo del nodo Q como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de Q siguen estando a la derecha de P.
- El árbol P pasa a ser el subárbol izquierdo del nodo Q.
- Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
4) Pasamos el subárbol derecho del nodo R como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de R siguen estando a la izquierda de P.
5) Ahora, el nodo R pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo R, en lugar del nodo P. Como en los casos anteriores, previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
6) El árbol P pasa a ser el subárbol derecho del nodo R.
Doble rotacion 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, es decir, que esté cargado a la izquierda.
En este caso también tendremos que realizar dos rotaciones.
Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de 2. Llamaremos Q al nodo raíz del subárbol derecho de P, y R al nodo raíz del subárbol izquierdo de Q.
1) Haremos una rotación simple de Q a la derecha
2) Después, haremos una rotación simple de P a la izquierda.
1) Haremos una rotación simple de Q a la derecha
2) Después, haremos una rotación simple de P a la izquierda.
Con más detalle, procederemos del siguiente modo
1) Pasamos el subárbol derecho del nodo R como subárbol izquierdo de Q. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de R siguen estando a la izquierda de Q.
2) Ahora, el nodo R pasa a tomar la posición del nodo Q, es decir, hacemos que la raíz del subárbol derecho de P sea el nodo R en lugar de Q.
3)El árbol Q pasa a ser el subárbol derecho del nodo R
1) Pasamos el subárbol derecho del nodo R como subárbol izquierdo de Q. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de R siguen estando a la izquierda de Q.
2) Ahora, el nodo R pasa a tomar la posición del nodo Q, es decir, hacemos que la raíz del subárbol derecho de P sea el nodo R en lugar de Q.
3)El árbol Q pasa a ser el subárbol derecho del nodo R
4) Pasamos el subárbol izquierdo del nodo R como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de R siguen estando a la derecha de P.
5) Ahora, el nodo R pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo R, en lugar del nodo P. Como en los casos anteriores, previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.El árbol P pasa a ser el subárbol izquierdo del nodo R.
Si está desequilibrado a la izquierda (FE < –1), y su hijo derecho tiene distinto signo (+) hacemos rotación doble izquierda-derecha.
https://www.youtube.com/watch?v=sAOeP9K-bEE
http://ingsistemas.ufps.edu.co/SEED/arbolavl.html
No hay comentarios.:
Publicar un comentario