Diapositiva de prueba
Transcript of Diapositiva de prueba
![Page 1: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/1.jpg)
ARBOL
• Los árboles representan estructuras dinámicas de datos, debido a que pueden cambiar en tiempo de ejecución y no lineales puesto que a cada elemento del árbol pueden seguirle varios elementos.
![Page 2: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/2.jpg)
ÁRBOLES
• Un árbol es una estructura jerárquica aplicada
sobre una colección de elementos
u objetos llamados nodos; uno de los cuales es conocido
como raíz. Además se crea una relación de parentesco
entre los nodos dando lugar a términos como
padre, hijo, hermano, antecesor, sucesor, ancestro,etc.
• Formalmente se define un árbol de tipo T como
una estructura homogénea que es la concatenación
de un elemento de tipo T con un número finito de
arboles disjuntos llamados subárboles.
![Page 3: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/3.jpg)
E
G
KJI
A
B
D F
C
H
L
(A (B (D ( I ), E, F (J, K )), C (G, H ( L ))))
Diagramas de Venn
Anidación de paréntesis
FORMAS DE REPRESENTACION DE UN ÁRBOL
![Page 4: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/4.jpg)
Los árboles tienen una gran variedad de aplicaciones.
Para construir un árbol genealógico, para el análisis de circuitos eléctricos y
para numerar los capítulos y secciones de un libro.
Gráficamente puede representarse una estructura de diferentes formas y todas
ellas equivalentes.
Por medio de grafos, esta última representación es la que comúnmente se
utiliza; y ha originado el término árbol por su parecido abstracto con el
vegetal (raíz, ramas, hojas).
APLICACIONESA
B C
D E F G H
I J LK
![Page 5: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/5.jpg)
CARACTERÍSTICAS Y PROPIEDADES DE LOS ÁRBOLES
a) Todo árbol que no es vacío, tiene un único nodo raíz.
b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. En este caso es común utilizar la expresión X es hijo de Y.
c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. En este caso es común utilizar la expresión X es padre de Y.
d) Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son HERMANOS.
e) Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de TERMINAL u HOJA.
f) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de INTERIOR.
g) GRADO es el número de descendientes directos de un determinado nodo. GRADO DE ÁRBOL, es el máximo grado de todos los nodos del árbol.
h) NIVEL es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición, la raíz tiene en nivel 1.
i) ALTURA del árbol es el máximo número de niveles de todos los nodos del árbol.
![Page 6: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/6.jpg)
Ejemplo: ÁRBOL GENERAL.
Dado el árbol general de la figura de abajo, se hacen sobre él las
siguientes consideraciones.
1.- A es la raíz del árbol.
2.- B es hijo de A. C es hijo de A. D es hijo de B. E es hijo de B. L es hijo de H.
3.- A es padre de B. B es padre de D. D es padre de I. C es padre de G. H es padre de L.
4.- B y C son hermanos. D,E y F son hermanos. G y H son hermanos. J y K son
hermanos.
5.- I, E, J, K, G y L son nodos terminales u hojas.
6.- B, D, F, C y H son nodos interiores.
7.- El grado del nodo A es 2. B es 3. C es 2. D es 1. E es 0. El grado del árbol es 3.
8.- El nivel del nodo A es 1. B es 2. D es 3. C es 2. L es 4.
9.- La altura del árbol es 4.
A
B C
D E F G H
I J LK
![Page 7: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/7.jpg)
LONGITUD DE CAMINO (LC)
• Se define la longitud de camino X como el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. por definición la raíz tiene longitud de camino 1, sus descendientes directos 2…
• Por ejemplo el nodo I tiene una longitud de camino igual a 4
![Page 8: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/8.jpg)
• Es la suma de las longitudes de camino de todos los nodos del árbol, y se calcula por medio de la siguiente fórmula.
i= nivel del árbol
h= altura del árbol
Ni = número de nodos en el nivel i
h
i
i inLCI1
*
LONGITUD DE CAMINO
LONGITUD DE CAMINO INTERNO (LCI)
![Page 9: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/9.jpg)
i= nivel del árbol
h= altura del árbol
ni = número de nodos en el nivel i
LCI = 1x1 + 2x2 + 5x3 + 4x4
LCI= 36
A
B C
D E F G H
I J LK
Ejemplo
LONGITUD DE CAMINO INTERNO (LCI)
LONGITUD DE CAMINO
![Page 10: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/10.jpg)
• La media del longitud de camino se calcula con la siguiente formula
LCIM = LCI /N
LCIM= media de longitud de camino interno
N = número de nodos
LCIM = 36/12
LCIM= 3
LONGITUD DE CAMINO
MEDIA DE LONGITUD DE CAMINO INTERNO
A
B C
D E F G H
I J LK
![Page 11: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/11.jpg)
• ARBOL EXTENDIDOEs aquel en el que el número de hijos de cada nodos es igual al grado del árbolEn caso de que algún nodo no cumpla con esta condición se debe incorporar al mismo tantos nodos especiales como se requiera.
• NODOS ESPECIALESTienen como objetivo:– Remplazar las ramas vacías o nulas– No pueden tener descendientes– Se representa en forma de cuadrado.
LONGITUD DE CAMINO EXTERNO(LCE)
LONGITUD DE CAMINO
![Page 12: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/12.jpg)
Árbol general
LONGITUD DE CAMINO EXTERNO(LCE)LONGITUD DE CAMINO
Árbol extendido
A
B C
D E F G H
I J LK
El número de nodos especiales de este árbol es 25.
![Page 13: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/13.jpg)
• Es la sumatoria de las longitudes de camino de todos los nodos especiales del árbol y se calcula con la siguiente formula
1
2
*h
i
i ineLCE
DONDE:
h= ALTURA
i = NIVEL
Ne= NODO ESPECIAL
LONGITUD DE CAMINO EXTERNO(LCE)
LONGITUD DE CAMINO
![Page 14: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/14.jpg)
• h= altura
• i = nivel del árbol
• Ne= numero de nodos especiales en el nivel i
LCE= 1x2 + 1x3+11x4+12x5
LCE =109
LONGITUD DE CAMINO EXTERNO(LCE)
LONGITUD DE CAMINO
![Page 15: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/15.jpg)
• LA MEDIA DE LA LONGITUD DE CAMINO EXTERNO se calcula dividiendo el LCE, para el número de nodos especiales.
LCEM= LCE/Ne
LCE= 109
Ne= 25
LCEM = 109/25=4.36
MEDIA DE LONGITUD DE CAMINO EXTERNO(LCE)
LONGITUD DE CAMINO
![Page 16: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/16.jpg)
ÁRBOLES BINARIOS
Es una estructura ordenada, en el cual cada nodo puede tener como máximo dos subárboles conocidos como subárbol izquierdo y subárbol derecho, dependiendo de su ubicación con respecto a la raíz
![Page 17: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/17.jpg)
EJEMPLOS
ÁRBOLES BINARIOS
• Árboles de búsquedas
27
14 57
7
77
32 59
11 50
![Page 18: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/18.jpg)
EJEMPLOS
ÁRBOLES BINARIOS
Árbol genealógico
Pedro
mamá papá
abueloabuelo abuelaabuela
![Page 19: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/19.jpg)
EJEMPLOS
ÁRBOLES BINARIOS
Árboles que representa expresiones matemáticas
(a*b)+{(c÷d) 3ʌ}
+
* ᶺ
a
d
÷ 3
c
b
![Page 20: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/20.jpg)
TIPOS DE ÁRBOLES BINARIOSÁRBOLES BINARIOS DISTINTOS
Estructura y distribución de arcos diferentes
a. b.
27
14 57
7
11
27
14 57
7
11
ÁRBOLES BINARIOS
![Page 21: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/21.jpg)
TIPOS DE ÁRBOLES BINARIOSÁRBOLES BINARIOS SIMILARES
Estructura idénticas e información de nodos diferentes
27
14 0
7
1
ÁRBOLES BINARIOS
27
14 57
7
11
b.a.
![Page 22: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/22.jpg)
TIPOS DE ÁRBOLES BINARIOSÁRBOLES BINARIOS EQUIVALENTES
Estructura idénticas e información de nodos iguales
27
14 57
7
11
ÁRBOLES BINARIOS
27
14 57
7
11
b.a.
![Page 23: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/23.jpg)
TIPOS DE ÁRBOLES BINARIOSÁRBOLES BINARIOS
Árboles binarios distintos: ………………..
Árboles binarios similares: ………………..
Árboles binarios equivalentes: …………..
Ejemplos:
![Page 24: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/24.jpg)
ÁRBOLES BINARIOS COMPLETOS
ÁRBOLES BINARIOS
Árbol binario completo(ABC), es aquel en el cual todos sus nodos excepto los del ultimo nivel tiene dos hijos
![Page 25: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/25.jpg)
ÁRBOLES BINARIOS COMPLETOS
ÁRBOLES BINARIOS
CÁLCULO DEL NÚMERO DE NODOS.
Números de nodos(ABC)=2h -1
h= altura del árbol
Números de nodos(ABC)=24 -1
Números de nodos(ABC)=15
![Page 26: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/26.jpg)
REPRESENTACIÓN DE ÁRBOLES GENERALES COMO BINARIOS
ÁRBOLES BINARIOS
• Enlazar los hijos de cada nodo en forma vertical
![Page 27: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/27.jpg)
REPRESENTACIÓN DE ÁRBOLES GENERALES COMO BINARIOS
ÁRBOLES BINARIOS
• Enlazar los nodos hermanos en forma horizontal
![Page 28: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/28.jpg)
REPRESENTACIÓN DE ÁRBOLES GENERALES COMO BINARIOS
ÁRBOLES BINARIOS
![Page 29: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/29.jpg)
REPRESENTACIÓN DE ÁRBOLES GENERALES COMO BINARIOS
ÁRBOLES BINARIOS
• Girar aproximadamente 45 grados
![Page 30: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/30.jpg)
ASPECTOS IMPORTANTES
ÁRBOLES BINARIOS
• Si la rama derecho de cada nodo excepto el nodo raíz es diferente de vacío, se encuentra un nodo que era hermano en el árbol general.
– 5 hermano de 4
– 6 hermano de 2
– 11 hermano de 5
• Si la rama izquierda de cada nodo excepto el nodo raíz es diferente de vacío, se encuentra un nodo que era hijo en el árbol general.
– 5 hermano de 6
– 2 hermano de 7
– 4 hermano de 9
![Page 31: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/31.jpg)
ASPECTOS IMPORTANTES
ÁRBOLES BINARIOS
• Si la rama izquierda de cada nodo excepto el nodo raíz es diferente de vacío, se encuentra un nodo que era hijo en el árbol general.
– 5 hijo de 6
– 9 hijo de 5
– 4 hijo de 9
![Page 32: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/32.jpg)
REPRESENTACIÓN DE ÁRBOLES GENERALES COMO BINARIOS
ÁRBOLES BINARIOSEjemplo
![Page 33: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/33.jpg)
REPRESENTACIÓN DE ÁRBOLES GENERALES COMO BINARIOS
ÁRBOLES BINARIOSEjemplo:
![Page 34: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/34.jpg)
REPRESENTACIÓN DE ÁRBOLES GENERALES COMO BINARIOS
ÁRBOLES BINARIOSEjemplo:
![Page 35: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/35.jpg)
RECORRIDOS EN ÁRBOLES BINARIOS
RECORRIDOSRecorrido en preorden
• Visitar la raíz
• Recorrer el subárbol izquierdo
• Recorrer el subárbol derecho
Recorrido en inorden
• Recorrer el subárbol izquierdo
• Visitar la raíz
• Recorrer el subárbol derecho
Recorrido en postorden
• Recorrer el subárbol izquierdo
• Recorrer el subárbol derecho
• Visitar la raíz
![Page 36: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/36.jpg)
Ejemplos:
Recorrido en preorden
104,71,17,3,18,19,240,108,110,245
Recorrido en inorden
3,17,18 ,71 ,19, 104 , 108, 110 240, 245
Recorrido en postorden3 18 17 19 71 110 108 245 240
104
RECORRIDOS EN ÁRBOLES BINARIOS
![Page 37: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/37.jpg)
Ejemplos:
Recorrido en preorden:
Recorrido en inorden:
Recorrido en postorden:
RECORRIDOS EN ÁRBOLES BINARIOS
![Page 38: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/38.jpg)
ÁRBOLES DE BINARIOS DE BÚSQUEDA
Formalmente se define un árbol binario de búsqueda dela siguiente manera: Para todo nodo T del árbol se debecumplir que todos los valores almacenados en el subárbolizquierdo de T sean menores o iguales a la informaciónguardada en el nodo T. De forma similar, todos los valoresalmacenados en el subárbol derecho de T deben sermayores o iguales a la información guardada en el nodo T
![Page 39: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/39.jpg)
INSERCIÓN
OPERACIONS CON ÁRBOLES BINARIOS
1. Comparar la clave a insertar con la raíz del árbol. Si es mayor, se
sigue con el subárbol derecho. Si es menor, se continúa con el
subárbol izquierdo.
2. Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las
siguientes condiciones:
a. El subárbol derecho, o el subárbol izquierdo, es igual a vacío,
en cuyo caso procederá a insertar el elemento en el lugar que
le corresponde.
b. La clave que se quiere insertar está en el nodo analizado, por
lo tanto no se lleva a cabo la inserción. Este caso es válido sólo
cuando la aplicación exige que no se repitan elementos.
![Page 40: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/40.jpg)
INSERCIÓN
OPERACIONS CON ÁRBOLES BINARIOS
Insertar los siguientes datos:
15, 5,17,3,16,8,21,6,25,11,13
![Page 41: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/41.jpg)
Ejemplo:
Insertar los elementos 120-87-43-65-140-99-130-22-56
INSERCIÓN
OPERACIONS CON ÁRBOLES BINARIOS
![Page 42: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/42.jpg)
Ejemplo: INSERCIÓN
OPERACIONS CON ÁRBOLES BINARIOS
![Page 43: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/43.jpg)
La operación de búsqueda consiste en lo siguiente.
Comparar el valor buscado con la informara del nodo visitado, si no
es igual, se deberá continuar sólo por alguno de los dos subárboles
les.
BÚSQUEDA
OPERACIONS CON ÁRBOLES BINARIOS
![Page 44: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/44.jpg)
En la eliminación de un árbol binario de búsqueda , se deben
distinguir los siguientes casos:
1. Si el elemento a eliminar es terminal u hoja, simplemente se
suprime redefiniendo el puntero de su predecesor.
2. Si el elemento a eliminar tiene un solo descendiente, entonces tiene
que sustituirse por ese descendiente.
3. Si el elemento a eliminar tiene los dos descendientes, entonces se
tiene que sustituir por el nodo que se encuentra más a la izquierda
en el subárbol derecho o por el nodo que se encuentra más a la
derecha en el subárbol izquierdo.
ELIMINACIÓN
OPERACIONS CON ÁRBOLES BINARIOS
![Page 45: Diapositiva de prueba](https://reader034.fdocumento.com/reader034/viewer/2022052622/559622d01a28ab79708b46a0/html5/thumbnails/45.jpg)
Bibliografía
Osvaldo, C. (2002). Estructuras de Datos.México: McGRAW-HILL.