Download Árboles
Document related concepts
Transcript
Francisco J. Hernández López [email protected] Estructura de datos no lineal, en la que cada elemento sólo puede estar enlazado con su predecesor (o nodo padre) y sus sucesores (o nodos hijos) Existe un único camino entre el primer nodo de la estructura y cualquier otro nodo Se utilizan para representar jerarquías: Árbol genealógico Diagramas de organización Formulas matemáticas Numerar capítulos y secciones de un libro Algoritmos para ordenación, búsqueda, compilación, etc. Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 2 Nodo:Vértices o elementos de un árbol Enlace/arco/borde/arista: Conexión entre dos nodos consecutivos Nodo: Raíz: Todo árbol que no es vacío, tiene un único nodo raíz, el cual es el nodo superior de la jerarquía Terminal u hoja: Nodo que no contiene ningún subárbol, o que no tiene hijos Interior o rama: Nodo con uno o más subárboles, o nodo que no es hoja Descendiente o hijo: Cada subárbol de un nodo Ascendiente o padre: Nodo de jerarquía superior a un nodo dado Hermanos: Nodos que tienen el mismo padre Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 3 Bosque: Colección de árboles Orden del árbol: Es el número de hijos que puede llegar a tener cada elemento del árbol. Ej.: En un árbol binario, cada nodo solo puede llegar a tener dos hijos, por lo tanto el orden del árbol es 2 Grado del árbol: Es el número de hijos que tiene el elemento con más hijos dentro del árbol Nivel de un nodo: Es la distancia (medida en nodos) que hay entre el nodo y la raíz. Si consideramos que el nivel de la raíz es 1, entonces el nivel que tienen sus hijos es 2 Nota: También se puede considerar que la raíz tiene nivel 0. Entonces el nivel de un nodo será la longitud del camino (medido en enlaces) desde la raíz al nodo Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 4 Altura del árbol: Es el nivel del nodo de mayor nivel. Como cada nodo del árbol se puede considerar a su vez como la raíz de un árbol, entonces podemos hablar de altura de ramas Peso del árbol: Número de nodos terminales (u hojas) Factor de equilibrio: Se define como la altura del subárbol derecho menos la altura del subárbol izquierdo 𝐹𝐸 = 𝐴𝑆𝐷 − 𝐴𝑆𝐼 Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 5 A B E C F K G L D H M Raíz: A Hojas: F, H, I, K, L, M, N, O Ramas: B, C, D, E, G, J Hijos: B, C, D, E, F, G, H, I, J, K, L, M, N, O Padres: A, B, C, D, E, G, J Hermanos: (B, C, D) de A, (E, F) de B, (H, I, J) de D, (L, M) de G, (N, O) de J Programación Avanzada, Árboles. Francisco J. Hernández-López I J N O Orden del árbol: 3 Grado del árbol: 3 Nivel del nodo F: 3 Altura del árbol: 4 Altura de la rama B: 3 Altura de la rama I: 1 Peso del árbol: 8 𝐹𝐸 en el nodo D: 1 (Sin considerar el nodo I) Agosto-Diciembre 2014 6 Son árboles en los que cada nodo no puede tener más de dos hijos, por lo tanto son árboles de orden 2 Tipos de árboles binarios: Completamente balanceados/Completos/Perfectos: Si cada nodo tiene exactamente dos hijos o no tiene hijos y si cada hoja está al mismo nivel. Un árbol binario de nivel 𝑛 tiene 2𝑛 − 1 nodos Equilibrados: Las alturas de los dos subárboles de cada nodo tiene como máximo una diferencia de 1 en valor absoluto, es decir el 𝐹𝐸 ≤ 1 en cada nodo Degenerados: Todos sus nodos solo tienen un subárbol Similares: Árboles con la misma estructura Equivalentes: Árboles con la misma estructura y contienen la misma información Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 7 A B C D H E I J G F K L Programación Avanzada, Árboles. Francisco J. Hernández-López M N O Agosto-Diciembre 2014 8 A A B D H C E I F J B G K D L M Programación Avanzada, Árboles. Francisco J. Hernández-López H C E F I G K L M Agosto-Diciembre 2014 9 a 1 b 2 d 3 e g 4 5 Nota: Estos árboles tienen orden 2 y grado 1 Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 10 f a b g c d e Programación Avanzada, Árboles. Francisco J. Hernández-López h i j Agosto-Diciembre 2014 11 a a b b c d e Programación Avanzada, Árboles. Francisco J. Hernández-López c d e Agosto-Diciembre 2014 12 A A B D F E J B C K G L I H M N Árbol de orden 3 Programación Avanzada, Árboles. Francisco J. Hernández-López D C F E J K G L I H M N 1. Enlazar los hijos de cada nodo en forma horizontal (todos los hermanos) Agosto-Diciembre 2014 13 A A B D F E J B C K G L I H M N Árbol de orden 3 Programación Avanzada, Árboles. Francisco J. Hernández-López D J C E F K G L H I M N 2. Enlazar en forma vertical el nodo padre con el hijo que se encuentra más a la izquierda. Además debe eliminarse el enlace de dicho padre con el resto de sus hijos Agosto-Diciembre 2014 14 A B D C F E J K G L I H M N Árbol de orden 3 Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 15 A B A B D C J D F E J K G L I H M G E N Árbol de orden 3 F K M L I N Árbol binario Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 16 A B E C F L D G M H N Programación Avanzada, Árboles. Francisco J. Hernández-López I O J K P Agosto-Diciembre 2014 17 A B E C J D K P L F Q R S T U V Bosque de árboles Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 18 A B E C J D K F P L Q R S T U V 1. Enlazar en forma horizontal las raíces de los distintos árboles generales Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 19 A B E C J D K F P L Q R S T U V 2. Enlazar los hijos de cada nodo en forma horizontal (todos los hermanos) Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 20 A J B E C D K F P L Q R S T U V 3. Enlazar en forma vertical el nodo padre con el hijo que se encuentra más a la izquierda. Además se debe eliminar el vínculo del padre con el resto de sus hijos Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 21 Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 22 A J B C E F K D P L Q R S T Árbol binario Programación Avanzada, Árboles. Francisco J. Hernández-López U V Agosto-Diciembre 2014 23 A J B D E C F G R K H L S T U V W X Bosque de árboles Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 24 Añadir o insertar elementos Buscar o localizar elementos Borrar o eliminar elementos Moverse a través del árbol Recorrer todo el árbol Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 25 Pre-orden: /*AB+AD (raíz, izq, der) / * A In-orden: A*B/A+D (izq, raíz, der) + B A D Programación Avanzada, Árboles. Francisco J. Hernández-López Post-orden: AB*AD+/ (izq, der, raíz) Agosto-Diciembre 2014 26 Se pueden implementar tanto con memoria estática así como con memoria dinámica A continuación veremos como implementar un árbol binario con memoria dinámica: Programación Avanzada, Árboles. Francisco J. Hernández-López Agosto-Diciembre 2014 27