almacenamiento y recuperacion de información- arbol avl ana lilia laureano cruces universidad...

Almacenamiento y Almacenamiento y Recuperacion de Recuperacion de

Información- Arbol AVLInformación- Arbol AVL

Almacenamiento y Almacenamiento y Recuperacion de Recuperacion de

Información- Arbol AVLInformación- Arbol AVL

Ana Lilia Laureano CrucesAna Lilia Laureano Cruces

Universidad Autónoma MetropolitanaUniversidad 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 -.

0000

00

0

0+00

-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+00

-0

+

0

++00

00

+

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

b

a

ca

b

b es mayor que c c es mayor que b

Nodo pivote FB =-2

Una rotación simple derecha es la misma imagen vista a través de un espejo

Rotación Doble-Izquierda

a

c

b

ca

bNodo pivote FB = 2

Una rotación doble derecha es la misma imagen vista a través de un espejo

b es mayor que a pero menor que c

Rotación Simple - Derecha

a b

cA

B

C D

ab c

A B C D

Rotación Doble-Izquierda

a

c

b ba

c

A

C D

BA BDC

Rotación Simple-Izquierda

• Implica el movimiento de tres apuntadores.

Resto del árbol

b

a1

2 3

+

0

Resto del árbol

a

b

1 2

3

0

0

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

b

a

1

2 3

+

0

Resto del árbol

c

b

2

0

0

Una rotación doble derecha es la misma imagen vista a través de un espejo

c

4

03

a

1 4

0

• 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.

finfinfinfin