Download ELO-320 Arboles binarios AVL

ELO320 Estructuras de Datos y Algoritmos
Arboles Binarios AVL
Tomás Arredondo Vidal
Este material está basado en:
❒ Robert Sedgewick, "Algorithms in C", (third edition), Addison-Wesley, 2001
❒ Thomas Cormen et al, “Algorithms”, (eighth edition), MIT Press, 1992.
❒ material del curso ELO320 del Prof. Leopoldo Silva
❒ material en el sitio http://es.wikipedia.org
13: Arboles AVL
1
13-Árboles Binarios AVL
13.1 Definiciones y tipos de datos
13.2 Cálculos de complejidad
13.3 Análisis de inserción
13.4 Análisis de descarte
13.5 Análisis de rotación
13: Arboles AVL
2
Definiciones
❒ El alto de un árbol es el largo de la trayectoria más larga de una
❒
❒
❒
❒
hoja hasta la raíz.
Adel'son-Vel'skii y Landis (1962) definieron árboles AVL en los
cuales, para cada nodo, el alto del subárbol derecho difiere del
alto del subárbol izquierdo a lo más en uno.
El desarrollo del algoritmo muestra la necesidad de un análisis
exhaustivo de los diferentes casos que se presentan.
Se define el factor de balance como el alto del subárbol derecho
menos el alto del subárbol izquierdo.
Entonces en un árbol AVL, todos los nodos cumplen la propiedad
de tener valores del factor de balance iguales a: -1, 0, ó +1.
13: Arboles AVL
3
13-Árboles Binarios AVL
13.1 Definiciones y tipos de datos
13.2 Cálculos de complejidad
13.3 Análisis de inserción
13.4 Análisis de descarte
13.5 Análisis de rotación
13: Arboles AVL
4
Complejidad: árboles AVL
❒ Sea nh el número de nodos en ❒ n0= 1
un árbol AVL de altura h
dada, que esta en su peor
❒ n1= 2
caso de desbalance.
❒ Los siguientes diagramas
ilustran dichos árboles y los
factores de balance de sus
❒ n2 = 4
nodos
n2=n1+n0+1
❒ Se muestran los casos
desbalanceados por la
derecha, los de la izquierda
son especulares.
❒ Lo que se desea encontrar es ❒ n3 = 7
n3=n2+n1+1
la altura h de todos los
árboles AVL de n nodos con
su máximo grado de
desbalance.
h=2
13: Arboles AVL
5
Complejidad: árboles AVL II
❒ Mediante inducción puede
❒ n4 = 12
demostrarse que en general n4= n3 + n2 + 1
para un árbol AVL (con
máximo grado de desbalance
+1 o -1):
nh = nh-1 + nh-2 + 1
Dado n0 = 1 y n1 = 2
❒ Lo que implica que un árbol
AVL está formado por dos
subárboles AVL.
❒ La secuencia generada es
nh = 1, 2, 4, 7, 12, 20, 33, 54…
para h = 0, 1, 2, 3….
h=4
13: Arboles AVL
6
Complejidad: árboles AVL III
❒ La secuencia generada es
nh = 1, 2, 4, 7, 12, 20, 33, 54… para h = 0, 1, 2, 3….
❍ Como la secuencia de Fibonnaci
Fn = Fn-1 + Fn-2, F0 = 0 y F1 = 1
❒ Evaluando numéricamente (e.g. Maple evalf):
n(h) = 1.894427191(1.618033988)h + 0.1055728091(-.6180339886)h - 1
❒ El segundo termino tiende a cero, resolviendo numéricamente (e.g.
Maple solve):
h(n) = 2.078086923ln (.5278640450 n)
❒ Para acotar por arriba, se desea encontrar el valor de la constante c
que satisface: c*log2(n)=2.078086923*ln(.5278640450*n)
13: Arboles AVL
7
Complejidad: árboles AVL IV
❒ Usando un método numérico:
c=1.440420092
❒ Finalmente la altura en un árbol AVL
queda acotada por:
1.440420092*log2(n) > h(avl) > h(bst)
❒ Lo cual demuestra que:
h(avl) = Θ(log2(n))
❒ Graficando el alargue vs un árbol
binario balanceado dado n:
2.078086923ln (.5278640450 n) / log2(n)
13: Arboles AVL
8
13-Árboles Binarios AVL
13.1 Definiciones y tipos de datos
13.2 Cálculos de complejidad
13.3 Análisis de inserción
13.4 Análisis de descarte
13.5 Análisis de rotación
13: Arboles AVL
9
Análisis de inserción
❒ La función de inserción debe ser
modificada para mantener la propiedad
de árbol AVL.
❒ Existen inserciones que sólo implican
recalcular los factores de balance, ya
que el árbol sigue siendo AVL.
❒ Por ejemplo las dos inserciones sólo
modifican los factores de balance de
algunos nodos ancestros del insertado,
que están en la trayectoria del recién
insertado hacia la raíz.
❒ Se van a mostrar dos casos de
inserción por la izquierda, existen
casos equivalentes (especulares) de
inserción por la derecha.
13: Arboles AVL
10
Análisis de inserción: caso a
❒ a) Al insertar por la izquierda, y en el proceso de ascenso, por la
trayectoria desde el nodo recién insertado hacia la raíz, revisando los
factores de balance, si se llega a un nodo con factor uno, basta corregir
el factor de ese nodo (quedando éste en 0) y no es preciso seguir
corrigiendo en el ascenso. Esto debido a que ese nodo no cambiará su
altura; estaba en h y queda en h.
❒ Se ilustra este caso a continuación:
13: Arboles AVL
11
Análisis de inserción: caso b
❒ b) Al insertar por la izquierda, y en el proceso de ascenso de revisión
de los factores de balance, si se llega a un nodo con factor cero, debe
corregirse el factor de ese nodo (quedando éste en menos uno) y es
preciso seguir el ascenso corrigiendo factores de balance. Esto debido
a que ese nodo cambió su altura; estaba en h y queda en h+1.
❒ Se ilustra este caso a continuación:
13: Arboles AVL
12
Análisis de inserción: caso c
❒ Se analiza un árbol AVL de altura dos, pero el
❒
❒
❒
❒
análisis es válido para cualquier subárbol AVL.
Se escoge un caso sencillo para extraer el caso
general:
c) Si se inserta nodo F, en la rama externa más
larga del subárbol derecho: La relación de orden
del árbol binario es: A<B<C<D<E<F
Se trata igual el caso: F<E.
Se detecta la pérdida de propiedad AVL, para
este caso, cuando el factor de balance de un
nodo recalculado después de la inserción es +2, y
el factor de balance del hijo derecho de éste es
positivo.
Inserciones de nodos con valores menores que
B, mejoran los factores de balance, mantienen la
propiedad AVL, y no existe necesidad de
corregir. Han sido tratados en los casos a y b.
13: Arboles AVL
13
Análisis de inserción: caso d
❒ d) Si se inserta nodo D, en la rama
interna más larga del subárbol
derecho. Con orden: A<B<C<D<E<F
❒ Se trata igual el caso D<C.
❒ Esta situación se detecta cuando el
factor de balance de un nodo es +2, y
el factor de balance del hijo derecho
de éste es negativo.
❒ Inserciones de nodos con valores
menores que B, mejoran los factores
de balance, mantienen la propiedad
AVL, y no existe necesidad de
corregir.
13: Arboles AVL
14
Corrección para mantener AVL: caso c
❒ El caso c) requiere una reestructuración de los nodos
para mantener la propiedad AVL. Manteniendo la
relación de orden: A<B<C<D<E<F, se denomina rotación
simple a la izquierda, la que deja al subárbol, según:
13: Arboles AVL
15
Corrección para mantener AVL: caso d
❒ El caso d) también requiere reestructurar para mantener el árbol con
la propiedad AVL.
❒ Se corrige con una doble rotación. Primero una a la derecha, que hace
ascender C y luego otra a la izquierda, que hace ascender C hasta la
raíz:
❒ En ambas se conserva la relación de orden: A<B<C<D<E<F
❒ Existen dos casos adicionales al c) y el d), que corresponden a
inserciones por la izquierda, y pueden visualizarse con las imágenes
especulares de las mostradas.
13: Arboles AVL
16
Rotaciones en AVL: generalización caso c
❒ Se puede generalizar, el caso c). La primera figura muestra
la situación antes de agregar un nodo en el subárbol
derecho de B. La figura al centro muestra el árbol
desbalanceado, no AVL. A la derecha se muestra después
de una rotación simple a la izquierda, la cual mejora el
balance y genera un árbol AVL.
13: Arboles AVL
17
Rotaciones en AVL: generalización caso d
❒ El caso d) también se puede generalizar. La primera figura muestra la
situación antes de agregar un nodo en el subárbol izquierdo o derecho
del nodo B. La segunda figura muestra el árbol no AVL:
13: Arboles AVL
18
Rotaciones en AVL: generalización caso d
❒ Lo cual se corrige, con una rotación a la derecha, que hace ascender B
y luego otra a la izquierda para llevar B a la raíz del subárbol,
produciendo un árbol AVL.
❒ No es necesario seguir revisando los factores de balance de los nodos
superiores a la raíz del subárbol, ya que éste queda con factor de
balance 0. El alto de ese nodo es (h+1), antes y después de la inserción
y las correcciones.
13: Arboles AVL
19
13-Árboles Binarios AVL
13.1 Definiciones y tipos de datos
13.2 Cálculos de complejidad
13.3 Análisis de inserción
13.4 Análisis de descarte
13.5 Análisis de rotación
13: Arboles AVL
20
Análisis de descarte: caso a
❒ Se descarta en forma similar a un árbol binario. Sin embargo, debido a
la propiedad AVL, si el nodo a descartar tiene un solo subárbol
(derecho o izquierdo), ese subárbol debe ser una hoja.
❒ Luego del descarte, debe ascenderse para mantener los factores de
balance de la trayectoria hacia la raíz, hay varios casos de esto.
Debido a simetría sólo se analizan casos de descarte por la izquierda.
❒ Caso a) Al descartar por la izquierda, y en el proceso de ascenso de
revisión de los factores de balance, si se llega a un nodo con factor
cero, basta corregir el factor de ese nodo (quedando éste en +1) y no
es preciso seguir el ascenso. Esto debido a que ese nodo no cambiará
su altura; estaba en h y queda en h.
13: Arboles AVL
21
Análisis de descarte: caso b
❒ Caso b) Al descartar por la izquierda, y en el proceso de revisión de los
factores de balance, si se llega a un nodo con factor menos uno, se
debe corregir el factor de ese nodo (quedando éste en cero) y es
preciso seguir revisando en la vía de ascenso. Esto debido a que ese
nodo cambió su altura de (h+1) a h.
13: Arboles AVL
22
Análisis de descarte: caso c
❒ En la situación de la figura a la izquierda, se descarta por la izquierda.
La figura central muestra la situación, y la necesidad de rebalancear
por pérdida de propiedad AVL. Lo cual se logra con una rotación a la
izquierda, que se muestra en la figura de la derecha, generando un
árbol AVL. No es preciso seguir la revisión ascendente, ya que el
subárbol, no cambia su altura.
13: Arboles AVL
23
Análisis de descarte: caso d
❒ En la situación de la figura a la izquierda, se descarta por la izquierda.
La figura central muestra la situación, y la necesidad de rebalancear
por pérdida de propiedad AVL. Lo cual se logra con una doble rotación
(primero a la derecha, luego a la izquierda). Es preciso seguir la
revisión ascendente, ya que el subárbol, cambia su altura de (h+1) a h.
13: Arboles AVL
24
Análisis de descarte: caso e
❒ En la situación de la figura a la izquierda, se descarta por la izquierda.
La figura central muestra la situación, y la necesidad de rebalancear
por pérdida de propiedad AVL. Lo cual se logra con una rotación a la
izquierda. Es preciso seguir la revisión ascendente, ya que el subárbol
cambia su altura, de (h+1) antes del descarte a h.
❒ Se puede discernir entre los casos d y e, observando el hijo derecho
del nodo que pasó a tener factor de balance dos. Esto implica que la
función descartar debe analizar 10 casos. Cinco en descartes por la
izquierda y 5 por la derecha.
13: Arboles AVL
25
13-Árboles Binarios AVL
13.1 Definiciones y tipos de datos
13.2 Cálculos de complejidad
13.3 Análisis de inserción
13.4 Análisis de descarte
13.5 Análisis de rotación
13: Arboles AVL
26
Análisis de rotación: simple a la izquierda
❒ Al inicio t apunta a la raíz del subárbol.
❒ Luego de temp = t y t = t->right, queda la figura de la izquierda.
❒ Luego de temp->right = t->left; y t->left = temp queda la figura de la
derecha.
❒ La corrección de los factores de balance se puede efectuar según:
temp->bal =0 y t->bal =0
13: Arboles AVL
27
Análisis de rotación: rutina general
❒ Para lograr una rutina general de rotación se analiza la siguiente
situación.
❒ Sean a, b y c los altos de los subárboles, que no cambian.
❒ Antes de la rotación, los factores de balance de los nodos A y B son x e
y, respectivamente; luego de la rotación éstos se denominan: nA y nB.
❒ Se desea determinar
nA y nB en términos de x e y.
❒ La rotación simple a la derecha es la imagen especular de este caso.
13: Arboles AVL
28
Análisis de rotación: calculo de nA
❒ En la figura izquierda se cumple: y = c-b, x=b+1-a si b>c, o x=c+1-a si c>b
❒ En la figura de la derecha se cumplen, por la definición del factor de
balance: nA= b-a, nB= c-1-a si a>b, o nB=c-1-b si b>a.
❒ Cálculo de
nA:
b>c, remplazando se obtienen: nA=x-1-0 o bien para c>b: nA=x-1-y
❒ Las últimas dos ecuaciones pueden anotarse: nA=x-1-max(y,0)
❒ Para
❒ Calculo de nB:
a>b, se tiene nB=x-2+y o si b>c se tiene nB=x-2+0. Las dos
relaciones anteriores pueden anotarse: nB=x-2+min(y, 0)
❒ Para
❒ Juntando ambos resultados: nB = min(x-2+min(y,0), y-1)
13: Arboles AVL
29
Análisis de rotación: código
❒ El siguiente segmento corrige factores de balance en una
rotación simple a la izquierda:
x = temp->bal; // oldbal(A)
y = t->bal; // oldbal(B)
temp->bal = x-1-max(y, 0); // newbal(A)
t->bal = min(x-2+min(y, 0), y-1); // newbal(B)
Los siguientes macros implementan min( ) y max( )
# define max(A,B) ((A)>(B)?(A):(B)) /* Definición de macros */
# define min(A,B) ((A)>(B)?(B):(A))
❒ Para el resto del código ver: avl-tree.c
13: Arboles AVL
30