ARBOLES AVL

Creadores
Georgi Maksímovich Adelsón-Velski es un
científico de la computación y matemático ruso. Junto
con Landis ideó en 1962 el árbol AVL, primer árbol
binario autoajustable

Yevgeni Mijáilovich Landis fue un matemático soviético nacido

en Járkov, Ucrania. Es conocido en el mundo de la computación por
idear junto a Georgi Adelsón-Velski el primer árbol binario de
búsqueda auto-balanceable, el árbol AVL.
Cuando Landis tenía cuatro años su familia fue a vivir a Moscú.
Desde el instituto demostró su interés por las matemáticas. Solicitó
su acceso al Departamento de Matemáticas y Mecánica de
la Universidad Estatal de Moscú, donde fue admitido en 1939.
Poco después fue reclutado por el ejército ruso para combatir en
la Segunda Guerra Mundial, donde fue hecho prisionero. En varias
ocasiones fue herido y sufrió importantes congelaciones, estando al
borde de la muerte. En 1945 fue liberado y volvió a la universidad.
2
 Balanceo
 Una de las tareas más dificiles es detectar el desbalance de un árbol
 Una manera simple de mantener un árbol binario balanceado es
verificar la altura de cada subárbol
 Si dos hermanos difieren en altura en más de 1, entonces está
desbalanceado

3
 Definición
 Es un árbol el cual en cada uno de sus nodos, las alturas de
sus subárboles izquierdo y derecho difieren como máximo en
1 unidad
 Un árbol vacío es un árbol AVL
 Si T es un árbol no vacío y Tl y Tr son subárboles => T es
AVL si y solo si:
 Tl es AVL
 Tr es AVL
 |h(Tl) – h(Tr)| <=1
 Búsqueda, inserción y borrado ~ O(log N), donde N es el
número de nodos

4
 Factor de balanceo
• El factor de balanceo de un nodo u, denotado como bf(u) puede
definirse como:
 bf(u) = h(uL) – h(uR), donde h(uL) es la altura izquierda del
subárbol de u, y h(uR) es la altura del subárbol derecho de u
• Cada nodo u de un árbol AVL puede tener un factor de balanceo
bf(u) de -1 o 0 o +1
• Los factores de balanceo se indican entre paréntesis al lado de
cada nodo
• Con el fin de facilitar las operaciones de inserción e eliminación
de manera eficiente, un campo adicional llamado factor de
balanceo bf puede ser añadido con la estructura del nodo

5
 Factor de balanceo
 Valores de bf:
• Si bf = 0, los subárboles izquierdo y derecho tienen la misma
altura
• Si bf = 1, el árbol está equilibrado en altura, pero el subárbol
derecho es un nivel más alto
• Si fe = -1, el árbol está equilibrado en altura, pero el subárbol
izquierdo es un nivel más alto

6
 ¿Cómo calcular el factor de balanceo?
 Se sigue el camino desde el nodo que fue insertado o eliminado
hasta el nodo raíz
• Guardar el camino en una pila
• Añadir un nuevo puntero a cada nodo que apunte al padre del nodo actual
 Al realizar una inserción o eliminación se debe volver a calcular el bf
 Bf se incrementa si:
 Se inserta un nodo en la rama derecha
 Se elimina un nodo de la rama izquierda
 Si se detecta cambio de altura, el recalculo se propaga hacia arriba
 Bf se decrementa si:
 Se inserta un nodo en la rama izquierda
 Se elimina un nodo de la rama derecha
 Si se detecta cambio de altura, el recalculo se propaga hacia arriba

7
 ¿AVL?

8
 Ejemplo: 1

9
 Ejemplo: 1

10
 Ejemplo: 2

11
 Ejemplo: 2

12
 Operaciones en AVL
 Al ser un árbol AVL un tipo de árbol binario de búsqueda, se
pueden aplicar las mismas operaciones de búsqueda,
inserción y eliminación, pero se deben considerar
mecanismos que garanticen el balanceo del árbol
 Se incluyen operaciones de rotación

13
 Declaración de un AVL

14
 Operación: Búsqueda
 Buscar un elemento en un árbol AVL es muy similar a la
operación de búsqueda de un BST
 La altura de un AVL árbol de búsqueda AVL de N elementos
es O(log N), y en consecuencia, el tiempo de complejidad de
una operación de búsqueda es también O(log N)

15
 Operación: Inserción
 La inserción de un elemento en el árbol AVL tiene el mismo
procedimiento de inserción dado en el árbol de búsqueda
binaria
 Pero, la inserción conduce a determinar el factor de balance
de un nodo
 En caso que los valores del factor de balance no fueran -1, 0-
+1 => hay que balancear el árbol

16
 Operación: Inserción
Aspectos .a tener en cuenta luego de realizar la operación de
inserción:
 El bf de un árbol desbalanceado puede estar solo entre -2, -1, 0,
+1, y +2
 Luego de la inserción, los nodos con bf igual a -2 o +2 =>
