ARBOLES BINARIOS

Definición
 Conjunto de nodos enlazados en el cual cada nodo tiene 0 o
más hijos y a lo mucho un padre
 Uno de los nodos es etiquetado como raíz, y no tiene padre
 Nodos sin hijos son llamados nodos hoja
 Un árbol binario tiene a lo mucho dos hijos (izquierdo y
derecho)
 Todos los hijos a la izquierda del nodo tienen valores menores
 Todos los hijos a la derecha del nodo tienen valores mayores

2
 Ejemplo

3
 Beneficios
 Eficiente inserción, eliminación y búsqueda
 Tiempo de búsqueda es directamente proporcional a su
altura: O(h)
 En árboles balanceados , la altura del árbol es O(log N)
 En ciertas circunstancias, la altura del árbol puede degenerar,
conduciendo al peor caso: O(N)

4
 Búsquedas en un árbol binario

5
 Mínimo
 El mínimo de un árbol binario de búsqueda es el nodo con el
valor más pequeño
 Para encontrar el mínimo basta con seguir los enlaces
izquierda a partir de la raíz del árbol para encontrar el nodo
con el valor más pequeño. El mínimo es el nodo más a la
izquierda del árbol.

6
 Máximo
 El máximo es el nodo con el valor más alto. Encontrar el
máximo es muy similar a encontrar el mínimo, siguiendo los
enlaces derechos en lugar de los izquierdos. El máximo es el
nodo más a la derecha del árbol.

7
 Sucesor
 El sucesor de un nodo es el siguiente valor mas alto en el árbol
 Implica dos casos:
1. Si un nodo tiene un hijo derecho, entonces el sucesor es el mínimo
de aquel
2. Si el nodo no tiene un hijo derecho, entonces se busca hacia atrás
hasta encontrar un nodo que sea hijo izquierdo, y entonces se usa su
padre

8
 Predecesor
 El predecesor de un nodo es aquel con el anterior valor más
pequeño
 El algoritmo es esencialmente el inverso del sucesor
 Implica dos casos:
 Si el nodo tiene un hijo izquierdo, entonces se toma su máximo
 Si no tiene un hijo izquierdo, se busca hacia atras hasta
encontrar un nodo hijo izquierdo

9
 Inserción
 La operación de inserción es bastante idéntica a la búsqueda,
excepto que cuando el valor no existe, se añade al árbol
 Este ingresa como nodo hoja

10
 Inserción
 La inserción en el árbol de números aleatorios usualmente
mantiene la altura del árbol como O(log N)
 ¿Qué sucede si se insertan datos de manera ordenada?, como
a partir de un diccionario o guía telefónica?

11
 Inserción
 En caso de una inserción ordenada, la búsqueda en el árbol
degenerará e una lista enlazada
 La altura y promedio de búsqueda será equivalente a O(N)

12
 Inserción
 Incluso, al tener los datos ordenados y generar un árbol que
tienda a crecer de manera no equilibrada se pueden aplicar
ajustes
 Estos ajustes son mecanismos para mantener el balance del
árbol: árboles rojo y negro, árboles AVL, etc.

13
 Eliminación
 Se consideran 3 casos para el proceso de eliminación
1. Si el nodo a ser eliminado no tiene hijos
2. Si el nodo a ser eliminado tiene un hijo (izquierdo o derecho)
=> Se remplaza el nodo con uno de sus hijos
3. Si el nodo a ser eliminado tiene dos hijos => Se intercambia
el nodo con su sucesor y se procede de nuevo con el caso 1 o
2

14
 Caso 1:nodo sin hijos
 Se deseenlaza el nodo del padre y se elimina

15
 Caso 2: nodo con un hijo
 El padre del nodo a ser eliminado apunta al nodo hijo

16
 Caso 3: nodo con dos hijos
 Encontrar el sucesor del nodo a ser eliminado ( o el
predecesor)

17
 Reemplazo de subárboles
 Para realizar reemplazos dentro de un árbol binario, se puede
aplicar la rutina TRANSPLANTE
 Esta rutina reemplaza un subárbol como un hijo de nodo
padre con otro subárbol

18
 Casos de eliminación
a) El nodo z a eliminar no tiene hijo izquierdo => se
remplaza z por su hijo derecho r

b) El nodo z a eliminar tiene un hijo izquierdo l y ningún hijo

derecho => se remplaza z por l

19
 Casos de eliminación
c) El nodo z a eliminar tiene 2 hijos, como en el caso de la
figura=> se remplaza z por y, actualizando el hijo
izquierdo de y para que sea de l, y dejando x como hijo
derecho de y

20
 Casos de eliminación
d) El nodo z a eliminar tiene 2 hijos, como en el caso de la
figura=> se remplaza y por su hijo izquierdo x y se
establece a y como padre de r. Luego, se establece a y
como hijo de q y padre de l

