unidad 4 algoritmos y estructuras de...
TRANSCRIPT
![Page 1: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/1.jpg)
Unidad 4
Algoritmos y Estructuras de Datos
Estructuras para Árboles
![Page 2: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/2.jpg)
Árboles
![Page 3: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/3.jpg)
Definiciones
Son de una de las estructuras de datos mas utilizadas
Dentro de la computación tienen, entre otras las
siguientes aplicaciones:
Organizar tablas
Asignación de bloques de memoria
Búsqueda
Ordenamiento
![Page 4: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/4.jpg)
Definición
Un árbol es un conjunto finitoT de uno o mas nodos tal que:
Existe un nodo especial llamado raíz
Los nodos restantes están particionados en m>0 conjuntos
disjuntosT1,…Tm y cada uno de estos conjuntos es un árbol
![Page 5: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/5.jpg)
Representación grafica
Conjuntos anidados
![Page 6: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/6.jpg)
Representación grafica
Paréntesis anidados:
(1(2(4(9,10,11),5),3(6(12),7,8)))
Indentacion:
![Page 7: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/7.jpg)
Representación grafica
La forma mas común es un grafo con la raíz hacia arriba:
![Page 8: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/8.jpg)
Propiedades Cada vértice o nodo puede tener un nombre y una
información asociada
Un camino es una lista de vértices diferentes en los quevértices sucesivos están conectados por arcos en el árbol
La longitud de un camino es el número de nodos del caminomenos uno. Por tanto, hay un camino de longitud cero decualquier nodo a si mismo
![Page 9: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/9.jpg)
Propiedades Un nodo Y está abajo de un nodo X, si X está en el camino de
Y a la raíz
Cada nodo, excepto la raíz, tiene exactamente un nodo arribade él, que es llamado su padre
Los nodos que están exactamente abajo de él son llamadossus hijos
El número de hijos que cuelgan de un nodo es llamado elgrado del nodo
![Page 10: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/10.jpg)
Propiedades
El grado de un árbol es el grado máximo de los nodos del
árbol
Un nodo de grado cero es llamado hoja, es decir, no tiene
hijos
![Page 11: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/11.jpg)
Ejemplo
•Muestre el camino del nodo A al nodo P e indique la longitud del camino
•¿Cuáles son las hojas del árbol?
•Muestre los nodos de grado 1, 2 y 3
•¿Cuál es el grado del árbol?
![Page 12: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/12.jpg)
SOLUCIÓN
El camino del nodo A al nodo P es (A, B, D, J, P), cuya longitud
de camino es 4
Las hojas son: I, P, K, L, F, M, N, O y H
El único nodo de grado 1 es J.
Los nodos de grado 2 son A, B, D y E.
Los nodos de grado 3 son C y G.
No existen nodos de mayor grado, por tanto, el grado del
árbol es 3.
![Page 13: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/13.jpg)
Propiedades
El nivel de un nodo es el número de nodos en el camino de él
hacia la raíz
La altura de un árbol es el nivel máximo de todos los nodos
en el árbol
![Page 14: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/14.jpg)
Ejemplo
La altura del árbol es 4
![Page 15: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/15.jpg)
Bosques
Un conjunto de árboles es llamado bosque
Si se elimina la raíz de un árbol, se convierte en un bosque
Si se aumenta un nodo a un bosque, se convierte en árbol
![Page 16: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/16.jpg)
Árboles Binarios de Búsqueda (ABB)
![Page 17: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/17.jpg)
Definiciones
Son el caso particular mas simple
Definición:
Un conjunto T de elementos es un árbol binario de búsqueda
si:
T es vació
T esta particionado en 3 conjuntos disjuntos
![Page 18: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/18.jpg)
Definiciones
Esos tres conjuntos son:
Un solo elemento llamado la raíz
2 conjuntos que son ABB, llamados subárbol izquierdo y
subárbol derecho
![Page 19: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/19.jpg)
Definiciones
Donde n es un nodo y TD y TI son árboles binarios, además
de cumplir con las siguientes propiedades:
La llave de búsqueda (el valor) de n es MAYOR que todas las
llaves de búsqueda de TI
La llave de búsqueda (el valor) de n es MENOR que todas las
llaves de búsqueda de TN
![Page 20: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/20.jpg)
Representación
La forma mas simple de representar un árbol binario es la
ligada:
![Page 21: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/21.jpg)
Ejemplo
Representación ligada
![Page 22: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/22.jpg)
Operaciones con un ABB
Inserción
Búsqueda
Eliminación
Recorridos
![Page 23: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/23.jpg)
Inserción
Insertar el elemento X
Si el árbol esta vació, X será la raíz del árbol
Si no esta vació se compara el valor de X con el del nodo
padre:
Si es menor se inserta como un hijo izquierdo
Si es mayor se inserta como hijo derecho
![Page 24: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/24.jpg)
Inserción, Ejemplo
Crear un ABB insertando los siguientes elementos: 10, 8, 14,
12, 9, 17, 5, 7, 11, 16, 13, 3, 21
![Page 25: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/25.jpg)
Búsqueda
Para buscar al elemento X:
Si X es la llave de la raíz de un ABB se ha terminado.
Si X es menor que el padre, se busca a la izquierda
Si X es mayor que el padre, se busca a la derecha
![Page 26: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/26.jpg)
Búsqueda, Ejemplo
Si se busca el elemento “7”:
Se compara 7 con 10 y se desciende por la izquierda
Se compara 7 con 8 y se desciende por la izquierda
Se compara 7 con 5 y se desciende por la derecha
Se encuentra la llave deseada
![Page 27: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/27.jpg)
Eliminación
Eliminación de un elemento X
Si el elemento se encuentra, existen tres posibilidades:
El elemento es una hoja
Tiene un hijo único
Tiene dos hijos
![Page 28: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/28.jpg)
Eliminación de una hoja
Caso mas sencillo, en donde lo único que hay que hacer es
que la liga que lo referencia debe ser nil
![Page 29: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/29.jpg)
Con un hijo único
Para eliminar un nodo, su padre deberá referenciar a su hijo
![Page 30: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/30.jpg)
Con un hijo único
Al eliminar la llave 4, se debe cambiar el subárbol izquierdo
de 5 por el que contiene a 2 como raíz
![Page 31: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/31.jpg)
Con un hijo único Es el mismo procedimiento para eliminar un nodo con un único hijo izquierdo
Al eliminar el nodo cuya información es 6, el subárbol izquierdo de 8
referenciará al subárbol derecho del 6 (nodo 7)
![Page 32: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/32.jpg)
Con dos hijos
Existen dos opciones:
Sustituir el valor de la información del nodo a eliminar por el
nodo que contiene la menor llave del subárbol derecho (Menor
de los mayores)
Sustituir el valor de la información del nodo a eliminar por el
nodo que contiene la mayor llave del subárbol izquierdo (Mayor
de los menores)
![Page 33: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/33.jpg)
Eliminación con dos hijos
Si se desea eliminar la raíz, se substituye el valor por la llave con el mayor de los menores y luego eliminar ese valor
O sustituir el valor por la llave con el menor de los mayores y luego eliminar ese valor
![Page 34: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/34.jpg)
Eliminación con dos hijos
Utilizando el mayor de los menores
![Page 35: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/35.jpg)
Eliminación con dos hijos
Utilizando el menor de los mayores
![Page 36: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/36.jpg)
Recorridos en un ABB
Existen tres maneras de recorrer un árbol binario de
búsqueda:
Preorden o previo
Inorden o simétrico
Postorden o posterior
La diferencia entre ellas es el orden en que se visitan los
nodos
![Page 37: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/37.jpg)
Recorridos Pre orden o previo
Visitar la raíz
Recorrer recursivamente el subárbol izquierdo
Recorrer recursivamente el subárbol derecho
Inorden o simetrico Recorrer recursivamente el subárbol izquierdo
Visitar la raíz
Recorrer recursivamente el subárbol derecho
Post orden o posterior Recorrer recursivamente el subárbol izquierdo
Recorrer recursivamente el subárbol derecho
Visitar la raíz
![Page 38: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/38.jpg)
Recorridos, Ejemplo
preorden:
20, 15 10, 5, 12, 18, 17, 19, 33, 25, 21, 27, 50, 40, 70
inorden:
5, 10, 12, 15, 17, 18, 19, 20, 21, 25, 27, 33, 40, 50, 70
postorden:
5, 12, 10, 17, 19, 18, 15, 21, 27, 25, 40, 70, 50, 33, 20
![Page 39: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/39.jpg)
Desempeño El peor caso en un ABB es cuando se insertan elementos que se
encuentran ordenados (ya sea de menor a mayor o viceversa)
Por esta razón su uso no es recomendable cuando se maneja información
extraída por ejemplo de un diccionario
![Page 40: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/40.jpg)
Desempeño
Si se insertan n elementos en un ABB de altura h:
El espacio utilizado en el peor de los casos es O(n)
Los métodos de inserción, búsqueda y eliminación son de
tiempo O(h)
La altura en el peor de los casos es O(n) y en el mejor de los
casos O(log n)
![Page 41: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/41.jpg)
Peor de los casos
![Page 42: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/42.jpg)
Montículo Binario
![Page 43: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/43.jpg)
Definición
Un Montículo Binario es un Árbol Binario Completo
Todos los niveles están llenos a excepción del nivel de hojas
Una característica es que los elementos izquierdo y derecho
deben ser mayores que su padre
Debido a la representación de árbol completo, un Montículo
Binario se representa como un arreglo
![Page 44: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/44.jpg)
Representación
Aquí la distribución de padres e hijos está dada por la
posición de cada elemento en el arreglo, de esta forma:
Un nodo padre en (i):
Tiene a un hijo izquierdo en (2*i + 1) si 2*i+1 < N
Tiene a un hijo derecho en (2*i + 2) si 2*i+2 < N
En donde:
N es el número de elementos
Un nodo hijo tiene a su padre en (i-1)/2 si i es distinto a 0
![Page 45: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/45.jpg)
Llenado
La representación más común de un Montículo Binario es a
través de un arreglo
Aquí, cada que se inserta un elemento, es necesario
compararlo con aquel, que de acuerdo a su posición sería su
padre
Si el padre es menor, es necesario intercambiar los elementos
y volver a comparar con quien ahora sería su nuevo padre
Así sucesivamente hasta que el padre ya no sea menor o el
elemento quede en la raíz
![Page 46: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/46.jpg)
Árboles Adelson-Velskii y Landis
(AVL)
![Page 47: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/47.jpg)
Definiciones Es un árbol binario de búsqueda equilibrado
Un árbol AVL es un ABB en donde las alturas de los hijos
izquierdo y derecho solo pueden diferir a lo máximo en uno
![Page 48: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/48.jpg)
Definiciones
![Page 49: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/49.jpg)
Operaciones con árboles AVL
Inserción
Búsqueda
Eliminación
Recorrido
Balanceo
![Page 50: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/50.jpg)
Operaciones Las operaciones de búsqueda y recorridos son las mismas que
para un ABB
Las operaciones de inserción y borrado de un elemento son
las mismas, con la excepción de que después de ejecutarlas
requieren una operación de balanceo
![Page 51: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/51.jpg)
Balanceo Tras una inserción, los nodos pueden ver alterado su
equilibrio
Existen cuatro casos que se deben considerar:1. Una inserción en el subárbol izquierdo del hijo izquierdo de X.
2. Una inserción en el subárbol derecho del hijo izquierdo de X.3. Una inserción en el subárbol izquierdo del hijo derecho de X.
4. Una inserción en el subárbol derecho del hijo derecho de X.
![Page 52: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/52.jpg)
Balanceo
En el primer y cuarto caso, en donde la inserción se produce
en los márgenes, el balance se recupera con una rotación
simple.
![Page 53: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/53.jpg)
Balanceo simple El subárbol A ha crecido en un nivel, provocando que sea dos
niveles más profundo que C
Para re equilibrar de manera correcta el árbol, hay que subirA un nivel y bajar C
El resultado es que k1 será la nueva raíz
La propiedad de los árboles binarios de búsqueda indica queen el árbol inicial, k2 > k1, así que en el nuevo árbol k2 seconvierte en el hijo derecho de k1
![Page 54: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/54.jpg)
Rotación simple a la derecha
k 1
k 12k
2k
A
AB B
C
C
![Page 55: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/55.jpg)
Ejemplo
![Page 56: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/56.jpg)
Rotación simple a la izquierda
k 1
k 12k
2k
A
A
B BC
C
![Page 57: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/57.jpg)
Ejemplo
![Page 58: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/58.jpg)
Rotaciones dobles
La rotación simple tiene el problema de que no resuelve el
problema en los casos 2 y 3
Para resolver el problema se deben efectuar dos rotaciones
sencillas:
Una rotación simple entre el hijo de X y su nieto, seguida de
una rotación simple entre X y su nuevo hijo
![Page 59: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/59.jpg)
Rotación doble
k 1k 1
2k
2k3k
3k
A A
B
B
C
CD
D
![Page 60: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/60.jpg)
Rotación doble
k 1
k 1
2k
2k
3k3k
A
AB
B C
CDD
![Page 61: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/61.jpg)
Ejemplo
12 12
8
8
16 16
4 4
2 2
10
10
6
6
1414
5
5
![Page 62: Unidad 4 Algoritmos y Estructuras de Datosacademicos.azc.uam.mx/jfg/diapositivas/algoritmos_ed/Unidad_4.pdf · Llenado La representación más común de un Montículo Binario es a](https://reader034.vdocumento.com/reader034/viewer/2022042913/5f495fe3d3fe6e2ce86165bc/html5/thumbnails/62.jpg)
Desempeño
Al ser los árboles AVL balanceados, no importa en que orden
se ingresen las llaves, la altura siempre será de O(log n):
La altura mínima de un árbol AVL de n llaves es: piso |log n|
La altura máxima : techo|log n|+1