indican que su anterior bf fue -1 o +1 respectivamente
 La inserción afecta el bf de los nodos que están solamente en el
camino desde la raíz al nuevo nodo insertado
 El antecesor más cercano del nuevo nodo insertado cuyo bf es
+2 o -2 inicia la rotación

17
 Ejemplo: rotación luego de inserción

18
 Inserción: rotaciones
 En un árbol AVL, si antes de la inserción, los bf de los nodos desde la
raíz hasta el nodo donde será insertado el nuevo fue 0, entonces el árbol
no llegará a estar desbalanceado
 Si la inserción desbalancea a un árbol AVL, la altura del subárbol debe
ser ajustado por rotación con respecto a su antecesor más cercano
 Las rotaciones se clasifican en cuatro tipos:
 Rotación LL: el nuevo nodo es insertado como el subárbol izquierdo (L) del
subárbol izquierdo (L) de A
 Rotación LR: el nuevo nodo es insertado como el subárbol derecho (R) del
subárbol izquierdo (L) de A
 Rotación RR: el nuevo nodo es insertado como el subárbol derecho (R) del
subárbol derecho (R) de A
 Rotación RL: el nuevo nodo es insertado como el subárbol izquierdo (L) del
subárbol derecho (R) de A

19
 Rotación LL o rotación simple a la
derecha

20
 Rotación LL o rotación simple a la
derecha
Ejemplo 1

21
 Rotación LL o rotación simple a la
derecha
Ejemplo 2

22
 Rotación LR o rotación doble derecha

23
 Rotación LR o rotación doble derecha
Ejemplo 1

24
 Rotación LR o rotación doble derecha
 Ejemplo 2

25
 Rotación RR o rotación simple a la
izquierda

26
 Rotación RR o rotación simple a la
izquierda
Ejemplo 1

27
 Rotación RR o rotación simple a la
izquierda
Ejemplo 2

28
 Rotación RL o rotación doble a la
izquierda

29
 Rotación RL o rotación doble a la
izquierda
Ejemplo 1

30
 Rotación LR o rotación doble a la
izquierda
 Ejemplo 2

31
 Algoritmo inserción
Insert(T, element)
GETNODE(X)
DATA(X)=element
LCHILD(X)=RCHILD(X)=NULL and bf(x)=0
If the tree T is empty then
Set T to X.
Exit.
//when AVL search tree T is non empty.
Starting from the root search the place to insert the new element.
Identify the most recently seen node with balance factor of either −1 or +1 as the ancestor node A.
If the element already exists
Print “Insertion not possible as the element already exists”.
Exit.
If no ancestor node A exists then update the balance factors in the path from root and exit.
If ancestor node A is found then
If(bfA)=+1 and the new node is inserted in the right subtree of A) or (bf(A)=-1 and the node is inserted in the left subtree of A)then
bf(A)=0.
Update the balance factors of all the nodes on the path from A to the newly inserted node.
Exit.
Else
Recognize the type of imbalance at A and execute the appropriate rotation.
Update the balance factors of nodes in the path from new subtree root to the newly inserted node as needed by the rotation.
Reset the left and right subtrees of the corresponding nodes.
Exit
End.

32
 Operación: eliminación
 La eliminación de un nodo en un árbol AVL puede causar
desbalance
 Rotaciones son invocadas luego de la eliminación
 El factor de balance de algunos o todos los nodos incluidos en el
camino desde la raíz al padre del nodo eliminado pueden ser
alterados
 Observaciones:
• Si nodo borrado del subárbol derecho de p => bf(p) +1
• Si nodo borrado del subárbol izquierdo de p => bf(p) -1
• h(árbol) -1 si el nuevo bf(p) = 0
• h(árbol) no se altera si el nuevo bf(p) = +1 o -1
• Si bf(p) = +2 o -2 => invocar rotaciones

33
 Eliminación: rotaciones
 Rotaciones tipo R: si la eliminación procede del subárbol derecho
de A (se considera que se tiene un subárbol izquierdo con raíz B)
• R0: si bf(B) = 0
• R1: si bf(B) = +1
• R-1: si bf(B) = -1
 Rotaciones tipo L: si la eliminación procede del subárbol izquierdo
de A (se considera que se tiene un subárbol derecho con raíz B)
• L0: si bf(B) = 0
• L1: si bf(B) = +1
• L-1: si bf(B) = -1

34
 Rotaciones tipo R
 Rotación R0

35
 Rotación R0
 Ejemplo

36
 Rotaciones tipo R
 Rotación R1

37
 Rotación R1
 Ejemplo

38
 Rotaciones tipo R
 Rotación R-1

39
 Rotación R-1
 Ejemplo

40
 Rotaciones tipo L

41
 Ejercicios
 En el AVL siguiente Insertar la secuencia: 38, 20, 57, 47 y 46

 Insertar en un AVL vacío: 40, 33, 46, 6, 8, 24, 18, 22, 25 y

60

42
 Ejercicios
 Equilibrar el siguiente árbol

43