Download TAB AV

Almacenamiento y
Recuperacion de
Información- Arbol AVL
Ana Lilia Laureano Cruces
Universidad Autónoma Metropolitana
Por qué es importante el balanceo
en un árbol de búsqueda
• La manera en la que los elementos estén
distribuidos en un árbol de búsqueda
determinará su altura, y en consecuencia, la
cantidad de comparaciones a realizar al
buscar un elemento (eficiencia). Lo ideal
sería que el árbol tuviera sus elementos
distribuidos en forma equilibrada o
balanceada, consiguiendo así la mayor
eficiencia que ofrece la búsqueda binaria.
Cual es él número máximo de
comparaciones que se realiza en el peor
caso de búsqueda en un ABB
• La cantidad máxima de comparaciones al
realizar una búsqueda en ABB está
determinada por la altura del árbol.
• Si un ABB degenera en una lista, se tiene un
árbol cuya altura es igual a la cantidad de
nodos y el peor caso corresponderá a
realizar tantas comparaciones como nodos
tenga el árbol.
• Pero, qué pasa si el árbol está
balanceado, si la altura determina la
cantidad máxima de comparaciones,
sería ideal tener una altura mínima.
• La altura mínima se dará en la medida
en que cada nivel del árbol este
integrado a su máxma capacidad.
Arboles Binarios
• En general se tiene que el número
máximo de nodos en el nivel k, en un
árbol binario es 2k.
• Con base en lo anterior se puede
encontrar la cantidad total de
elementos que puede guardar un árbol
binario de altura k.
•
•
•
•
•
Altura 0 … 1 elemento
Altura 1 … 3 elementos
Altura 2 … 7 elementos
Altura 3 … 15 elementos
Altura 4 … 31 elementos
• De aquí que el nodo máximo de nodos en un
árbol binario de altura k es de 2 k -1.
• La cantidad máxima de comparaciones a
realizar en un ABB ideal de n elementos es:
log2 (n + 1).
• De aquí se concluye que el ABB debe estar
balanceado y como las operaciones sobre el
ABB no garantizan el balanceo, se debe
hacer una mejora.
Qué es un árbol
balanceado
• Se considera un árbol balanceado cuando
todos sus niveles, excepto el último, están
integrados a su máxima capacidad de
nodos.
• Entonces se trata de que los ABB, estén lo
más balanceados posibles.
• Para ello se maneja información relativa al
equilibrio de cada nodo del árbol.
Qué es un árbol AVL
• Es un ABB de búsqueda que trata de
mantenerse lo más balanceado posible,
conforme se realizan operaciones de
inserción y eliminación.
• Fueron propuestos en 1962, por Adelson,
Veliski y Landis, de donde surge su nombre.
Su contribución principal consistió en
presentar algoritmos eficientes de
eliminación e inserción.
• Formalmente se debe cumplir:
– Para cualquier nodo del árbol, la altura del
subarbol derecho menos la altura del
subarbol izquierdo (la diferencia entre las
alturas de sus subárboles) no excede una
unidad.
Arboles AVL
Arboles AVL
Arboles NO AVL
Arboles NO AVL
Qué es el factor de balance
• Los nodos de un árbol AVL, guardan un valor
entre 1 y -1, lo que se conoce como factor de
balance (FB) y representa la diferencia entre
las alturas de sus subárboles.
– FB=0, alturas de los subárboles iguales.
– FB (+), sub-der, más grande
– FB (-), sub-izq, más grande
El TAD Arbol_AVL
• La especificación de TAD AVL, es
idéntica a la especificación del TAD
ABB. Se considera un cambio en las
postcondiciones de las operaciones de
INSERTAR y BORRAR, con el fin de
obtener un árbol que cumpla con las
reestricciones de altura.
Cómo se realiza la
Inserción en un AVL
• Se inserta como si fuera un ABB.
• Se verifica si se afecta el balanceo del
árbol, de acuerdo a las reglas de los
AVL.
– No provoca des-balanceo. Lo que implica
solo actualizar los FB.
– Se provoca un des-balanceo
Nodo Pivote
• La forma de detectar en que caso se hace o
no un balanceo, es a través de la búsqueda
de un nodo pivote.
• Es aquel que tiene un FB diferente del rango
válido (-1,0,+1) y es el más cercano de los
ancestros del nodo recién insertado.
• De acuerdo a lo anterior se pueden detectar
los casos que a continuación se presentan.
El AVL carece de pivote
• Esto significa que todos los ancestros
tienen un FB igual a cero. En este caso
el nuevo nodo no produce desbalance
y sólo deben ajustarse los FB de los
ancestros, volviéndose + o -.
0
+
0
0
0
0
0
0
0
0
0
+
0
EL AVL tiene pivote
• Y el nuevo nodo se ha insertado en el
subárbol más pequeño del pivote. En
este caso tampoco habrá desbalanceo,
ya que se igualan las alturas de los dos
subárboles, y se procede a ajustar los
FB de los ancestros a partir del pivote.
+
+
0
0
0
0
0
+
0
0
0
0
+
+
0
0
EL AVL tiene pivote
• Y el nuevo nodo se ha insertado en el
subárbol más grande del pivote. En
este caso habrá desbalanceo, a partir
de ese nodo pivote y tendrá que
balancearse.
Avelson, Velinskii y Landis
• Detectaron que ante un problema de
desblance, todos los casos podía resolverse
aplicando uno de los cuatro esquemas de
balaceo, llamados rotaciones. Lo interesante
es que este tipo de proceso afecta solo los
nodos que forman parte del subárbol cuya
raíz es el nodo pivote. Dejando intactos los
nodos del resto del árbol.
Rotación Simple-Izquierda
c
Nodo pivote FB =-2
b
b
a
c
a
b es mayor que c c es mayor que b
Una rotación simple derecha es la misma
imagen vista a través de un espejo
Rotación Doble-Izquierda
a
Nodo pivote FB = 2
b
c
b
a
c
b es mayor que a pero menor que c
Una rotación doble derecha es la misma
imagen vista a través de un espejo
Rotación Simple - Derecha
a
b
b
a
A
c
c
A
B
C
D
B
C
D
Rotación Doble-Izquierda
c
a
a
b
b
A
c
C
B
D
A
C
D
B
Rotación Simple-Izquierda
• Implica el movimiento de tres apuntadores.
Resto del árbol
Resto del árbol
+ b
0
0
0
a
a
b
1
3
2
3
1
2
Una rotación simple derecha es la misma
imagen vista a través de un espejo
Rotación Doble-Izquierda
• Implica el movimiento de cinco apuntadores.
Resto del árbol
+
Resto del árbol
0
b
0
0
0
a
c
b
c
1
2
2
a
0
3
4
1
Una rotación doble derecha es la misma
imagen vista a través de un espejo
3
4
• Los árboles AVL son una estructura de datos importante. Estos
árboles no son aplicables a la mayoría de los problemas de
estructuras de archivos básicamente porque son árboles
estrictamente binarios y estos tienden a tener muchos niveles.
Sin embargo sugieren la posibilidad de mantener balanceado
el árbol de aquí que se pueda garantizar el tiempo de
búsqueda. Siempre y cuando estemos hablando de memoria
principal.
• En el caso de memoria secundaria un procedimiento que
requiere más de 5 accesos para encontrar una llave, es menos
que deseable, 20 o mas que inaceptable. Una búsqueda
binaria requiere muchos accesos y mantener un índice
ordenado es caro.
fin