21
 Pseudocódigo de eliminación

22
 Recorridos
 Proceso de visitar cada del árbol exactament una vez
 Tipos de órdenes de recorrido:
Preorden
Inorden
Postorden

23
 Recorrido pre-orden
 Pasos para realizar este tipo de recorrido:
1. Visitar la raíz
2. Recorren el subárbol izquierdo en pre-orden
3. Recorrer el subárbol derecho en pre-orden

24
 Recorrido in-orden
 Pasos para realizar este tipo de recorrido:
1. Se recorre el subárbol izquierdo en in-orden
2. Se visita la raíz
3. Se recorre el subárbol derecho en in-orden

D BA G E H C F

25
 Recorrido post-orden
 Pasos para realizar este tipo de recorrido:
1. Se recorre el subárbol izquierdo en post-orden
2. Se recorre el subárbol derecho en post-norden
3. Se visita la raíz

D B G H E F CA

26
 Ejercicios
1. Construir un árbol binario de búsqueda para las siguientes
listas:
1.1 12, 34, -9, 12, 19, 23, 6, -4 (no permite repetidos)
1.2 80, 90, 34, 654, -23, -87, 5 (no permite repetidos)
1.3 Z, G, K, N, U, W, T, A ,U, S (si permite repetidos)
1.4 D, W, Q, N, D, W, S,Y, N, F (si permite repetidos)
2. Dado el árbol siguiente, elimine los elementos: 5, 10, 40,
8.

27
 3. Proporcionar un versión recursiva de la función TREE-INSERT
4. ¿Es la operación de eliminación “conmutativa” en el sentido que
eliminando x y luego y de un árbol binario de búsqueda se
obtiene el mismo árbol que eliminando primero y y luego x?.
Argumente su respuesta
5. Suponer que en lugar de mantener en cada nodo x el atributo
x.p, señalando al padre de x, se mantiene x.succ señalando al
sucesor de x. Proporcionar un pseudocódigo para las
operaciones de búsqueda, inserción, y eliminación en un BST
usando esta representación (se podría implementar una
subrutina que devuelva el padre de un nodo)

28
 Ejercicios
6. Si un nodo z en un árbol binario tiene dos hijos, se puede
elegir un nodo y como su predecesor en lugar de su
sucesor. Qué otros cambios al método TREE-DELETE
serían necesarios si se hiciera ello?. Algunos argumentan
que una buena estrategia es dar igual prioridad al
predecesor y sucesor, y procurar un mejor desempeño
empírico. Cómo podría el método TREE-DELETE ser
modificado para implementar tal estrategia?
7. ¿Cuál es máximo número de nodos que pueden ser
almacenados en un árbol binario con 10 niveles?
8. ¿Cuál es el mínimo número de niveles en un árbol binario
conteniendo 6023nodos?

29
 Ejercicios
9. Una base de datos se va a desarrollar para realizar un
seguimiento de información de estudiantes en una
universidad. Nombres, números de identificación, y los
promedios de calificaciones serán incluídos.La información
será accedida por un campo clave, que viene a ser el
nombre del estudiante. Codificar una clase llamada Listing
que defina los nodos. La clase debe proporcionar
operaciones para buscar información en el árbol por una
variedad de datos, insertar, eliminar, actualizar, y listar
información. El programa debe proporcionar un menú para
operar las operaciones

30
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.
32
 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

33
 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

34
 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

35
 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

36
 ¿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

37
 ¿AVL?

38
 Ejemplo: 1

39
 Ejemplo: 1

40
 Ejemplo: 2

41
 Ejemplo: 2

42
 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

43
 Declaración de un AVL

44
 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)

45
 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

46
 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

47
 Ejemplo: rotación luego de inserción

48
 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

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

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

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

52
 Rotación LR o rotación doble derecha

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

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

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

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

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

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

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

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

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

62
 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

63
 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

64
 Rotaciones tipo R
 Rotación R0

65
 Rotación R0
 Ejemplo

66
 Rotaciones tipo R
 Rotación R1

67
 Rotación R1
 Ejemplo

68
 Rotaciones tipo R
 Rotación R-1

69
 Rotación R-1
 Ejemplo

70
 Rotaciones tipo L

71
 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

72
 Ejercicios
 Equilibrar el siguiente árbol

73
 Ejercicios
 Considerando el árbol dado, eliminar el nodo 5

 Considerando el árbol dado, eliminar el nodo 6

74
 Ejercicios
 Considerando el árbol dado, eliminar el nodo 96

 Considerando el árbol dado, eliminar el nodo 65

75
 Ejercicios
 Considerando el árbol dado, eliminar el nodo 67

76